Row Reappearance During Synchronization in SQLite Tables With and Without ROWID

Issue Overview: Row Reappearance During Ordered Traversal After Updates in WITHOUT ROWID Tables

The core challenge arises when implementing a synchronization algorithm that iterates over rows in a specific order, compares them to an external data source (e.g., a sorted vector of key-value pairs), and updates mismatched values. This process works as expected in tables that use implicit ROWID identifiers but fails when applied to WITHOUT ROWID tables. Specifically, after updating a row in a WITHOUT ROWID table, the same row reappears in subsequent iterations of the query, breaking synchronization logic.

This discrepancy stems from fundamental differences in how SQLite organizes data in ROWID versus WITHOUT ROWID tables and how queries interact with these structures during cursor-based traversal. The issue is not caused by incorrect application logic but by the database engine’s behavior when rows are modified during iteration. Understanding this requires a deep dive into SQLite’s storage model, query execution plans, and isolation guarantees.

Key Observations

1. ROWID Tables:

   • Use an implicit 64-bit integer primary key (ROWID) for row storage.
   • Data is stored in a B-tree structure ordered by ROWID.
   • Updates to non-ROWID columns do not alter a row’s physical position in the B-tree.

2. WITHOUT ROWID Tables:

   • Use an explicit primary key as the clustered index.
   • Data is stored in a B-tree ordered by the primary key.
   • Updates to non-primary-key columns may still affect cursor positioning during traversal.

3. Query Stability:

   • SQLite provides limited guarantees about cursor stability during concurrent modifications.
   • The isolation documentation explicitly warns that updating rows ahead of the cursor may cause rows to reappear.

Critical Factors Influencing Behavior

• Query Plan Materialization: Whether the query optimizer uses a temporary B-tree to materialize results upfront.
• Clustered Index Structure: How the physical storage order interacts with cursor navigation.
• Update Propagation: How changes to rows affect in-progress queries depending on indexing and storage details.

Possible Causes: Clustered Index Traversal and Query Plan Differences

1. Cursor Positioning in Clustered Indexes

In WITHOUT ROWID tables, the primary key defines the physical storage order. When iterating through rows using a cursor, the database engine navigates the clustered index B-tree. If a row is updated during traversal—even if its primary key remains unchanged—the act of modifying the row’s data can alter the B-tree’s internal structure. This includes page splits, row relocations due to size changes, or index reorganizations. These low-level changes may cause the cursor to "loop back" and encounter the same row again, especially if the query does not materialize the result set upfront.

2. Absence of Temporary B-Tree Materialization

Queries that include an ORDER BY clause matching the natural order of the underlying table (ROWID or primary key) may avoid materializing results in a temporary B-tree. For example:

SELECT * FROM without_rowid_table ORDER BY primary_key_column;

In WITHOUT ROWID tables, this query leverages the clustered index directly without creating a temporary copy. By contrast, a query that requires sorting (e.g., ORDER BY non_indexed_column) forces SQLite to build a temporary B-tree. When results are materialized, updates to the underlying table do not affect the cursor, as it operates on the temporary copy. Without materialization, the cursor interacts with the live B-tree, making it susceptible to mid-traversal modifications.

3. Isolation and Undefined Behavior in Mid-Traversal Updates

SQLite’s documentation explicitly states that updating rows ahead of the cursor may lead to undefined behavior, including rows reappearing or disappearing. In ROWID tables, updates to non-ROWID columns do not alter the row’s position in the storage B-tree. However, in WITHOUT ROWID tables, even non-primary-key updates can indirectly affect cursor stability due to the clustered index’s sensitivity to row size and fragmentation.

Troubleshooting Steps, Solutions & Fixes: Ensuring Stable Iteration Across Table Types

1. Force Materialization of Query Results

Modify the query to force SQLite to materialize the entire result set before iteration. This decouples the cursor from the live table structure, preventing mid-traversal updates from affecting the result order.

Technique 1: Add a Redundant ORDER BY Clause

If the query already includes an ORDER BY clause matching the primary key, introduce a no-op expression to trick the optimizer into materializing results:

SELECT * FROM without_rowid_table ORDER BY primary_key_column || '';

The || '' forces SQLite to treat the sort as non-trivial, prompting it to use a temporary B-tree.

Technique 2: Use a Subquery with LIMIT

Wrap the original query in a subquery with LIMIT -1 OFFSET 0, which disables some optimizations:

SELECT * FROM (SELECT * FROM without_rowid_table ORDER BY primary_key_column) LIMIT -1 OFFSET 0;

