Optimizing SQLite LIKE Queries with String Literals and Indexes

Understanding the LIKE Optimization Constraints in SQLite

The SQLite database engine is renowned for its lightweight nature and efficiency, but like any database system, it has specific optimization rules that must be adhered to for optimal performance. One such optimization pertains to the LIKE operator, which is used for pattern matching in SQL queries. The LIKE operator can leverage indexes to speed up queries, but only under certain conditions. Specifically, the right-hand side (RHS) of the LIKE operator must be a string literal or a parameter bound to a string literal. This constraint can lead to unexpected performance issues when the RHS is an expression that yields a constant string, even if the expression is deterministic and known to produce a constant value at runtime.

To illustrate this, consider a table t1 with the following schema:

CREATE TABLE t1 (
    id INTEGER NOT NULL PRIMARY KEY,
    name TEXT NOT NULL,
    name_simple TEXT NOT NULL AS (UPPER(name)) STORED
);
CREATE INDEX t1_name_simple ON t1(name_simple);

In this schema, the name_simple column is a computed column that stores the uppercase version of the name column. An index is created on name_simple to facilitate faster searches. Now, consider the following queries:

EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE name_simple LIKE 'A%';
EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE name_simple LIKE UPPER('a%');

The first query uses the index on name_simple because the RHS of the LIKE operator is a string literal ('A%'). However, the second query does not use the index, even though UPPER('a%') yields a constant string ('A%'). This behavior is due to the fact that SQLite’s query planner does not evaluate expressions at compile time to determine if they can be optimized using an index. Instead, it treats the RHS of the LIKE operator as a black box, assuming that it could produce any value, including one that starts with a wildcard character, which would necessitate a full table scan.

The Role of Compile-Time Evaluation in Query Optimization

The core issue here lies in the distinction between compile-time (or prepare-time) evaluation and runtime evaluation in SQLite. During the compilation phase, SQLite generates bytecode that will be executed to perform the query. However, the query planner does not execute the code during this phase; it merely generates it. As a result, expressions on the RHS of the LIKE operator are not evaluated, and their potential to be optimized using an index cannot be determined.

This limitation is particularly evident when using functions like UPPER() or RTRIM() in conjunction with the LIKE operator. For example, consider the following query:

SELECT * FROM t1 WHERE name_simple LIKE RTRIM(?) || '%';

In this case, the RHS of the LIKE operator is an expression that involves a parameter (?) and a function (RTRIM). Even though the expression yields a constant string at runtime, the query planner cannot determine this at compile time. As a result, it generates a query plan that assumes the worst-case scenario: that the RHS could start with a wildcard character, necessitating a full table scan.

This behavior is consistent with SQLite’s general approach to query optimization, which prioritizes robustness and predictability over speculative optimizations. By assuming that expressions on the RHS of the LIKE operator could produce any value, SQLite ensures that the generated query plan will work correctly in all cases, even if it is not the most efficient plan for a specific set of inputs.

The Impact of ICU Extension and Case Sensitivity on LIKE Optimization

Another layer of complexity arises when using the ICU extension in SQLite, which provides enhanced support for Unicode and locale-specific string comparisons. When the ICU extension is loaded, it overrides the default LIKE operator with its own implementation, which is more sophisticated but also more computationally expensive. This override has several implications for query optimization.

First, the ICU extension’s LIKE operator does not support the same optimizations as the default LIKE operator. Specifically, it does not use indexes for pattern matching, even if the RHS is a string literal. This means that queries using the ICU LIKE operator will always result in a full table scan, regardless of the structure of the query or the presence of indexes.

Second, the ICU extension’s behavior is affected by the PRAGMA case_sensitive_like setting. When this pragma is enabled, the ICU LIKE operator is disabled, and SQLite reverts to its default LIKE implementation. However, once the ICU LIKE operator is disabled, it cannot be re-enabled without reloading the ICU extension. This behavior can lead to unexpected performance issues, especially if the PRAGMA case_sensitive_like setting is changed dynamically during the execution of a program.

Consider the following example:

.load libIcu.so
CREATE INDEX t1_name ON t1(name);
CREATE INDEX t1_name_nc ON t1(name COLLATE NOCASE);
INSERT INTO t1(name) VALUES ('Ägidius');
EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE name LIKE 'ä%';
PRAGMA case_sensitive_like=on;
EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE name LIKE 'ä%';
PRAGMA case_sensitive_like=off;
EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE name LIKE 'ä%';

In this example, the first query uses the ICU LIKE operator and performs a full table scan. The second query, with PRAGMA case_sensitive_like=on, reverts to the default LIKE operator and uses the index on name. The third query, with PRAGMA case_sensitive_like=off, attempts to use the ICU LIKE operator again but fails to do so because the ICU extension has been effectively disabled by the previous pragma setting.

Strategies for Optimizing LIKE Queries in SQLite

Given the constraints and complexities discussed above, there are several strategies that can be employed to optimize LIKE queries in SQLite:

1. Use String Literals Directly: Whenever possible, use string literals directly on the RHS of the LIKE operator. This allows SQLite to leverage indexes and perform efficient pattern matching. For example, instead of using UPPER('a%'), use 'A%' directly in the query.

2. Avoid Expressions on the RHS: Avoid using expressions that yield constant strings on the RHS of the LIKE operator. If you need to manipulate the string before using it in the query, do so in the application code and pass the result as a parameter. For example, instead of SELECT * FROM t1 WHERE name_simple LIKE RTRIM(?) || '%';, use SELECT * FROM t1 WHERE name_simple LIKE ?; and pass the result of RTRIM(?) || '%' as a parameter.

3. Use COLLATE NOCASE for Case-Insensitive Searches: If you need to perform case-insensitive searches, consider using the COLLATE NOCASE collation sequence. This allows you to create indexes that support case-insensitive pattern matching without resorting to the ICU extension. For example:

   CREATE INDEX t1_name_nc ON t1(name COLLATE NOCASE);
   SELECT * FROM t1 WHERE name LIKE 'a%' COLLATE NOCASE;
   

4. Be Mindful of the ICU Extension: If you are using the ICU extension, be aware of its limitations and the impact of the PRAGMA case_sensitive_like setting. If you need to perform case-sensitive searches, consider disabling the ICU extension or using a different approach to pattern matching.

5. Consider Alternative Approaches: In some cases, it may be more efficient to use alternative approaches to pattern matching, such as full-text search (FTS) or regular expressions. These approaches have their own trade-offs and may not be suitable for all use cases, but they can provide better performance in certain scenarios.

Conclusion

Optimizing LIKE queries in SQLite requires a deep understanding of the database engine’s query planner and the constraints imposed by its optimization rules. By adhering to best practices, such as using string literals directly, avoiding expressions on the RHS of the LIKE operator, and being mindful of the impact of the ICU extension, you can ensure that your queries are as efficient as possible. While SQLite’s approach to query optimization may seem restrictive at times, it is designed to provide robust and predictable performance across a wide range of use cases. By working within these constraints and leveraging the available tools and techniques, you can achieve optimal performance in your SQLite applications.