Optimizing SQLite Table Performance by Reducing Fragmentation and Page Scattering

Understanding Table Fragmentation and Scattered Page Allocation in SQLite

Issue Overview: Table Fragmentation, Page Underutilization, and Non-Sequential Page Access

The core issue revolves around degraded query performance on a heavily updated SQLite table ("A") compared to a periodically rebuilt table ("B"). The problem manifests as slower query execution times (3–4x slower) for table A within the original database, even though table A has fewer columns and a simpler schema. Exporting table A to a new database resolves the performance gap, suggesting that fragmentation and page scattering are critical factors.

Key Observations:

1. Fragmentation Metrics: The sqlite3_analyzer report reveals that table A has 50% unused space per page, while table B uses 99.7% of its page space efficiently. This indicates severe page underutilization in table A due to frequent updates causing row-size variability.
2. Non-Sequential Page Allocation: After rebuilding table A (via temporary table recreation), unused space is reduced, but 62.3% of pages remain non-sequential. This forces SQLite to perform scattered I/O operations during full scans or index traversals, even on SSDs.
3. Index Fragmentation: Table A’s secondary index (idxA) may also suffer from fragmentation, as rebuilding the table alone does not optimize index structures. Queries leveraging this index inherit its inefficiencies.
4. Query Performance Discrepancy: Full-table scans on table A in the original database take 6 seconds vs. 400ms in an exported database. This disparity highlights the impact of page scattering on I/O-bound operations.

Underlying Mechanisms:

• SQLite Storage Model: SQLite stores tables and indexes as B-trees. Each table is a B-tree where rows are stored in rowid order (or primary key order for WITHOUT ROWID tables). Frequent updates can fragment this structure by creating gaps in pages or forcing row migrations to overflow pages.
• Autovacuum Limitations: SQLite’s autovacuum reclaims free pages but does not reorder pages or compact data. It primarily prevents file bloat by truncating unused space at the end of the file.
• Page Reuse Behavior: When rows are deleted and reinserted, SQLite reuses free pages from the freelist, which may be scattered across the file. This perpetuates non-sequential page allocation.

Root Causes: Update Patterns, Schema Design, and Storage Configuration

1. Update-Induced Page Fragmentation
   Table A’s integer value field undergoes frequent updates with values spanning a wide range (8-bit to 64-bit integers). SQLite’s variable-length integer encoding (varint) causes row sizes to fluctuate. Updating a small integer to a larger one forces the row to occupy more space, potentially splitting it across pages or leaving gaps in the original page. Over time, this creates underfilled pages and increases the total page count.

2. Secondary Index Fragmentation
   The non-unique index on table A’s integer value column (idxA) becomes fragmented as updates alter the indexed values. Index entries are stored in sorted order, so frequent changes disrupt the logical clustering of data, leading to increased tree traversal depth and I/O operations.

3. Inefficient Page Reuse During Rebuilds
   Rebuilding table A via DELETE and INSERT (without dropping the table) reuses existing free pages from the freelist. These pages are often scattered, resulting in non-sequential allocation. The VACUUM command is required to rebuild the entire database with contiguous pages, but it’s not table-specific.

4. Suboptimal Page Size Configuration
   Using the default 4 KB page size on a large database (350 GB) may exacerbate fragmentation. Larger pages (e.g., 8 KB or 16 KB) can store more rows per page, reducing the number of pages accessed during scans. However, increasing page size requires careful testing, as it affects all tables and indexes.

5. Insufficient Schema Optimization
   While WITHOUT ROWID was suggested, it’s not ideal for tables with an integer primary key. SQLite optimizes rowid-based tables for such cases, and using WITHOUT ROWID could negate these optimizations, leading to slower inserts/updates without guaranteed read benefits.

Resolving Fragmentation: Targeted Rebuilding, Page Reordering, and Schema Tweaks

1. Defragmenting Table A via Isolation and Targeted VACUUM
Step 1: Move Table A to a Separate Database File

• Create a new database file (A.db) and attach it to the main database:

  ATTACH DATABASE 'A.db' AS aux;
  

• Copy table A to the new database:

  CREATE TABLE aux.A AS SELECT * FROM main.A;
  

• Rebuild indexes in the new database to ensure they’re optimized:

  REINDEX aux.A;
  

• Detach and vacuum the isolated database:

  DETACH DATABASE aux;
  VACUUM 'A.db';
  

This isolates the vacuum operation to table A, avoiding the 350 GB main database rebuild.

Step 2: Use Incremental VACUUM
Enable incremental vacuuming to reclaim free pages periodically without full compaction:

PRAGMA auto_vacuum = INCREMENTAL;

Execute incremental vacuum after heavy update cycles:

PRAGMA incremental_vacuum(N);

Replace N with the number of free pages to reclaim.

2. Forced Page Reordering via Full Rebuild
Step 1: Drop and Recreate Table A with Ordered Inserts

• Use ORDER BY during the rebuild to enforce primary key order, improving page locality:

  CREATE TABLE new_A AS SELECT * FROM A ORDER BY id;
  DROP TABLE A;
  ALTER TABLE new_A RENAME TO A;
  

• Rebuild indexes with sorted input to optimize B-tree structure:

  CREATE INDEX idxA_temp ON A(oc);
  DROP INDEX idxA;
  ALTER INDEX idxA_temp RENAME TO idxA;
  

Step 2: Leverage SQLite’s Backup API
Use sqlite3_backup_init to create a compacted copy of table A. This method bypasses freelist page reuse:

sqlite3 *src, *dst;
sqlite3_open("main.db", &src);
sqlite3_open("A_compacted.db", &dst);
sqlite3_backup *b = sqlite3_backup_init(dst, "main", src, "A");
sqlite3_backup_step(b, -1);
sqlite3_backup_finish(b);

3. Schema and Configuration Adjustments
Step 1: Increase Page Size
Test larger page sizes (e.g., 8 KB) to improve storage density:

PRAGMA page_size = 8192;
VACUUM;

Note: Page size must be set before creating the database. For existing databases, use the VACUUM INTO command:

PRAGMA page_size = 8192;
VACUUM INTO 'new_db.db';

Step 2: Optimize Data Types
Use fixed-size integers (INTEGER in SQLite is variable-length). If values are consistently large, consider dummy columns to pad rows to a fixed size, reducing update-induced size changes:

CREATE TABLE A (
  id INTEGER PRIMARY KEY,
  oc INTEGER,
  pad BLOB -- Stores 4-byte padding to stabilize row size
);

4. Monitoring and Maintenance

• Track Page Fragmentation: Regularly run sqlite3_analyzer to monitor unused bytes and non-sequential pages.
• Schedule Off-Peak Rebuilds: Use cron jobs or triggers to rebuild table A during low-usage periods.
• Enable PRAGMA secure_delete = OFF: Prevents zeroing of deleted data, speeding up rebuilds.

5. Advanced Techniques

• SQLite File Control Operations: Use SQLITE_FCNTL_CKPT_START to trigger a checkpoint, forcing the database to defragment in the background.
• Custom Vacuum Scripts: Implement a script that rebuilds table A and its indexes in a new database, swaps the files, and updates foreign keys.

By addressing both page fill efficiency and allocation order, these steps restore query performance to levels seen in exported databases. Regular maintenance and schema adjustments ensure long-term stability.