Technique 3: Enable Debugging Modes (For Testing Only)

Use PRAGMA vdbe_debug=1; to inspect the query plan and verify whether a temporary B-tree is used. This is not suitable for production but helps diagnose materialization issues.

2. Defer Updates Until After Traversal

Collect all required updates during the initial traversal and apply them afterward. This avoids modifying the table while the cursor is active.

Implementation Steps:

1. Iterate and Identify Changes: Traverse the table and record primary keys and new values in memory or a temporary table.
2. Batch Apply Updates: After completing the iteration, execute UPDATE statements for each modified row.

Example Using a Temporary Table:

-- Create temporary table for updates
CREATE TEMP TABLE sync_changes (pk INTEGER PRIMARY KEY, new_value TEXT);

-- Populate with changes during iteration
INSERT INTO sync_changes VALUES (...);

-- Apply updates
UPDATE without_rowid_table
SET value_column = (SELECT new_value FROM sync_changes WHERE pk = primary_key_column)
WHERE EXISTS (SELECT 1 FROM sync_changes WHERE pk = primary_key_column);

3. Use Transactional Isolation to Freeze the Snapshot

Wrap the entire synchronization process in a SERIALIZABLE transaction to ensure a consistent snapshot. Note that SQLite’s default isolation level (DEFERRED) allows other writes to occur, which can still interfere with cursor stability.

Example:

BEGIN IMMEDIATE;
-- Perform iteration and updates here
COMMIT;

Caveats:

• This works only if no concurrent writes occur.
• Long-running transactions may lead to database lock contention.

4. Normalize Table Schemas to Use ROWID

If the synchronization algorithm’s performance is critical and the workarounds add unacceptable overhead, consider converting WITHOUT ROWID tables to use ROWID. This is a schema design trade-off and should be evaluated against query performance requirements.

Conversion Example:

-- Original schema
CREATE TABLE original (
    pk1 INTEGER,
    pk2 INTEGER,
    data TEXT,
    PRIMARY KEY (pk1, pk2)
) WITHOUT ROWID;

-- Convert to ROWID table
CREATE TABLE converted (
    pk1 INTEGER,
    pk2 INTEGER,
    data TEXT,
    PRIMARY KEY (pk1, pk2)
);

-- Copy data
INSERT INTO converted SELECT * FROM original;
DROP TABLE original;
ALTER TABLE converted RENAME TO original;

5. Use Indexed Views for Stable Ordering

Create an indexed view (via a temporary table) that mirrors the original table’s data but includes a stable ordering key. This is useful when materialization cannot be forced through query modifications.

Example:

-- Create a temporary table with a stable ordering key
CREATE TEMP TABLE sync_snapshot AS
SELECT *, 0 AS stable_order FROM without_rowid_table ORDER BY primary_key_column;

-- Iterate over the snapshot and collect changes
-- Apply changes to the original table afterward

6. Profile and Optimize Query Plans

Use EXPLAIN and EXPLAIN QUERY PLAN to analyze how SQLite executes the query. Look for differences in USING TEMP B-TREE directives between ROWID and WITHOUT ROWID table queries.

Diagnostic Commands:

EXPLAIN QUERY PLAN
SELECT * FROM without_rowid_table ORDER BY primary_key_column;

Interpreting Output:

• USE TEMP B-TREE FOR ORDER BY indicates materialization.
• SCAN TABLE without_rowid_table suggests direct traversal without materialization.

7. Adjust Synchronization Algorithm Logic

Modify the algorithm to handle row reappearance gracefully. For example:

• Skip rows that have already been processed by tracking primary keys in a hash set.
• Use a two-pass approach: first collect discrepancies, then resolve them.

Pseudocode:

processed = set()
cursor.execute("SELECT primary_key, value FROM table ORDER BY primary_key")
for row in cursor:
    if row.primary_key in processed:
        continue
    processed.add(row.primary_key)
    # Compare and schedule updates

Final Recommendations

1. Default to Materialization: Force temporary B-tree usage in queries targeting WITHOUT ROWID tables.
2. Benchmark Alternatives: Compare the performance of deferred updates versus query plan modifications.
3. Schema Audit: Evaluate whether WITHOUT ROWID is necessary for affected tables, as ROWID tables offer more predictable cursor behavior during updates.

By addressing the interplay between SQLite’s storage engine, query optimization, and application-level synchronization logic, developers can achieve consistent behavior across both ROWID and WITHOUT ROWID tables.