A couple months ago, we released DoltLite, a free open-source drop-in replacement for SQLite with Dolt-style version control features. DoltLite works by ripping out SQLite’s B-Tree storage engine and replacing it with a content-addressed Prolly Tree, the same data structure that powers Dolt.
We’ve been benchmarking Dolt against MySQL for years using sysbench. Recently, Dolt got faster than MySQL on sysbench. But, Dolt and MySQL are completely separate SQL engines. Most of the performance difference comes from the SQL engine, not the B-tree vs Prolly Tree difference. “How much?”, you ask. It was hard to tell.
Until now. DoltLite is SQLite from the B-tree interface up, in other words, the same SQL engine. The only difference between DoltLite and SQLite is B-tree versus Prolly Tree, a true performance bake off. We can finally answer the question “What’s the Prolly Tree performance tax?” This article does just that.
The Prolly Tree Tax#
Here’s the whole article in one table. Same SQL engine on both sides, so every number below is purely the Prolly Tree versus SQLite’s B-tree, nothing else. We run in memory to keep it a clean race, with no disk or page cache to muddy the result. The one exception is autocommit writes, which only mean anything on disk, since committing is a durability cost. Lower is better for DoltLite:
| Workload | Prolly Tree tax |
|---|---|
| Reads | 1.20x — a 20% tax |
| Batched writes | 1.67x — a 67% tax |
| Autocommit writes | 4.00x — the real tax lives here |
The Prolly Tree tax is modest on reads, noticeable on batched writes, and only really bites when you commit every single write. And on that last one you usually have an out: batch your writes in a transaction.
A True Bake-Off#
DoltLite is a drop-in replacement for SQLite, and that’s exactly what makes this measurement clean. Everything from the B-tree interface up — the parser, the planner, the whole SQL engine — is line-for-line SQLite. The only thing we changed is the storage engine underneath. So when we run the identical SQL through both and compare, the difference is the Prolly Tree tax, isolated. No SQL-engine variable muddying the result the way there is when we benchmark Dolt against MySQL.
To isolate the data structure even further, the numbers in this article are from in-memory databases. That strips out the disk and the page cache, leaving the raw cost of walking and updating a Prolly Tree instead of a B-tree.
We build stock SQLite straight out of the same source tree (make DOLTLITE_PROLLY=0 sqlite3) and run a sysbench-style OLTP suite against both on every PR: 100,000-row tables, the median of 5 invocations per test (9 for autocommit writes), workload-only timing off a monotonic clock. CI enforces a hard ceiling: 2.5x on any individual test, 2x on a section average. The build goes red if we regress performance. We run the whole thing four times with different key types: integer, text, blob, and composite.
The full table gets posted as a comment on every PR.
Reads#
In memory, reads cost about 20% more than SQLite:
| Test | SQLite (us) | DoltLite (us) | Multiplier |
|---|---|---|---|
| oltp_point_select | 23,710 | 29,457 | 1.24 |
| oltp_range_select | 10,124 | 11,930 | 1.18 |
| oltp_sum_range | 9,490 | 11,938 | 1.26 |
| oltp_order_range | 2,572 | 2,953 | 1.15 |
| oltp_distinct_range | 3,628 | 4,013 | 1.11 |
| oltp_index_scan | 3,951 | 5,275 | 1.34 |
| select_random_points | 10,245 | 11,268 | 1.10 |
| select_random_ranges | 2,979 | 4,117 | 1.38 |
| covering_index_scan | 4,124 | 4,380 | 1.06 |
| groupby_scan | 30,945 | 33,884 | 1.09 |
| index_join | 6,005 | 8,159 | 1.36 |
| index_join_scan | 3,396 | 4,597 | 1.35 |
| types_table_scan | 1,057,625 | 1,218,914 | 1.15 |
| table_scan | 1,233,810 | 1,304,540 | 1.06 |
| oltp_read_only | 102,177 | 120,120 | 1.18 |
| Average | 1.20 |
Why 20%? A Prolly Tree node is content-addressed, so every step down the tree is a hash lookup in the chunk cache plus a decode of the node’s packed key/value layout, where SQLite’s B-tree just follows a page pointer. That extra indirection is the tax.
Batched Writes#
Batched into a transaction, writes cost about 67% more in memory:
| Test | SQLite (us) | DoltLite (us) | Multiplier |
|---|---|---|---|
| oltp_bulk_insert | 181,919 | 253,557 | 1.39 |
| oltp_insert | 15,472 | 27,785 | 1.80 |
| oltp_update_index | 51,887 | 89,758 | 1.73 |
| oltp_update_non_index | 34,388 | 59,641 | 1.73 |
| oltp_delete_insert | 46,005 | 71,917 | 1.56 |
| oltp_write_only | 22,530 | 44,628 | 1.98 |
| types_delete_insert | 24,611 | 40,401 | 1.64 |
| oltp_read_write | 72,397 | 108,598 | 1.50 |
| Average | 1.67 |
A 67% tax to get full history, branching, diff, and merge on your data. Sounds like a good trade to me.
Writes cost more than reads because a Prolly Tree is immutable. Changing one row can’t overwrite a node in place the way a B-tree does. It re-hashes that node and every node above it up to the root, allocating new content-addressed chunks along the way. That’s more work per write, even inside a single transaction. The flip side is that the very same immutability is what buys you cheap branching and content-addressed diffs.
Autocommit Writes#
It was going so well. Committing every write is where the Prolly Tree performance story gets a little gnarly. This is the one section measured on disk: a commit is a durable write, so it only means anything with a real file behind it.
| Test | SQLite (us) | DoltLite (us) | Multiplier |
|---|---|---|---|
| oltp_bulk_insert_ac | 20,541 | 75,772 | 3.69 |
| oltp_insert_ac | 23,297 | 91,726 | 3.94 |
| oltp_update_index_ac | 26,183 | 104,527 | 3.99 |
| oltp_update_non_index_ac | 21,466 | 86,763 | 4.04 |
| oltp_delete_insert_ac | 22,961 | 96,960 | 4.22 |
| oltp_write_only_ac | 23,384 | 95,285 | 4.07 |
| types_delete_insert_ac | 20,889 | 93,985 | 4.50 |
| oltp_read_write_ac | 29,065 | 103,041 | 3.55 |
| Average | 4.00 |
About 4x. This is structural, not a bug. Every commit in a Prolly Tree re-hashes the path from the changed leaf up to the root and writes new immutable, content-addressed chunks. That cost is O(log n) in the tree’s depth, but with a bigger constant than SQLite, so it grows as tables get bigger. Back when we ran the suite at 10,000-row tables, autocommit writes were comfortably under 2x, versus the 4x you see here at 100,000 rows. SQLite just mutates a page in place and shifts the index if necessary.
Moreover, DoltLite’s content-addressed store must update more physical locations on disk as well as the manifest and the branch HEADs. This just adds to the performance overhead.
Keep DoltLite Fast#
The sysbench metrics suggest two pieces of DoltLite performance advice.
Batch Writes#
The autocommit write fix is the same advice you’d get for stock SQLite: batch your writes.
BEGIN;
-- thousands of inserts here
COMMIT;Those same operations get much cheaper the moment you wrap them. Batching amortizes the per-commit re-hashing across thousands of rows, which is exactly why the batched-writes tax (1.67x) is so much smaller than the autocommit one (4x).
Let’s keep the 4x in perspective. That autocommit test is 200 separate committed inserts, ~25ms total in SQLite versus ~100ms in DoltLite. Per write, that’s about 0.125ms versus 0.5ms, both faster than a single frame of video. Unless you’re committing one row at a time in a loop, you will never feel it. So go ahead and use autocommit if it’s easier. For most applications the tax simply won’t matter.
Use Integer Keys#
We run everything with a few different primary key types to see what, say, UUID-shaped keys cost. In memory, text keys push reads to about 1.5x and batched writes to about 1.9x, with range scans climbing toward 2.3x. The takeaway: if you care about speed, integer primary keys are the fast path. UUIDs work, they just cost more.
Conclusion#
So what’s the Prolly Tree tax? For years we could only guess. Dolt is faster than MySQL, but they’re different SQL engines, so the storage layer’s contribution was buried. DoltLite finally lets us measure it in isolation. The Prolly Tree tax is about 20% on reads, 67% on batched writes, and 4x on single-row autocommit writes. Just like my beloved California, the taxes are worth it. In California, you get the weather. With DoltLite, you get the version control.
Packing your bags and joining the DoltLite gold rush? Come by our Discord, and we’ll give you a warm welcome in the #doltlite🪶 channel.