Issue Overview: Assertion Failure During ANALYZE with STAT4 Optimization Enabled

The core issue involves an assertion failure (pIn1!=pOut) triggered during the execution of ANALYZE when SQLite’s STAT4 optimization is enabled. This occurs in scenarios where tables have indexes defined with constant expressions (e.g., 0||1 or 0<1). The failure manifests as a crash in the SQLite virtual machine (VDBE) due to overlapping register assignments during the statistics collection process.

The problem is rooted in how SQLite’s query planner generates bytecode for sampling index data during ANALYZE when STAT4 is active. The STAT4 optimization enhances the query planner’s ability to estimate selectivity by storing histogram data for indexed columns. However, when indexes contain deterministic constant expressions (which evaluate to the same value for all rows), the bytecode generator may inadvertently assign the same register for both input (pIn1) and output (pOut) operands in a critical VDBE operation. This violates an internal assertion designed to prevent register aliasing, leading to an abrupt termination of the process.

Key elements of the failure include:

• Indexes with constant expressions: The presence of indexes like CREATE INDEX i ON v0(0,0,0,0,0||1) or CREATE INDEX i0 ON v1(0<1) creates a scenario where the indexed values are invariant across all rows.
• STAT4 sampling logic: The ANALYZE command attempts to sample these indexes to build statistical models, but the bytecode generated for sampling fails to account for the degenerate nature of constant expressions.
• Register allocation conflict: During bytecode generation, the virtual machine assigns overlapping registers for operations that manipulate these invariant values, triggering the assertion.

This issue is particularly insidious because it only surfaces when both STAT4 is enabled and the database schema contains indexes with constant expressions. The failure is deterministic for such schemas but remains hidden in typical usage scenarios where indexes reference actual column data.

Possible Causes: Degenerate Index Handling in STAT4 Sampling Logic

The assertion failure arises from a combination of factors in SQLite’s query planner and bytecode generation subsystems. Below are the primary contributors to the issue:

1. Constant Expression Indexes and STAT4 Sampling

Indexes defined with expressions that evaluate to constants (e.g., 0||1, 0<1) create degenerate statistical profiles. Since all rows in such an index have identical values, the histogram data collected by STAT4 becomes trivial. SQLite’s sampling logic, however, is not optimized for this edge case. When generating bytecode to sample these indexes, the system assumes that the index contains variable data and attempts to iterate over its entries. For constant expressions, this iteration collapses into a single step, leading to register allocation conflicts.

2. VDBE Register Aliasing in OP_SeekEnd/OP_IfNoHope Operations

The crash occurs during the execution of virtual machine opcodes responsible for positioning the cursor on the last entry of an index (OP_SeekEnd) and checking for the absence of valid rows (OP_IfNoHope). These opcodes require distinct input and output registers to avoid overwriting critical values. In the presence of constant expression indexes, the query planner’s register allocator incorrectly assigns the same register (pIn1 and pOut) for both operations. This violates the assertion pIn1!=pOut in sqlite3VdbeExec(), which guards against such aliasing.

3. Incomplete Handling of Degenerate Indexes in Earlier Patches

Prior patches (e.g., 13c8c60bb6b4447b) addressed similar assertion failures by modifying how the query planner handles indexes with constant columns. However, these fixes focused on scenarios where all columns in an index were constants. The current issue involves indexes where some columns are constants (e.g., 0,0,0,0,0||1), and the final column is a deterministic expression. The sampling logic fails to recognize that such indexes still qualify as "degenerate" and require special handling.

4. Bisect Results and Version-Specific Behavior

The bisect history indicates that the bug was introduced in a 2015 commit (2131a5ca53f0e9b0) related to the STAT4 optimization. Later versions (including the current trunk at the time of reporting) contained partial fixes but did not fully address all edge cases involving mixed constant and expression-based indexes. The assertion failure reappears when the optimizer attempts to sample indexes that blend literal constants with deterministic expressions.

Troubleshooting Steps, Solutions & Fixes: Resolving Register Conflicts in STAT4 Bytecode

Step 1: Reproduce the Issue in a Controlled Environment

Begin by replicating the failure using the exact schema and queries provided:

CREATE TABLE v0(c);
CREATE TABLE v1(c);
CREATE INDEX i ON v0(0,0,0,0,0||1);  -- Index with four constants and one expression
CREATE INDEX i0 ON v1(0<1);          -- Index with a boolean expression
INSERT INTO v0 VALUES(0);
ANALYZE;

Compile SQLite with debugging symbols and STAT4 enabled:

export CFLAGS="-g -O0 -DSQLITE_DEBUG -DSQLITE_ENABLE_STAT4"
./configure
make

