Recently I got asked an interesting question in our Discord:

Could Adaptive Radix Trees be a good alternative to Prolly Trees?

This turned out to be an interesting question! The tl;dr is: “There are a couple of reasons why Radix Trees wouldn’t work for our use case, but questioning those reasons actually raises some interesting thought experiments.” Let’s break it down.

Prolly Trees#

We talk a lot about Prolly Trees, since it’s the data structure that makes Dolt possible.

Dolt is the first version controlled SQL database, it supports Git-style version control operations like push, pull, branch, and merge, and can store the entire version history of tables with minimal space overhead. We’re able to do this because Dolt is built on Prolly Trees, a novel data structure for tree-based maps. Prolly Trees are incredibly useful because of some properties that they have:

• Content-Addressed nodes: All tree nodes are stored in a [hash table], keyed by their hash. Nodes reference each other by storing hashes to other nodes.
• History Independence - Any data set has a unique representation, regardless of the sequence of operations that led to the current state.
• Structural Sharing - Storing multiple versions of the data only requires additional storage proportional to their diff: duplicate parts of the data are deduplicated.
• Ranged Lookup Support - They can store ordered data and perform lookups based on ordered keys or offsets.

We have a Prolly Tree visualizer that helps illustrate these principles; I recommend playing around with it. These properties form the core of a version controlled database.

Content addressing means that we can check whether two nodes are identical by just comparing their hashes. And when nodes reference each other by their hashes, this means we can compare whether two trees are identical by just comparing the hash of their root nodes. A tree that does this is called a Merkle tree, of which Prolly Trees are an example.

History independence extends this even further: since two trees that contain the same data have the exact same shape, this means we can use hashes to not just identify not just whether two trees are identical, but also whether they contain the same data. And if they root hashes differ, we can recurse and look at the hashes of the child nodes to identify exactly which regions have changes.

Structural sharing is a natural consequence of the previous properties and lets us avoiding using more space than necessary. And range lookups are an important feature for any database index.

But Prolly Trees aren’t the only data structure to have these properties.

Adaptive Radix Trees#

An Adaptive Radix Tree (ART) is a specific improvement on Radix Trees, designed to make them more cache-friendly, more space-efficient, and allow for potentially faster lookup operations. They provide a way to represent a map as a tree where each node in the tree contains all the keys with a common prefix.

An Adaptive Radix Tree is not inherently a Merkle tree, but it’s easy to make it one: simply store every node in a hash table, and represent edges by storing the hash of the child node inside the parent. If you “Merkleize” an Adaptive Radix Tree this way, it immediately gains a lot of the same useful properties that we want from Prolly Trees.

For starters, Adaptive Radix Trees are already history-independent. Since all keys with a common prefix share a common parent node, the shape of the tree is entirely determined by its set of keys, regardless of the order items were inserted. Thus, it’s also easy to show that a Merkleized ART would also exhibit structural sharing: changes to a key-value pair in the tree can only ever modify the nodes along the path from the root to that key. Two versions of the tree with the same elements would necessarily have both the same shape and the same root hash.

Dolt’s diff and merge algorithms require that there is exactly one way to partition an index tree, and Adaptive Radix Trees 100% meet that requirement. So does that mean that we could replace Prolly Trees in Dolt with Adaptive Radix Trees?

It’s not quite that simple.

Radix Trees Require Lexicographic Ordering#

Both Radix Trees and Prolly Trees support ordered iteration, but there’s an important distinction between ordering in search-based trees like Prolly Trees, and ordering in Radix Trees. While search-based trees can use any search function to compare keys, Radix Trees can only order their keys lexicographically.

This is because keys in Radix Trees are interpreted as a sequence of bytes. When performing a lookup, each node is indexed on some number of bytes from the key. In ARTs in particular, every node is a decision point on a single byte in the key.

This works just fine when the key is meant to interpreted as a string. But for a database, keys often encode little-endian integers, floats, decimals, and more. For these ata types, their lexicographic ordering is different from their semantic ordering. In order for Radix Trees to support ordered iteration, they must first convert the key into a different format where the semantic ordering matches the lexicographic ordering, which is nontrivial and introduces a bottleneck.

Another possible solution would be to use a Radix Tree design that interprets keys as a sequence of multi-byte values, not a sequence of bytes. But this is not what Adaptive Radix Trees are: ARTs have a specific layout that is heavily optimized for operating on bytes, and a design that indexes on larger data types would look very different.

Radix Tree Heights Scale With Key Length#

Because each node in a Radix Tree corresponds to a key prefix, the shape of a Radix Tree is strongly influenced by the shape of the keys used. In an unoptimized Radix Tree, the depth of a leaf node is proportional to the length of its key. This potentially makes it unsuitable if the keys are variable-length or potentially of unbounded length.

Adaptive Radix Trees use two optimizations called path compression and lazy expansion to prevent this. However even with these optimizations, the depth of a leaf is proportional to the number of comparisons required to distinguish the key from all other keys in the tree, which in the worst case is again proportional to the length of the key.

Radix Trees are not Self-Balancing#

