SQLite Assertion Failure in sqlite3FindInIndex with COLLATE Operator Indexes

Issue Overview: Indexed Query Execution Failure Due to COLLATE Operator in Expression-Based Index

A critical assertion failure occurs in SQLite when executing DELETE statements that utilize an index containing COLLATE operators in their indexed expressions. The crash manifests specifically when the following conditions converge:

1. Schema Design with Expression-Based Indexes: A table is created with an index that includes expressions combining logical operators (e.g., ~name) and explicit collation sequences (e.g., COLLATE RTRIM). For example:

   CREATE INDEX index1 ON t0 (FALSE COLLATE RTRIM, ~name COLLATE RTRIM ASC);
   

   This creates an index where the first column is a boolean expression with RTRIM collation and the second column is a bitwise NOT operation on "name" with ascending RTRIM collation.

2. DELETE Statement with INDEXED BY Clause: A DELETE operation explicitly forces the use of this non-standard index via INDEXED BY index1, while the WHERE clause contains a complex boolean expression involving:

   • Multiple COLLATE operators
   • Nested IS/IS NOT operators
   • Subquery-free IN operator with a table reference
     Example:

   DELETE FROM t0 AS t0 INDEXED BY index1 
   WHERE t0.name IS (~name) COLLATE RTRIM IS NOT TRUE COLLATE RTRIM IS NOT ~name NOT IN t0;
   

