Optimizing Bulk Inserts into WITHOUT ROWID Tables in SQLite

Understanding the Performance Gap Between WITHOUT ROWID and ROWID Tables

Issue Overview

The core challenge revolves around inserting ~20 million rows into a WITHOUT ROWID table with a composite primary key (a, b) at speeds comparable to a standard ROWID table. The observed performance difference is significant: 19–23 seconds for the WITHOUT ROWID table versus 5–6 seconds for the ROWID table, even when using best practices like batched transactions, prepared statements, and ordered inserts. Profiling reveals that SQLite is CPU-bound during the insertion process for both table types, ruling out disk I/O as the bottleneck.

The WITHOUT ROWID table’s structure imposes additional constraints:

CREATE TABLE data (
  a INTEGER NOT NULL,
  b INTEGER NOT NULL,
  c INTEGER,
  d INTEGER,
  PRIMARY KEY (a, b)
) WITHOUT ROWID;

This creates a clustered index where the primary key (a, b) directly determines the physical storage order of the data. Unlike ROWID tables, which append new rows sequentially (leveraging the implicit auto-incrementing rowid), WITHOUT ROWID tables require B-tree traversal for every insertion to locate the correct position for the composite key. This introduces overhead from:

1. Key Comparison: Each insertion requires comparing the (a, b) values against existing entries to enforce uniqueness and maintain order.
2. Page Splits and Rebalancing: As the B-tree grows, inserting non-sequential keys forces SQLite to split pages and rebalance the tree, increasing computational work.
3. Index Maintenance: For WITHOUT ROWID tables, the primary key is the sole index, but its structure as a clustered index complicates bulk insertion compared to a ROWID table with separate data and index storage.

The user has already tested several optimizations:

• In-Memory Databases: Reduced latency slightly but did not close the performance gap.
• Journal Disabling: Minimal impact, as the table is initially empty.
• Temporary Tables and INSERT INTO SELECT: No significant gains, suggesting SQLite does not infer pre-sorted data for optimizations.
• Post-Insert Indexing: Slower than direct insertion into the WITHOUT ROWID table, with drawbacks in storage size and read performance.

Key Factors Contributing to the Slowdown

1. Clustered Index Overhead:
   In WITHOUT ROWID tables, the primary key serves as the clustered index, dictating the physical storage layout. Inserts must navigate the B-tree to find the correct position for each (a, b) pair. Even with ordered inserts, SQLite’s B-tree implementation for composite keys lacks optimizations like append bias (used in ROWID tables to accelerate sequential writes).

2. B-Tree Insertion Mechanics:
   Each insertion triggers a call to sqlite3BtreeInsert(), which performs:

   • Key Lookup: Locating the insertion point via sqlite3BtreeMovetoUnpacked(), a process that traverses the B-tree from root to leaf.
   • Uniqueness Checks: The NoConflict opcode verifies that the (a, b) pair does not duplicate existing entries, adding computational steps.
   • Page Management: Non-sequential inserts fragment pages, requiring splits and rebalancing, which are CPU-intensive.

3. Absence of Bulk Insert Optimizations:
   SQLite’s virtual machine (VDBE) does not automatically recognize bulk insertion patterns for WITHOUT ROWID tables. While INSERT INTO SELECT can theoretically bypass per-row checks, SQLite treats this as a series of individual inserts unless the source is a virtual table with explicit ordering metadata.

4. Generated Column Limitations:
   Combining a and b into a single 64-bit integer (e.g., ab = (a << 32) | b) and using generated columns for a and b reduces insertion overhead by simplifying the primary key. However, this degrades query performance for filters on a or b individually, as the composite key ab does not preserve prefix-based seek efficiency.

5. Virtual Table Constraints:
   While custom virtual tables could bypass SQLite’s B-tree layer, they require significant implementation effort and may not integrate seamlessly with existing data export workflows. The user’s experiment with temporary in-memory tables (data2) showed no gains, as SQLite still processes each row individually during INSERT INTO SELECT.