This is the big one. An important property of Prolly Trees that I haven’t mentioned yet is the fact that they’re probabilistically balanced. All leaf nodes in a Prolly Tree occur at the same level, and the size of a node in a Prolly Tree follow a predictable distribution regardless of the distribution of the keys themselves. This helps avoid worst-case scenarios where some key lookups are much more expensive than others. This self-balancing property is true even if the keys have different lengths, and even if the keys have a non-uniform distribution.

Radix Trees don’t have this property. A Radix Tree is only balanced if the keys are uniformly distributed.

If you assume that every key is equally likely to be read, you really want a balanced tree, where all paths are the same height and all nodes have roughly the same fanout. This is because nodes with a larger fanout are more likely to appear in a tree walk and take longer to do a binary search on, and paths with a greater height take longer to walk.

That said, if your access pattern isn’t uniform, then there may be circumstances where you don’t want a balanced tree. If you know in advance that some keys will be looked up more frequently than others, then a tree that has shorter heights for the common keys and longer heights for the uncommon keys might perform better. So a Radix Tree might have improved performance if:

• You’re using variable length keys and know that longer keys are accessed less frequently, or
• Keys that share a common prefix with each other are collectively accessed less often than keys that don’t share a common prefix with other keys.

I can’t think of any situation off of the top of my head where these might be true. It would also require a specific use case where you’re reasonably confident that these conditions will stay true over the lifetime of the database. But it could happen.

Where Radix Trees Could Help#

While ruminating on this, it got me thinking about whether there are circumstances where Dolt would benefit from something like Radix Trees as an addition to Prolly Trees instead of a replacement.

I got a moment of clarity when the same user as before asked me a question about Dolt’s DOLT_HASHOF_TABLE function. Typically, users don’t need to know about the content-hashes that Dolt uses internally. But sometimes users building applications on top of Dolt benefit from being able to peek at the underlying structure. For instance, by comparing the hashes of two tables, a user can programmatically determine whether or not the tables are identical.

In this case, the user was asking whether they could call DOLT_HASHOF_TABLE on a filtered subset of a table. This is a totally reasonable ask: there’s lots of cases where a user might want to know whether the set of rows matching the filter has changed by storing the hash.

Unfortunately, what the user was asking for isn’t currently possible. In order for it to work, Dolt would need to have computed the hash of a tree node containing exactly the rows that match the filter.

But you know what data structure does contain nodes containing exactly some filter condition? Radix Trees.

If you have a composite primary key and you want to filter on a specific value for the first key column, this is guaranteed to correspond to a single node in a Radix Tree. DOLT_HASHOF_TABLE on a subset of a table filtered by a key prefix would totally work if Dolt was built on Radix Trees. But it would come with severe trade-offs.

Fortunately, although users can’t get a hash describing a filtered table, they can get almost the same result via the DOLT_DIFF system table function, which can be filtered on the produce the desired effect. If the result is empty, then the tables being compared are equal.

The Best of Both Worlds?#

This got me thinking about a theoretical hybrid approach that users could opt-into for composite indexes. Currently, Dolt creates a single Prolly Tree for each index, where the key is a tuple of every column in the index. But instead, we could imagine a hierarchy of Prolly Trees, with one level for each column, and the leaf of one Prolly Tree pointing to the root of the next. This is essentially a Radix Tree, where each node of the Radix Tree is itself an entire Prolly Tree.

Doing this would introduce both the benefits and the drawbacks of Radix Trees: the entire tree would no longer be balanced, with some keys having faster lookups than others. Each value in the first key column would have its own Prolly Tree, and some of those would be larger than others. For uniform access patterns, this will be slower on average, but if the access pattern is known in advance, it might be faster.

Performance here is still dependent on the distribution of keys and their accesses, but it’s easier to reason about than pure Merkleized Radix Trees because the shape of the tree is determined purely by the number of different values for each column, rather than individual bytes. If a large percentage of the keys in the index have a common value for their first column, but most queries exclude that value, then the part of the tree that is actually accessed for queries will have a smaller depth than it would if the tree was balanced.

It would also allow functions like DOLT_HASHOF_TABLE to filter on a key prefix and return a content hash that represents just the rows with that prefix.

Right now, the amount of added complexity doesn’t seem worth the benefit. But it’s fun to think about.

Head-to-Head#

Putting this all together, we can directly compare every approach.

Shared benefits of every approach:

• History Independence: Tables with the same state always have the same hash.
• Structural Sharing: Many versions can be represented efficiently.
• Efficient Diff and Merge: Two tables can be compared by only inspecting the ranges of the tree that changed.

Pros of Prolly Trees:

• Allows iteration orders other than lexicographic ordering.
• Performance is independent of key distribution or key length.
• Avoids worst-case scenarios with extremely small or extremely large tree nodes.

Pros of Merkleized Radix Trees:

• If key lookups are known to be non-uniform in specific ways, could potentially have improved performance.
• A user can store a Merkle hash for an arbitrary key prefix to see if the set of rows with that prefix changes.

Pros of a hybrid approach:

• If most lookups only care about a small percentage of the tree, could potentially have improved performance.
• A user can store a Merkle hash for an arbitrary key prefix to see if the set of rows with that prefix changes.

Overall, the circumstances where Radix Trees provide a benefit are both extremely specific and quite speculative. Prolly Trees end up being the better approach overall.

Conclusion#

That’s all for now. As always, if you have any thoughts about this or if you just want to chat, come join our Discord. We always like to hear what people think.