3. Assertion-Enabled Build Configuration: The SQLite library is compiled with assertion checks enabled (-DSQLITE_DEBUG or similar). The assertion triggering the crash is:

   sqlite3FindInIndex: Assertion `pReq!=0 || pRhs->iColumn==XN_ROWID || pParse->nErr' failed.
   

   This indicates the query planner’s index lookup subsystem encountered an unexpected state while processing the forced index usage with collation-modified expressions.

The core conflict arises from SQLite’s index management subsystem failing to properly validate the compatibility between the index’s collation-defined expressions and the query’s WHERE clause predicates when using forced index selection. The COLLATE operators create implicit type affinity and comparison rule modifications that are not fully reconciled during index lookup path selection, leading to internal consistency check failures under assertion-enabled builds.

Possible Causes: Collation Sequence Mismatch in Indexed Expression Resolution

1. Implicit Collation Inheritance in Indexed Expressions

When an index includes expressions with COLLATE operators (e.g., ~name COLLATE RTRIM), SQLite must store index entries using the specified collation for comparison and sorting. However, when the query optimizer attempts to utilize such an index for WHERE clause evaluation, it may incorrectly map the original column’s collation (from table definition) to the indexed expression’s collation.

In the provided schema:

• The t0.name column has an implicit BINARY collation (default for PRIMARY KEY)
• The index index1 stores ~name with RTRIM collation
• The DELETE query’s WHERE clause applies additional COLLATE RTRIM modifiers

This creates a multi-layered collation context where the index’s stored collation (RTRIM) must reconcile with both the base column’s collation (BINARY) and the query’s collation (RTRIM). If the query planner’s index selection logic fails to account for these layers, it may generate invalid comparison operations between differently collated values.

2. Forced Index Usage Bypassing Collation Compatibility Checks

The INDEXED BY index1 clause overrides SQLite’s automatic index selection, forcing the use of an index that might not be optimal for the query’s collation requirements. Normally, SQLite would reject using an index if the collation of the indexed expression doesn’t match the collation required by the query. However, when forced via INDEXED BY, this safety check is bypassed, leading to scenarios where:

• The index stores data using RTRIM collation
• The query’s WHERE clause performs comparisons with mixed collations (BINARY from PRIMARY KEY and RTRIM from explicit COLLATE)
• The comparison operator (IS, IN) expects specific collation rules

This mismatch causes the index lookup logic to attempt invalid comparisons between values with different collation definitions, triggering the assertion failure during query planning.

3. Incomplete Error State Propagation in Parse Tree Validation

The assertion pParse->nErr in the failure message suggests that the SQLite parser (pParse) should have detected and recorded an error before reaching this code path. However, the forced index usage combined with collation mismatches creates a scenario where:

• The query planner (sqlite3FindInIndex) assumes an error must have been logged (pParse->nErr > 0)
• No actual error occurs due to incomplete collation compatibility checks
• The assertion fails because the required error state (pParse->nErr) isn’t set despite invalid index usage

This indicates a gap in error checking between the index selection subsystem and the overall query parser when dealing with forced indexes containing collation-modified expressions.

Troubleshooting Steps, Solutions & Fixes: Collation-Aware Index Design and Query Validation

1. Schema Modification: Eliminate Collation Conflicts in Indexed Expressions

Problem: The index index1 uses COLLATE RTRIM on both a boolean literal (FALSE) and a column expression (~name), while the base table’s PRIMARY KEY uses default BINARY collation.

Solution:

• Remove unnecessary COLLATE operators from index definitions unless explicitly required
• Align index expression collation with table column collation

Revised Schema:

CREATE TEMP TABLE IF NOT EXISTS t0 (
  name TEXT PRIMARY KEY ON CONFLICT ABORT COLLATE RTRIM
);
CREATE INDEX index1 ON t0 (FALSE, ~name COLLATE RTRIM ASC);

Key changes:

• Added explicit COLLATE RTRIM to PRIMARY KEY definition to match index’s collation
• Removed COLLATE RTRIM from FALSE expression (unnecessary for boolean)
• Retained COLLATE RTRIM on ~name only where essential

Verification:

EXPLAIN QUERY PLAN 
DELETE FROM t0 INDEXED BY index1 WHERE ...;

Check output for warnings about index incompatibility. A properly aligned schema will show no warnings.

2. Query Rewriting: Avoid Forced Index Usage with Complex Collations

Problem: The INDEXED BY index1 clause forces use of an index with collation rules that don’t match the WHERE clause’s implicit collations.

Solution:

• Remove INDEXED BY clause
• Let query optimizer choose appropriate index
• If forced index is mandatory, align WHERE clause collations with index

Revised Query:

DELETE FROM t0 AS t0
WHERE t0.name COLLATE RTRIM IS (~name COLLATE RTRIM) 
  COLLATE RTRIM IS NOT TRUE 
  COLLATE RTRIM IS NOT ~name NOT IN t0;

Added explicit COLLATE RTRIM to first ~name reference to match index’s collation.

Verification:
Use SQLite’s EXPLAIN to confirm index selection:

EXPLAIN 
DELETE FROM t0 WHERE ...;

Validate that chosen index matches expected behavior without forced usage.

3. SQLite Version Upgrade: Apply Collation Handling Fixes

Problem: The bug was fixed in check-in a8da85c57e07721d, which addresses incorrect results from queries using indexes with COLLATE operators in IN expressions.

Solution:

• Upgrade to SQLite 3.39.0+ containing the fix
• Rebuild from source with assertion checks enabled to verify resolution

Migration Steps:

1. Download latest amalgamation:

   wget https://sqlite.org/sqlite-amalgamation-latest.zip
   unzip sqlite-amalgamation-latest.zip
   

2. Compile with debug symbols:

   gcc -DSQLITE_DEBUG -DSQLITE_ENABLE_EXPLAIN_COMMENTS \
       -DSQLITE_ENABLE_STAT4 -g -O0 \
       sqlite3.c fuzzershell.c -o fuzzershell -ldl -lpthread
   

3. Re-run test case:

   ./fuzzershell < crash.sql
   

Validate that no assertion failures occur and DELETE operation completes successfully.

Post-Upgrade Validation:
Execute Richard Hipp’s test script to confirm correct behavior:

.mode box
CREATE TABLE t1(x TEXT PRIMARY KEY, y TEXT, z INT);
INSERT INTO t1(x,y,z) VALUES('alpha','ALPHA',1),('bravo','charlie',1);
CREATE INDEX i1 ON t1(+y COLLATE NOCASE);
SELECT * FROM t1;
DELETE FROM t1 INDEXED BY i1
 WHERE x IS +y COLLATE NOCASE IN (SELECT z FROM t1)
 RETURNING *;
SELECT * FROM t1;

Expected output:

• First SELECT shows 2 rows
• DELETE removes 1 row (alpha-ALPHA)
• Final SELECT shows 1 remaining row (bravo-charlie)

4. Collation-Aware Index Design Patterns

To prevent recurrence, adopt these indexing practices:

A. Column Collation Consistency

• Define collation at table column level when possible
• Use same collation in indexes referencing those columns

B. Expression Index Collation Narrowing
When indexing expressions:

-- Instead of:
CREATE INDEX idx ON tbl (col1 COLLATE NOCASE, col2);
-- Prefer:
CREATE INDEX idx ON tbl (col1, col2) COLLATE NOCASE;

This applies collation to entire index rather than individual columns.

C. Collation Usage Audit
Regularly check schema for collation mismatches:

SELECT name, sql 
FROM sqlite_master 
WHERE sql LIKE '%COLLATE%' AND type = 'index';

Review results to ensure COLLATE usage is necessary and consistent.

5. Advanced Debugging: SQLITE_DEBUG Instrumentation

For developers debugging similar issues, enable SQLite’s internal diagnostics:

Compile with Extended Assertions:

CFLAGS="-DSQLITE_DEBUG \
        -DSQLITE_ENABLE_SELECTTRACE \
        -DSQLITE_ENABLE_WHERETRACE" \
make fuzzershell

Diagnostic Queries:

1. Enable WHERE clause tracing:

   EXPLAIN 
   DELETE FROM t0 INDEXED BY index1 WHERE ...;
   

2. Check collation compatibility between index and WHERE clause:

   SELECT ic.name, ic.coll, e.coll 
   FROM pragma_index_info('index1') AS ic
   JOIN pragma_table_xinfo('t0') AS e 
     ON ic.name = e.name;
   

3. Validate index usability for query:

   EXPLAIN QUERY PLAN 
   DELETE FROM t0 INDEXED BY index1 WHERE ...;
   

Expected Output Analysis:

• SCAN TABLE t0 USING INDEX index1 indicates forced index usage
• Warnings about collation sequence mismatch signal improper index selection

6. Fuzzing Mitigation: SQL Query Sanitization

For fuzzer-generated queries like the original crash case:

Sanitization Rules:

1. Reject queries mixing INDEXED BY with:
   • COLLATE operators in index expressions
   • IN operators without subqueries
   • Nested IS/IS NOT operators
2. Normalize collation sequences:

   # Pseudocode for query sanitizer
   def sanitize_query(query):
       query = re.sub(r'COLLATE\s+\w+', 'COLLATE BINARY', query)
       return query
   

3. Validate index/column collation parity before execution

Implementation Example:

-- Before executing DELETE, check index collation
SELECT 
  il.name AS index_column,
  il.coll AS index_collation,
  ti.name AS table_column,
  ti.coll AS table_collation
FROM pragma_index_list('t0') AS il
JOIN pragma_index_xinfo(il.name) AS ix
JOIN pragma_table_xinfo('t0') AS ti
  ON ix.name = ti.name
WHERE il.origin = 'c' -- explicitly created indexes
  AND il.coll != ti.coll;

Any results indicate collation mismatches requiring correction.

7. Query Planner Override Prevention

To avoid forced index misuse:

Disable INDEXED BY in High-Risk Environments:

// Custom SQLite build with INDEXED BY removal
#define SQLITE_OMIT_INDEXED_BY

Runtime Enforcement:

-- Create trigger to block INDEXED BY queries
CREATE TEMP TRIGGER prevent_indexed_by 
BEFORE DELETE ON t0
WHEN EXISTS (SELECT 1 FROM sqlite_master WHERE sql LIKE '%INDEXED BY%')
BEGIN
  SELECT RAISE(ABORT, 'INDEXED BY clause prohibited');
END;

Query Rewriting Middleware:
Implement a pre-processor that removes or validates INDEXED BY clauses against collation rules before passing queries to SQLite.

8. Comprehensive Collation Handling Test Suite

Develop regression tests covering:

Test Case 1: Index Collation vs Query Collation

CREATE TABLE coll_test(a TEXT COLLATE NOCASE);
CREATE INDEX coll_idx ON coll_test(a COLLATE BINARY);
SELECT * FROM coll_test INDEXED BY coll_idx WHERE a = 'ABC';
-- Should fail unless explicit COLLATE BINARY in query

Test Case 2: Expression Index with Multiple Collations

CREATE TABLE coll_multi (
  x TEXT COLLATE RTRIM, 
  y TEXT COLLATE NOCASE
);
CREATE INDEX coll_multi_idx ON coll_multi (x COLLATE BINARY, y);
INSERT INTO coll_multi VALUES ('test ', 'TEST');
SELECT * FROM coll_multi 
WHERE x COLLATE BINARY = 'test' AND y = 'test';
-- Verify index usage correctness

Test Case 3: DELETE with INDEXED BY and COLLATE

CREATE TABLE coll_del (z TEXT PRIMARY KEY COLLATE RTRIM);
CREATE INDEX coll_del_idx ON coll_del(z COLLATE NOCASE);
DELETE FROM coll_del INDEXED BY coll_del_idx 
WHERE z = 'value' COLLATE BINARY;
-- Expect error or explicit collation mismatch warning

Automate these tests using SQLite’s TCL test harness or custom scripts to ensure collation handling remains robust across versions.

Final Recommendation Matrix

By systematically addressing collation sequence alignment between index definitions and query predicates, enforcing index selection best practices, and utilizing SQLite’s enhanced collation handling from version 3.39.0 onward, developers can eliminate this class of assertion failures while ensuring correct query results under complex collation scenarios.