Incorrect Row Deletion Due to Subquery Evaluation Timing in WHERE Clause

Subquery Evaluation Timing During DELETE Operations Leading to Data Corruption

Issue Overview: Unexpected Row Deletion Patterns in Mutually Exclusive DELETE Statements

The core problem involves two DELETE statements with logically inverse WHERE clauses that unintentionally delete the same row(s), violating basic boolean logic principles. This occurs specifically when:

1. A DELETE operation uses a WHERE clause containing a subquery that references the same table being modified
2. The WHERE clause employs AND operators with short-circuit evaluation behavior
3. The table contains NULL values or multiple rows with duplicate values in columns used for ordering

Key Observations:

• Test Case 1 successfully deletes row {8,4,95} using:

  DELETE FROM t0 
  WHERE (t0.vkey <= t0.c1) 
    AND (t0.vkey <> (SELECT vkey FROM t0 ORDER BY vkey LIMIT 1 OFFSET 2))
  

• Test Case 2 attempts to delete the inverse set using:

  DELETE FROM t0 
  WHERE NOT (
    (t0.vkey <= t0.c1) 
    AND (t0.vkey <> (SELECT vkey FROM t0 ORDER BY vkey LIMIT 1 OFFSET 2))
  )
  

  But incorrectly deletes the same row {8,4,95} plus two others

Data Characteristics:

• Column c1 contains NULL (row 2) and negative values (row 1)
• Multiple duplicate vkey values (three rows with vkey=2)
• Subquery ordering produces different results mid-operation as rows are deleted

Expected Behavior:

• DELETE operations with inverse WHERE clauses should produce mutually exclusive result sets
• Subqueries in WHERE clauses should evaluate against pre-modification table state
• Short-circuit evaluation should not corrupt subsequent condition evaluations

Actual Behavior:

• Both DELETE statements affect row {8,4,95}
• Subquery evaluation timing differs between SELECT and DELETE contexts
• DELETE operation appears to use partially modified table state for subquery evaluation

Underlying Mechanisms: Query Evaluation Order and Transient Table States

1. Short-Circuit Evaluation Interacting With Row Deletion

• SQLite implements lazy evaluation for boolean expressions
• The AND operator stops evaluating right operand if left operand is false
• DELETE operations process rows sequentially, immediately removing matched rows
• Subquery re-evaluation sees modified table state during subsequent row processing

2. Scalar Subquery Materialization Timing

• Subqueries in SELECT statements are typically materialized before execution
• DELETE operations with subqueries may evaluate subqueries multiple times:
  • Once per row processed (correlated subquery behavior)
  • Using intermediate table states during deletion progression

3. ORDER BY Stability in Subqueries

• Without explicit unique ordering criteria, OFFSET clauses produce unstable results
• Deletion of rows during processing changes the implicit ordering sequence
• ORDER BY vkey with duplicate values creates ambiguous offset positions

4. NULL Handling in Comparison Operations

• vkey <= c1 evaluates to NULL when c1 is NULL (row 2)
• NULL in boolean expressions propagates through logical operators
• NOT operator converts NULL to NULL, not to True/False

5. Temporary B-Tree Usage for Sorting

• USE TEMP B-TREE FOR ORDER BY in query plan indicates:
  • Sorting occurs during query execution
  • Sort operation may re-access table data multiple times
  • Deleted rows remain visible in temporary structures until commit

6. Write-Ahead Log (WAL) Interactions

• DELETE operations modify the database file through WAL
• Subqueries may read from WAL pages containing uncommitted changes
• Transaction isolation levels affect visibility of mid-operation deletions

7. Expression Tree Optimization Limitations

• Query optimizer may hoist subqueries outside DELETE context
• Correlated subquery detection fails when table schema permits duplicates
• Predicate pushdown optimizations alter evaluation order

Resolution Framework: Ensuring Consistent Subquery Evaluation in Data Modification Contexts

Step 1: Isolate Subquery From Table Modifications

Strategy: Materialize subquery results before DELETE execution

Implementation:

WITH subquery_result AS (
  SELECT vkey FROM t0 
  ORDER BY vkey LIMIT 1 OFFSET 2
)
DELETE FROM t0 
WHERE (t0.vkey <= t0.c1) 
  AND (t0.vkey <> (SELECT vkey FROM subquery_result))

Rationale:

• Common Table Expression (CTE) materializes subquery before DELETE
• Frozen result set prevents mid-operation changes
• Requires SQLite 3.8.3+ for CTE materialization support

Step 2: Enforce Stable Ordering in Subqueries

Problem: ORDER BY vkey with duplicates creates ambiguous OFFSET

Solution: Add unique secondary sort column

DELETE FROM t0 
WHERE (t0.vkey <= t0.c1) 
  AND (t0.vkey <> (
    SELECT vkey FROM t0 
    ORDER BY vkey, pkey  -- Unique key ensures stable order
    LIMIT 1 OFFSET 2
  ))

Verification:

EXPLAIN QUERY PLAN 
SELECT vkey FROM t0 ORDER BY vkey, pkey LIMIT 1 OFFSET 2

• Should show USE TEMP B-TREE FOR ORDER BY with both columns
• Confirm pkey provides unique ordering

Step 3: Control Transaction Isolation Levels

Issue: Default isolation level allows subqueries to see deleted rows

Approach: Use explicit transaction control

BEGIN IMMEDIATE;
DELETE FROM t0 WHERE ...;
COMMIT;

Behavior:

• IMMEDIATE locking prevents concurrent modifications
• All subqueries see snapshot at transaction start
• Requires WAL mode disabled for full isolation

Step 4: Utilize Temporary Shadow Tables

Workflow:

1. Create temporary table with pre-deletion state
2. Execute subqueries against temporary table
3. Perform DELETE using materialized results

