In a distributed database using hash partitioning for the tables there is usually two options when you scan a table. Either you know the partition key and only scan a single partition, or you scan all partitions.
Assume you are scanning for hundreds of rows. It could be a table containing the files in a directory as an example, or it could be the events from a user. In both cases both variants of the scan have issues.
The single partition to scan is very efficient, but it has no parallelism and thus can have long latency when looking for hundreds of rows.
The all partition to scan is very inefficient when the number of partitions is large, but it will always have a low latency.
It would be nice to find a combination that delivers low latency at high efficiency. This is a problem that has been on my mind for decades, the solution I think is fairly elegant.
In RonDB we are adding a new feature called two-level hashing. What this means is that the hashing is done in two steps. Assume your primary key is two columns, one is the event id and the second is a timestamp. In this case you first hash on the event id, this gives you a part of the hash key. Second you hash on the timestamp. Last you put the two hashes together into a single hash key. Another example is a primary key consisting of a directory id and a file name that would be useful in a metadata server of a file system.
For key lookups it is a new way of calculating the partition to store the row, but each row can only end up in a single partition.
However, in the case of a scan that want to get all rows for a certain event id you need to scan a subset of the partitions. Hashing the event id gives you the first potential partition rows can be stored in, to find all rows of the event id you have to scan a number of partitions starting from the first. We call this the fanout. So if the fanout is 8, it means you have to scan 8 partitions to find all rows for that event id you are looking for.
We ran a benchmark where we compared a two-level hashing with a traditional hashing on the primary key. The number of fragments was 96. The benchmark executed index scans on the event id and used a limit of 100 or 200.
We found that by using a fanout of 8 and a limit of 100 the throughput doubled and the latency decreased to half compared to the traditional approach. We tested with various fanouts and 8 was the optimal number. However increasing it to 12 only decreased throughput by less than 3%. So a fanout of 16 is better at handling larger limits. The exact fanout that should be chosen is of course dependent on the application. But the experiment showed that the feature had a significant impact on the throughput and latency of cases where your application does a lot of scanning for hundreds of rows.
We can see that this can benefit our applications both in metadata servers for file systems and for feature stores storing event rows where scanning for a few hundred rows is common. Using a Partition Key that is part of the primary key turns out to be a special case of this where the fanout is 1.
