Rowid Table Performance: Index Efficiency vs. Primary Key Scans in SQLite

---

Rowid Table Structure, B-Tree Page Utilization, and Query Optimization

Issue Overview: Primary Key Scan Performance Degradation with Large Row Sizes

The core issue revolves around unexpected performance degradation when querying the id column (aliased to the SQLite ROWID) in a rowid table containing large BLOB values. A simple SELECT id FROM Test query executes 25x slower without an explicit index on id, despite the id column being the INTEGER PRIMARY KEY (and thus mapped to the ROWID). This contradicts expectations derived from SQLite documentation, which states that rowid-based operations are inherently fast. The performance disparity arises from the interaction between the physical storage layout of rowid tables and the query execution strategy chosen by SQLite.

Key observations:

1. Without an index on id, the query planner performs a full table scan (SCAN TABLE Test), which becomes slower as the BLOB size increases.
2. With a covering index on id, the query planner uses the index (SCAN TABLE Test USING COVERING INDEX test_id), resulting in consistent, fast execution regardless of BLOB size.
3. The documentation emphasizes the efficiency of rowid-based operations, but this scenario reveals nuances in how SQLite’s B-tree storage mechanics interact with large rows.

The confusion stems from two factors:

• The physical storage structure of rowid tables (B*-Trees) versus secondary indexes.
• The query planner’s decision-making process when choosing between scanning the main table or a covering index.

---

Possible Causes: B-Tree Page Saturation, Overflow Pages, and Query Planner Heuristics

1. B-Tree Page Utilization in Rowid Tables

Rowid tables store all column data (including large BLOBs) in a single B*-Tree structure, where the ROWID serves as the key. Each leaf node in this B*-Tree contains entire rows, including all columns. When rows are large (e.g., 1KB BLOBs), fewer rows fit per 4KB database page. For example:

• A row with id (8 bytes), x (8 bytes), and y (1024 bytes) occupies ~1040 bytes.
• Only 3 rows fit per 4KB page (3 × 1040 ≈ 3120 bytes), leaving unused space.
• This forces SQLite to read many more pages to retrieve all id values during a full table scan.

By contrast, a secondary index on id stores only the id values in its B-Tree. Each index entry is ~12 bytes (8 bytes for id + 4 bytes for rowid overhead), allowing ~341 entries per 4KB page. Scanning the index requires reading ~293x fewer pages than scanning the main table (100,000 rows / 341 ≈ 293 pages vs. 100,000 / 3 ≈ 33,334 pages).

2. Overflow Pages and I/O Amplification

BLOBs larger than a threshold (default: ~1KB) are stored in overflow pages, which are separate from the main B*-Tree. Accessing these requires additional I/O operations. While the id column itself isn’t stored in overflow pages, the presence of large BLOBs in the same row forces the main B*-Tree to:

• Store a pointer to the overflow page in the leaf node.
• Fragment the storage of the row across multiple pages, increasing disk seeks.

Even though the query SELECT id FROM Test doesn’t access the BLOB, the table scan must still traverse all leaf nodes of the main B*-Tree, which are sparsely populated due to the large row size.

3. Query Planner Optimization Boundaries

SQLite’s query planner prioritizes minimizing disk I/O. When no index exists, it has no choice but to scan the main table. However, when a covering index is available:

• The index B-Tree contains all data required by the query (id in this case).
• Scanning the index avoids touching the main table’s B*-Tree entirely.

The planner does not inherently recognize that the ROWID (or its alias, id) is the primary key of the main table. It treats the index as a separate, faster access path.

---

Troubleshooting Steps, Solutions & Fixes: Storage Optimization, Indexing Strategies, and Documentation Clarifications

1. Diagnosing Page Utilization and Query Plans

Step 1: Analyze B-Tree Page Efficiency
Use the sqlite3_analyzer tool or run queries to calculate page utilization:

-- Calculate average rows per page in main table
SELECT (COUNT(*) * 1040) / (page_count * 4096) AS rows_per_page
FROM Test, pragma_page_count('Test');

If the result is low (e.g., ≤3 rows/page), the main table is sparse due to large rows.

Step 2: Check for Overflow Pages
Query the sqlite_stat1 table or use:

SELECT count(*) FROM Test WHERE length(y) > 1024;

If overflow pages are used, consider increasing the SQLITE_MAX_PAGE_SIZE or reducing BLOB size.

Step 3: Review EXPLAIN QUERY PLAN Output
Always validate the execution plan:

EXPLAIN QUERY PLAN SELECT id FROM Test;

Ensure the planner uses the index when optimal.

2. Indexing Strategies for Rowid Tables

Solution 1: Create Covering Indexes for Projection-Only Queries
If queries frequently select only the primary key (id), create a covering index:

CREATE INDEX test_id ON Test(id);

This allows the query planner to bypass the main table.

Solution 2: Avoid Indexes for Queries Accessing Other Columns
For queries involving x or y, the main table must be scanned. In such cases, ensure the index is not used unnecessarily:

-- Force table scan (rarely needed, but useful for testing)
SELECT id FROM Test NOT INDEXED;

Solution 3: Use WITHOUT ROWID for Wide Tables with Frequent Full Scans
If the table has many columns and frequent full scans are required, consider a WITHOUT ROWID table:

CREATE TABLE Test (
  id INTEGER PRIMARY KEY,
  x INTEGER,
  y BLOB
) WITHOUT ROWID;

This stores all columns in a B-Tree keyed by the primary key, improving scan performance for wide rows.

3. Documentation Clarifications and Best Practices

Clarification 1: Rowid Tables vs. Covering Indexes
The documentation’s claim that "retrieving or sorting records by rowid is fast" refers to point lookups (e.g., WHERE id = ?), not full scans. Full scans of the main table’s B*-Tree suffer when rows are large.

Clarification 2: Indexing the INTEGER PRIMARY KEY
While the ROWID is intrinsically indexed, creating an explicit index on it provides a covering index for queries projecting only the ROWID. This is faster because the index B-Tree is smaller and denser.

Best Practice: Profile Queries with Realistic Data Sizes
Always test performance with representative row sizes. Large BLOBs or TEXT fields drastically alter page utilization and query plans.

---

By understanding the interplay between row size, B-tree page efficiency, and query planner behavior, developers can make informed decisions about indexing and schema design in SQLite. The key takeaway is that while rowid tables are optimized for rowid-based lookups, full scans of large-row tables benefit significantly from covering indexes.