Execute the script and observe the assertion failure:

sqlite3: sqlite3.c:92069: int sqlite3VdbeExec(Vdbe *): Assertion `pIn1!=pOut' failed.

Step 2: Analyze the Generated Bytecode

Enable SQLite’s bytecode dumping to inspect the VDBE program for ANALYZE:

.echo on
.explain on
ANALYZE;

Focus on opcodes related to index sampling, particularly OP_SeekEnd and OP_IfNoHope. Look for instances where the same register is used for both input and output.

Example of Faulty Bytecode:

-- For index i (0,0,0,0,0||1)
OP_SeekEnd   r1, r1   -- Input and output registers are the same (r1)

Step 3: Identify Register Allocation Conflicts

The assertion pIn1!=pOut fails because the bytecode generator assigned the same register (r1) to both operands. This occurs when the index’s leading columns are constants, causing the planner to optimize away the loop structure normally used for sampling. The generator then reuses registers, unaware that OP_SeekEnd requires distinct registers.

Step 4: Apply the Fix from Commit 6f8b97f31a4c8552

The resolution involves modifying the bytecode generator to ensure pIn1 and pOut registers are distinct for OP_SeekEnd and OP_IfNoHope opcodes. Specifically, the sqlite3ExprCodeGetColumn() function is adjusted to avoid reusing registers when handling degenerate indexes.

Code Change Summary:

• In wherecode.c, revise the register allocation logic for OP_SeekEnd to explicitly reserve a temporary register if the input and output registers collide.
• Add a check in vdbeemit.c to prevent register aliasing during the generation of OP_IfNoHope.

Step 5: Validate the Fix with the Test Case

Rebuild SQLite with the patched code and rerun the test script. The ANALYZE command should complete without triggering the assertion. Verify that the sqlite_stat4 table is populated correctly:

SELECT * FROM sqlite_stat4;

Step 6: Generalize the Fix to All Degenerate Index Scenarios

To prevent regressions, extend the register allocation checks to all code paths that generate OP_SeekEnd and OP_IfNoHope. This includes cases where:

• Indexes contain a mix of constants and expressions.
• All index columns are constants (handled by prior patches but requiring reinforcement).
• Expressions evaluate to constants deterministically (e.g., 1+1, LOWER('ABC')).

Step 7: Update Compilation Flags for Debugging

When investigating similar issues, enhance the debugging flags to include:

export CFLAGS="-g -O0 -DSQLITE_DEBUG 
  -DSQLITE_ENABLE_TREETRACE      # Enable parse tree tracing
  -DSQLITE_ENABLE_WHERETRACE     # Log query planner decisions
  -DSQLITE_ENABLE_CURSOR_HINTS   # Debug B-tree cursor operations
  -DSQLITE_COUNTOFVIEW_OPTIMIZATION 
  -DSQLITE_ENABLE_STAT4"

These flags provide granular visibility into the query planner’s decisions and register allocation patterns.

Step 8: Implement Workarounds for Unpatched Versions

If updating SQLite is not immediately feasible, apply one of these mitigations:

• Disable STAT4 optimization:

  .testctrl optimizations 0x00000800;  -- Disable STAT4
  ANALYZE;
  

• Avoid constant expression indexes: Refactor schemas to use columns instead of literals in index definitions.
• Use partial ANALYZE: Collect statistics only for specific tables/indexes not involved in the issue:

  ANALYZE v1;  -- Skip v0 and its problematic index i
  

Step 9: Monitor for Edge Cases in Query Planner Logic

After applying the fix, test these additional scenarios to ensure robustness:

1. Indexes with all-constant columns:

   CREATE INDEX i2 ON v0(1, 2, 3);
   

2. Indexes with deterministic functions:

   CREATE INDEX i3 ON v0(ABS(-5), LENGTH('fixed'));
   

3. Mixed constant and column-based indexes:

   CREATE INDEX i4 ON v0(1, c, 2);
   

Step 10: Contribute Regression Tests to SQLite’s Test Suite

To prevent future regressions, submit a test case to SQLite’s official test suite that covers constant expression indexes with STAT4. Example test:

/* test/analyze9.test */
do_execsql_test analyze9-1.0 {
  CREATE TABLE t1(a);
  CREATE INDEX t1i ON t1(0, 1, 2, 3, 4||5);
  INSERT INTO t1 VALUES(1);
  ANALYZE;
} {}

By systematically addressing register allocation conflicts in STAT4 sampling logic and rigorously testing edge cases, this issue can be fully resolved, ensuring stability for databases leveraging expression-based indexes.