[{"_1":2,"_101":-5,"_102":-5},"loaderData",{"_3":4,"_30":31,"_72":73,"_100":-5},"routes/_main",{"_5":6},"socialMedia",[7,12,15,18,21,24,27],{"_8":9,"_10":11},"link","mailto:cedar.onyxes0q@icloud.com","icon","mail",{"_8":13,"_10":14},"https://github.com/sjdonado","github",{"_8":16,"_10":17},"rss.xml","rss",{"_8":19,"_10":20},"https://linkedin.com/in/sjdonado","linkedin",{"_8":22,"_10":23},"https://slides.com/sjdonado","presentation",{"_8":25,"_10":26},"https://stackoverflow.com/users/8108856/juan-rodriguez","layers",{"_8":28,"_10":29},"https://vsco.co/sjdonado/gallery","camera","routes/_main.posts",{"_32":33},"tags",[34,39,42,45,48,51,54,57,60,63,66,69],{"_35":36,"_37":38},"id",18,"name","ai",{"_35":40,"_37":41},29,"backend",{"_35":43,"_37":44},31,"bun",{"_35":46,"_37":47},30,"cloud",{"_35":49,"_37":50},25,"databases",{"_35":52,"_37":53},33,"frontend",{"_35":55,"_37":56},6,"life",{"_35":58,"_37":59},13,"performance",{"_35":61,"_37":62},32,"remix",{"_35":64,"_37":65},24,"self-hosted",{"_35":67,"_37":68},15,"sqlite",{"_35":70,"_37":71},14,"tooling","routes/_main.posts._index",{"_74":75,"_99":68},"posts",[76,90],{"_35":77,"_78":79,"_80":81,"_82":83,"_8":84,"_32":85,"_86":87},128,"title","The Covering Index Paradox","date","4/10/2025","description","SQLite index performance gap explained by B-tree height difference.","/posts/the-covering-index-paradox",[50,59,68],"content",{"_88":89},"rendered","\n

While recently tuning Bit’s performance, I encountered a bottleneck in one highly-selective query SELECT id, url FROM links WHERE slug = (?) LIMIT 1. Initial optimizations, such as replacing UUIDs with rowid and reducing the size of the slug column, significantly improved throughput. However, when I tested a covering index on (slug, id, url), I was surprised to find that it actually slowed down the queries, despite containing all the required columns and theoretically eliminating the need for one extra table lookups. Let’s dive into SQLite’s cost-based optimizer priorities to understand this counterintuitive behavior.

\n\n\n\n

For further context and reproducibility, here it is a separated database with a links table mirroring the original schema, populated with 10000 rows:

\n\n\n\n

CREATE TABLE IF NOT EXISTS links (\n    id INTEGER PRIMARY KEY AUTOINCREMENT,\n    slug TEXT NOT NULL UNIQUE,\n    url TEXT NOT NULL\n);\n\nWITH RECURSIVE generate_links AS (\n    SELECT 1 AS id, 'slug-' || 1 AS slug, 'https://sjdonado.com/link-' || 1 AS url\n    UNION ALL\n    SELECT id + 1, 'slug-' || (id + 1), 'https://sjdonado.com/link-' || (id + 1)\n    FROM generate_links\n    WHERE id < 10000\n)\nINSERT INTO links (slug, url)\nSELECT slug, url\nFROM generate_links;

\n\n\n\n

SQLite automatically creates sqlite_autoindex_links_1 for the UNIQUE constraint on slug:

\n\n\n\n

test.db> SELECT * FROM pragma_index_list('links') AS il JOIN pragma_index_info(il.name) ON 1 = 1;\n+-----+--------------------------+--------+--------+---------+-------+-----+------+\n| seq | name                     | unique | origin | partial | seqno | cid | name |\n+-----+--------------------------+--------+--------+---------+-------+-----+------+\n| 0   | sqlite_autoindex_links_1 | 1      | u      | 0       | 0     | 1   | slug |\n+-----+--------------------------+--------+--------+---------+-------+-----+------+\n1 row in set\nTime: 0.004s

\n\n\n\n

SQLite uses a default page size of 4KB, though this can be configured to any power of two between 512 bytes and 64KB. With the default configuration, each internal B-tree node can store approximately 500 child pointers, creating a substantial branching factor. This branching factor directly determines how many levels (the tree height) are needed to index a given number of rows, approximately log₅₀₀(N) levels for N rows. When querying data, each level traversed requires a separate page read operation, so a lower tree height dramatically improves performance. SQLite’s pager module caches recently accessed pages in memory, but the initial read of each required page still imposes I/O costs that scale with tree height.

\n\n\n\n

Covering Indexes

\n\n\n\n

To execute our query, several sequential operations are performed. SQLite will perform a binary search on the index table using SeekGE, looking for matches with the slug. It will stop there (because of the LIMIT clause, which sets the IdxGT counter) and then access the corresponding table using DeferredSeek with the rowid (IdxRowid) as a pointer:

\n\n\n\n

test.db> EXPLAIN QUERY PLAN SELECT id, url FROM links WHERE slug = 'slug-9345' LIMIT 1;\n+----+--------+---------+------------------------------------------------------------+\n| id | parent | notused | detail                                                     |\n+----+--------+---------+------------------------------------------------------------+\n| 4  | 0      | 39      | SEARCH links USING INDEX sqlite_autoindex_links_1 (slug=?) |\n+----+--------+---------+------------------------------------------------------------+\n1 row in set\nTime: 0.005s\ntest.db> EXPLAIN SELECT id, url FROM links WHERE slug = 'slug-9345' LIMIT 1;\n+------+--------------+----+----+----+-----------+----+---------+\n| addr | opcode       | p1 | p2 | p3 | p4        | p5 | comment |\n+------+--------------+----+----+----+-----------+----+---------+\n| 0    | Init         | 0  | 13 | 0  | <null>    | 0  | <null>  |\n| 1    | Integer      | 1  | 1  | 0  | <null>    | 0  | <null>  |\n| 2    | OpenRead     | 0  | 2  | 0  | 3         | 0  | <null>  |\n| 3    | OpenRead     | 1  | 3  | 0  | k(1,)     | 2  | <null>  |\n| 4    | String8      | 0  | 2  | 0  | slug-9345 | 0  | <null>  |\n| 5    | SeekGE       | 1  | 12 | 2  | 1         | 0  | <null>  |\n| 6    | IdxGT        | 1  | 12 | 2  | 1         | 0  | <null>  |\n| 7    | DeferredSeek | 1  | 0  | 0  | <null>    | 0  | <null>  |\n| 8    | IdxRowid     | 1  | 3  | 0  | <null>    | 0  | <null>  |\n| 9    | Column       | 0  | 2  | 4  | <null>    | 0  | <null>  |\n| 10   | ResultRow    | 3  | 2  | 0  | <null>    | 0  | <null>  |\n| 11   | DecrJumpZero | 1  | 12 | 0  | <null>    | 0  | <null>  |\n| 12   | Halt         | 0  | 0  | 0  | <null>    | 0  | <null>  |\n| 13   | Transaction  | 0  | 0  | 6  | 0         | 1  | <null>  |\n| 14   | Goto         | 0  | 1  | 0  | <null>    | 0  | <null>  |\n+------+--------------+----+----+----+-----------+----+---------+\n15 rows in set\nTime: 0.005s

\n\n\n\n

One can optimize query operations by avoiding table lookups through storing the url value in a single concatenated key structure. This is possible due to all columns of a composite index are stored in both B-tree internal nodes and leaf nodes, ensuring the key is sorted on a left-to-right basis. This allows efficient handling of various data distributions without performance degradation, as long as the data follows a deterministic sorting order.

\n\n\n\n

Outcome

\n\n\n\n

Following that optimization idea, let’s introduce a covering index for our table:

\n\n\n\n

 CREATE UNIQUE INDEX IF NOT EXISTS idx_links_slug_covering ON links(slug, id, url);

\n\n\n\n

test.db> SELECT * FROM pragma_index_list('links') AS il JOIN pragma_index_info(il.name) ON 1 = 1;\n+-----+--------------------------+--------+--------+---------+-------+-----+------+\n| seq | name                     | unique | origin | partial | seqno | cid | name |\n+-----+--------------------------+--------+--------+---------+-------+-----+------+\n| 0   | idx_links_slug_covering  | 1      | c      | 0       | 0     | 1   | slug |\n| 0   | idx_links_slug_covering  | 1      | c      | 0       | 1     | 0   | id   |\n| 0   | idx_links_slug_covering  | 1      | c      | 0       | 2     | 2   | url  |\n| 1   | sqlite_autoindex_links_1 | 1      | u      | 0       | 0     | 1   | slug |\n+-----+--------------------------+--------+--------+---------+-------+-----+------+\n4 rows in set\nTime: 0.002s

\n\n\n\n

Then, with the new index available, and after performing the same query again, we notice that it was not chosen by SQLite’s query planner:

\n\n\n\n

test.db> EXPLAIN QUERY PLAN SELECT id, url FROM links WHERE slug = 'slug-9345' LIMIT 1;\n+----+--------+---------+------------------------------------------------------------+\n| id | parent | notused | detail                                                     |\n+----+--------+---------+------------------------------------------------------------+\n| 4  | 0      | 39      | SEARCH links USING INDEX sqlite_autoindex_links_1 (slug=?) |\n+----+--------+---------+------------------------------------------------------------+\n1 row in set\nTime: 0.005s

\n\n\n\n

We can force the query to use our covering index, but there is no notable improvement:

\n\n\n\n

test.db> EXPLAIN QUERY PLAN SELECT id, url FROM links INDEXED BY idx_links_slug_covering WHERE slug = 'slug-9345'\n          LIMIT 1;\n+----+--------+---------+--------------------------------------------------------------------+\n| id | parent | notused | detail                                                             |\n+----+--------+---------+--------------------------------------------------------------------+\n| 3  | 0      | 40      | SEARCH links USING COVERING INDEX idx_links_slug_covering (slug=?) |\n+----+--------+---------+--------------------------------------------------------------------+\n1 row in set\nTime: 0.005s\ntest.db> EXPLAIN SELECT id, url FROM links INDEXED BY idx_links_slug_covering WHERE slug = 'slug-9345' LIMIT 1;\n+------+--------------+----+-----+----+-----------+----+---------+\n| addr | opcode       | p1 | p2  | p3 | p4        | p5 | comment |\n+------+--------------+----+-----+----+-----------+----+---------+\n| 0    | Init         | 0  | 12  | 0  | <null>    | 0  | <null>  |\n| 1    | Integer      | 1  | 1   | 0  | <null>    | 0  | <null>  |\n| 2    | OpenRead     | 1  | 931 | 0  | k(3,,,)   | 2  | <null>  |\n| 3    | String8      | 0  | 2   | 0  | slug-9345 | 0  | <null>  |\n| 4    | SeekGE       | 1  | 11  | 2  | 1         | 0  | <null>  |\n| 5    | IdxGT        | 1  | 11  | 2  | 1         | 0  | <null>  |\n| 6    | IdxRowid     | 1  | 3   | 0  | <null>    | 0  | <null>  |\n| 7    | Column       | 1  | 2   | 4  | <null>    | 0  | <null>  |\n| 8    | ResultRow    | 3  | 2   | 0  | <null>    | 0  | <null>  |\n| 9    | DecrJumpZero | 1  | 11  | 0  | <null>    | 0  | <null>  |\n| 10   | Next         | 1  | 5   | 0  | <null>    | 0  | <null>  |\n| 11   | Halt         | 0  | 0   | 0  | <null>    | 0  | <null>  |\n| 12   | Transaction  | 0  | 0   | 6  | 0         | 1  | <null>  |\n| 13   | Goto         | 0  | 1   | 0  | <null>    | 0  | <null>  |\n+------+--------------+----+-----+----+-----------+----+---------+\n14 rows in set\nTime: 0.007s

\n\n\n\n

The main difference in this last query is that instruction 7, Column retrieves the slug value directly from the index. Since DeferredSeek is no longer required, there is one operation less. However, the query is still slower. Why?

\n\n\n\n

The answer lies in the page size and density difference between these index types. Despite both indexes having the same B-tree height for our 1000-row dataset, the covering index requires triple the storage space (18 pages vs 6 pages). This directly translates to increased I/O operations during query execution.

\n\n\n\n

Index	Entry Size	Pages (N=10000)	B-tree Height	Entries/Page	Complexity	Page Reads
`rowid`	–	–	1	–	O(1)	1
`sqlite_autoindex_links_1`	24 bytes	60	3	~166	O(log N)	2-3
`idx_links_slug_covering`	72 bytes	182	4	~55	O(log N)	4-5

\n\n\n\n

For larger datasets, this density disparity would likely increase the B-tree height of the covering index before the autoindex, creating an even larger performance gap. The covering index approach only becomes advantageous when the cost of the additional table lookup DeferredSeek exceeds the cost of traversing a taller, less dense B-tree structure, typically with very large tables or when retrieving multiple wide columns that would make table lookups particularly expensive.

\n\n\n\n

That’s the paradox – a denser index is expected to be more efficient, yet it can lead to a taller B-tree and potentially worse performance.

\n",{"_35":91,"_78":92,"_80":93,"_82":94,"_8":95,"_32":96,"_86":97},1,"Building a Fast and Compact SQLite Cache Store","7/24/2024","Discover why bun:sqlite, combined with Msgpackr serialization, offers an efficient solution for building fast and compact cache stores.","/posts/building-a-fast-and-compact-sqlite-cache-store",[41,44,68],{"_88":98},"\n

When working on applications, caching is crucial for enhancing performance by reducing the need for repeated database fetches. Among the various SQLite libraries available, Bun’s native integration is optimized for performance and takes advantage of its non-blocking I/O capabilities.

\n\n\n\n

\n
The bun:sqlite module is roughly 3-6x faster than better-sqlite3 and 8-9x faster than deno.land/x/sqlite for read queries. Each driver was benchmarked against the Northwind Traders dataset. View and run the benchmark source. Source
\n

\n\n\n\n

In addition to efficient caching, serializing JavaScript objects can be slow when using JSON. This is why it makes sense to opt for efficient binary encoding alternatives like Msgpackr or CBOR. These formats are faster to parse, support complex data types, require less CPU usage, and store data more compactly, further enhancing overall application performance.

\n\n\n\n

\n\n\n\n

With this in mind, let’s explore how to build a cache manager using bun:sqlite along with efficient binary encoding.

\n\n\n\n

A cache-manager Store

\n\n\n\n

cache-manager provides a straightforward and intuitive API for caching, abstracting away the complexity of managing different cache stores and their configurations. With support for multiple stores, built-in expiration and TTL management, and robust error handling and fallback mechanisms, it ensures data integrity and freshness.

\n\n\n\n

Additionally, cache-manager is highly customizable and extensible, allowing you to create custom cache stores tailored to your needs. This flexibility means you can set up and use caching with minimal code, allowing you to focus on your application’s core logic.

\n\n\n\n

The required interface to fulfill as a cache-manager store is as follows:

\n\n\n\n

export type Store = {\n    get<T>(key: string): Promise<T | undefined>;\n    set<T>(key: string, data: T, ttl?: Milliseconds): Promise<void>;\n    del(key: string): Promise<void>;\n    reset(): Promise<void>;\n    mset(arguments_: Array<[string, unknown]>, ttl?: Milliseconds): Promise<void>;\n    mget(...arguments_: string[]): Promise<unknown[]>;\n    mdel(...arguments_: string[]): Promise<void>;\n    keys(pattern?: string): Promise<string[]>;\n    ttl(key: string): Promise<number>;\n};

\n\n\n\n

See more here.

\n\n\n\n

The Queries

\n\n\n\n

Configuring SQLite for Optimal Performance

\n\n\n\n

PRAGMA main.synchronous = NORMAL;: Ensures that SQLite writes are fast while still maintaining a reasonable level of data safety. It does not guarantee as much durability as FULL, but it is sufficient for many use cases.
PRAGMA main.journal_mode = WAL2;: Improves concurrency by allowing readers to access the database while a write operation is ongoing.
PRAGMA main.auto_vacuum = INCREMENTAL;: Allows SQLite to reclaim unused space incrementally, rather than all at once.

\n\n\n\n

1. Creating the Cache Table

\n\n\n\n

CREATE TABLE IF NOT EXISTS {table} (\n    key TEXT PRIMARY KEY, \n    val BLOB, \n    created_at INTEGER, \n    expire_at INTEGER\n);\nCREATE INDEX IF NOT EXISTS index_expire_{table} ON {table}(expire_at);

\n\n\n\n

The val column stores the cached value in a binary large object (BLOB) format, allowing it to handle various data types depending on the chosen serializer.

\n\n\n\n

2. Inserting or Updating Cache Entries

\n\n\n\n

INSERT OR REPLACE INTO ${name}(key, val, created_at, expire_at) VALUES (?, ?, ?, ?)

\n\n\n\n

expire_at is pre-calculated based on the ttl value in milliseconds, and val is pre-checked by a function isCacheable: (value: unknown) => boolean;.

\n\n\n\n

3. Retrieving Cache Entries

\n\n\n\n

SELECT * FROM ${name} WHERE key = ? AND expire_at > ? LIMIT 1

\n\n\n\n

Returns one record that has not expired.

\n\n\n\n

Auto Purge and Batch Operations

\n\n\n\n

1. purgeExpired

\n\n\n\n

const purgeExpired = async () => {\n  const now = Date.now();\n  if (now - lastPurgeTime >= 60 * 60 * 1000) {\n    const statement = db.prepare(`DELETE FROM ${name} WHERE expire_at < ?`);\n    statement.run(now);\n    lastPurgeTime = now;\n  }\n};

\n\n\n\n

Keeps the cache clean and efficient by regularly removing stale entries, ensuring that the cache does not grow indefinitely and affect performance.

\n\n\n\n

2. Batch Set (mset)

\n\n\n\n

const mset = async (pairs: [string, unknown][], ttl?: number) => {\n  const ttlValue = ttl !== undefined ? ttl * 1000 : defaultTtl;\n  if (ttlValue < 0) {\n    return;\n  }\n  const expireAt = Date.now() + ttlValue;\n\n  const stmt = `INSERT OR REPLACE INTO ${name} (key, val, created_at, expire_at) VALUES ${pairs.map(() => '(?, ?, ?, ?)').join(', ')}`;\n  const bindings = pairs.flatMap(([key, value]) => {\n    if (!isCacheable(value)) {\n      throw new NoCacheableError(`\"${value}\" is not a cacheable value`);\n    }\n    return [key, serializerAdapter.serialize(value), Date.now(), expireAt];\n  });\n\n  const statement = db.prepare(stmt);\n  statement.run(...bindings);\n};

\n\n\n\n

Improves efficiency by reducing the number of individual database operations. In the same way mget executes one single query to returns valid records with the query:

\n\n\n\n

SELECT * FROM ${name} WHERE key IN (${placeholders}) AND expire_at > ?

\n\n\n\n

Conclusion

\n\n\n\n

Bun’s SQLite implementation combined with efficient binary encoding formats like Msgpackr provides a powerful solution for building fast and compact cache stores.

\n\n\n\n

For the complete source code and implementation details, visitt: https://github.com/sjdonado/cache-manager-bun-sqlite3

\n\n\n\n

You can also find the npm package cache-manager-bun-sqlite3.

\n\n\n\n

Happy hacking!

\n\n\n\n

\n","currentTag","root","actionData","errors"]

Blog

The Covering Index Paradox

Building a Fast and Compact SQLite Cache Store