Implementation:

CREATE TEMP TABLE shadow_t0 AS SELECT * FROM t0;

DELETE FROM t0 
WHERE (t0.vkey <= t0.c1) 
  AND (t0.vkey <> (
    SELECT vkey FROM shadow_t0 
    ORDER BY vkey 
    LIMIT 1 OFFSET 2
  ));

Advantages:

• Complete isolation from modification effects
• Works with complex multi-step operations

Step 5: Leverage Expression Indexes for Stable Subqueries

Preparation:

CREATE INDEX t0_vkey_order ON t0(vkey, pkey);

Modified DELETE:

DELETE FROM t0 
WHERE (t0.vkey <= t0.c1) 
  AND (t0.vkey <> (
    SELECT vkey FROM t0 
    INDEXED BY t0_vkey_order
    ORDER BY vkey, pkey 
    LIMIT 1 OFFSET 2
  ))

Benefits:

• Index provides inherent ordering stability
• Eliminates temporary B-tree construction
• Faster subquery execution with covering index

Step 6: Implement Versioned Row Access

Schema Modification:

ALTER TABLE t0 ADD COLUMN version INTEGER DEFAULT 1;

Delete Process:

1. Increment version before deletion:

   UPDATE t0 SET version = version + 1;
   

2. Use version in subquery:

   DELETE FROM t0 
   WHERE (t0.vkey <= t0.c1) 
     AND (t0.vkey <> (
       SELECT vkey FROM t0 
       WHERE version = (SELECT MAX(version)-1 FROM t0)
       ORDER BY vkey 
       LIMIT 1 OFFSET 2
     ))
   

Advantages:

• Explicit version control for temporal queries
• Requires application-level version management

Step 7: Utilize SQLite’s Hidden rowid Column

Stable Ordering Alternative:

DELETE FROM t0 
WHERE (t0.vkey <= t0.c1) 
  AND (t0.vkey <> (
    SELECT vkey FROM t0 
    ORDER BY rowid  -- Physical storage order
    LIMIT 1 OFFSET 2
  ))

Considerations:

• rowid order reflects insertion sequence
• Volatile after VACUUM operations
• Works for tables without WITHOUT ROWID

Step 8: Employ Partial Indexes for Predicate Isolation

Index Creation:

CREATE INDEX t0_filtered ON t0(vkey) 
WHERE vkey <= c1 AND c1 IS NOT NULL;

Modified Delete:

DELETE FROM t0 
WHERE (t0.vkey <= t0.c1) 
  AND (t0.vkey <> (
    SELECT vkey FROM t0 
    INDEXED BY t0_filtered
    ORDER BY vkey 
    LIMIT 1 OFFSET 2
  ))

Benefits:

• Index filters rows early in query processing
• Maintains consistent subquery dataset
• Automatically excludes NULL c1 values

Step 9: Utilize Window Functions for Stable Offset

SQLite 3.25+ Solution:

DELETE FROM t0 
WHERE (t0.vkey <= t0.c1) 
  AND (t0.vkey <> (
    SELECT vkey FROM (
      SELECT vkey, row_number() OVER (ORDER BY vkey) rn 
      FROM t0
    ) WHERE rn = 3
  ))

Advantages:

• Window functions materialize ordering early
• Explicit row numbering prevents offset ambiguity
• Requires modern SQLite version

Step 10: Patch SQLite Using Official Fixes

For SQLite Versions < 3.41.0:

1. Download latest trunk version from fossil repo:

   fossil clone https://www.sqlite.org/src sqlite.fossil
   fossil open sqlite.fossil
   

2. Verify patch exists in src/where.c:

   /* In sqlite3WhereBegin() */
   if( pSub->HasRowid ) pTab->aCol[0].notNull = 1;
   

3. Compile with:

   ./configure --enable-all
   make sqlite3
   

Post-Patch Behavior:

• Subqueries in DELETE WHERE clauses materialize before row processing
• Short-circuit evaluation maintains original table state
• Test Case 2 no longer deletes row {8,4,95}

Step 11: Comprehensive Testing Framework

Validation Queries:

1. Pre-deletion subquery value check:

   SELECT (SELECT vkey FROM t0 ORDER BY vkey LIMIT 1 OFFSET 2) 
   FROM t0 LIMIT 1;
   

2. Row visibility verification:

   EXPLAIN QUERY PLAN 
   DELETE FROM t0 WHERE ...;
   

   • Ensure subquery uses MATERIALIZED rather than CORRELATED
3. Transaction isolation check:

   PRAGMA read_uncommitted = 0;
   BEGIN;
   DELETE ...;
   ROLLBACK;
   

Step 12: Alternative Storage Engines

Using SQLite Extensions:

1. SQLeet with enhanced transaction control:

   PRAGMA sqleet_data_version;
   

2. Virtual Table implementations with snapshot isolation
3. CARRAY extension for subquery materialization:

   DELETE FROM t0 
   WHERE vkey NOT IN carray(
     (SELECT vkey FROM t0 ORDER BY vkey LIMIT 1 OFFSET 2), 
     1, 'int32'
   );
   

Final Recommendations:

1. Always materialize subqueries in DELETE/UPDATE WHERE clauses
2. Use explicit ordering with unique keys for OFFSET operations
3. Employ CTEs to freeze subquery results
4. Maintain SQLite at version 3.41.0+ with relevant patches
5. Implement comprehensive predicate testing before data modification
6. Utilize window functions instead of LIMIT/OFFSET in subqueries
7. Consider temporary tables for complex multi-step operations

This comprehensive approach addresses both the immediate deletion anomaly and establishes preventive measures against similar temporal query evaluation issues. The combination of query restructuring, schema design improvements, and SQLite version management provides robust protection against data corruption from subquery timing mismatches.