Strategies for Mitigation and Optimization

1. Leverage Append-Optimized Insertions

• Pre-Sort Data: Ensure that the input data is strictly ordered by the (a, b) composite key. SQLite’s B-tree will minimize page splits if inserts follow the natural order of the clustered index.
• Batch Size Tuning: Experiment with smaller transactions (e.g., 50,000 rows per commit) to balance memory usage and lock contention.

2. Schema and Query Adjustments

• Pragma Tuning:

  PRAGMA cache_size = -<size_in_kb>;  -- Increase cache to reduce page faults
  PRAGMA synchronous = OFF;           -- Disable sync for in-memory databases
  PRAGMA journal_mode = OFF;          -- Disable journaling if data is disposable
  

• Synthetic Key Optimization:
  Combine a and b into a single 64-bit integer ab as the primary key, with a and b as generated columns. This reduces insertion overhead but requires query adjustments:

  CREATE TABLE data (
    ab INTEGER NOT NULL PRIMARY KEY,
    c INTEGER,
    d INTEGER,
    a INTEGER GENERATED ALWAYS AS (ab >> 32),
    b INTEGER GENERATED ALWAYS AS (ab & 0xFFFFFFFF)
  ) WITHOUT ROWID;
  

  Trade-off: Queries filtering on a alone lose efficiency, as the ab key does not preserve prefix ordering for a.

3. Code-Level Modifications

• SQLite Custom Builds:
  Modify the B-tree insertion logic to include an append bias for ordered inserts in WITHOUT ROWID tables. This involves adjusting the sqlite3BtreeInsert() function to use BTREE_SAVEPOSITION or similar flags when the insertion order matches the key order.
• Virtual Table Integration:
  Implement a custom virtual table that exposes pre-sorted data to SQLite, allowing INSERT INTO SELECT to bypass per-row uniqueness checks. This requires:
  • Overriding the xBestIndex method to report the natural order of (a, b).
  • Implementing xFilter to stream data in the correct order.

4. Alternative Storage Formats

• Hybrid Rowid/Without Rowid Workflow:
  1. Insert data into a temporary ROWID table without constraints.
  2. Create the WITHOUT ROWID table with PRAGMA ignore_check_constraints = ON.
  3. Use INSERT INTO data SELECT a, b, c, d FROM temp ORDER BY a, b; to leverage bulk sorting before insertion.

5. Profiling and Low-Level Optimizations

• VDBE Opcode Analysis:
  Use EXPLAIN to inspect the virtual machine instructions generated for inserts. Optimize hot paths like NoConflict and IdxInsert by reducing redundant comparisons.
• SQLite Configuration Flags:
  Recompile SQLite with -DSQLITE_ENABLE_STAT4 to improve query planner decisions or -DSQLITE_DIRECT_OVERFLOW_READ to accelerate overflow page access.

6. Workflow Re-Engineering

• Precompute and Serialize:
  Generate the entire dataset as a SQLite database file in a custom format (e.g., CSV or binary blobs), then use the sqlite3_blob API for direct block-level writes. This bypasses SQLite’s insertion logic entirely but requires deep expertise in the database file format.
• Parallel Inserts:
  Partition the data by a or b ranges and perform concurrent inserts into separate databases, merging them afterward with ATTACH DATABASE and INSERT INTO.

Conclusion

The performance disparity between WITHOUT ROWID and ROWID tables during bulk inserts stems from fundamental differences in their storage architectures. While ROWID tables benefit from append-optimized writes, WITHOUT ROWID tables incur overhead from clustered index maintenance. Mitigating this requires a combination of schema adjustments, query optimizations, and low-level SQLite modifications. For most users, pre-sorting data and leveraging synthetic keys offer the best balance between insertion speed and query flexibility. Advanced scenarios may warrant custom virtual tables or even patching SQLite’s B-tree implementation to recognize ordered insertion patterns.