6 ms·

One dimension that is not explored is partitioning the queries in batches. The primary cost is doing lookups on the out-of-cache table, so if you have a suffici

by orlp 2y ago

One dimension that is not explored is partitioning the queries in batches. The primary cost is doing lookups on the out-of-cache table, so if you have a sufficiently large amount of queries you can resolve a couple layers of the tree in one step while those layers are in cache, grouping them based on where they land deeper in the tree, and then resolving all those queries that touch the same deeper part of the tree in one batch as well. In theory, with an infinitely large amount of input queries you will never have to do an out-of-cache lookup, it can be completely amortized away into linear scans. That said, you now end up with a bunch of results that need to be put back into the correct output order, which likely makes it not worth it. But if the operation can be fused into a reduction (e.g. find the sum of the binary search results) or the output order does not matter in some other way then all of a sudden it might make sense.

mikepurvis 2y ago
Interesting stuff, definitely the kind of real world optimization that happens when you’re able to look at actual access characteristics rather highly abstracted models. At one level you could just be saving the results into a hashtable to bubble them out again, but at the extreme end the lookup is actually spread across multiple machines in a cluster, so it’s more like throwing the query to the proper one with the right chunk of the index, along with instructions about where the final RPC is supposed to go with the result.
koverstreet 2y ago
That presumes there's both locality in your queries, and it's not an online system - result latency doesn't matter much. That's not terribly common.
tmyklebu 2y ago
There are theory papers on "buffer trees"---B-trees where each node is augmented with an O(B)-length array of pending updates and queries. I believe there were also some attempts at building SQL databases based on them. It sounds like you're reaching for the same trick.
- koverstreet 2y ago
  that's a hybrid compacting data structure: compacting within the btree node, normal btree topology otherwise. And it works much better than pure compacting (i.e. the leveldb lineage), because you avoid lock contention at the root on multithreaded update workloads, and the compaction/resort is much lower overhead when it fits in l2. incidentally, there's a filesystem that uses this technique.
  - loeg 2y ago
    > incidentally, there's a filesystem that uses this technique. BetrFS?
- loeg 2y ago
  Sounds like "fractal trees" and TokuDB.
bobmcnamara 2y ago
This works really well for subset testing, especially if sets sorted. Walk the larger tree, using the smaller tree.
natmaka 2y ago
It enhances the throughput (on average everyone waits less) at the price of a higher max latency (some, who posted a request mobilizing a very-recently-out-of-cache-index, will wait way, way more...), isn't it? In the real world those worst cases quite often kill such optimization. The (data size / cache size) ratio and queries local (in time) dispersion are key.
- Bulat_Ziganshin 2y ago
  higher throughput means we can serve more people, not that anyone will be served faster. it's like a multi-lane highway
  - natmaka 2y ago
    Indeed, my point was about "faster" (in the title).
mlochbaum 2y ago
I have explored it, see https://mlochbaum.github.io/BQN/implementation/primitive/sort.html#in-place-partitioning https://mlochbaum.github.io/BQN/implementation/primitive/sor.... I implemented this method in Dyalog 18.0 with BlockQuicksort-like partitioning, using vectorized comparison with bit-boolean output. It's faster than you'd expect, maybe twice as slow as regular binary search when searched values are in cache, and better once they fall out of L2. But Dyalog reverted to 17.1 for later versions so you won't see it in a new download. It'll probably make it into CBQN eventually, perhaps with radix partitioning. Note that both quicksort and radix partitioning can be done and undone in a cache-friendly way. Unlike quicksort, there's no issue of pivot selection since you always choose the midpoint of the searched values. However, there's a complementary issue of memory if the partitions become unbalanced, because the larger partition can require saved memory of roughly the depth times the number of elements. With a bit per comparison it's bounded by the size of the input.
- mlochbaum 2y ago
  Wasn't the best section link, last paragraph here has more detail: https://mlochbaum.github.io/BQN/implementation/primitive/sort.html#binary-search https://mlochbaum.github.io/BQN/implementation/primitive/sor...
- curiouscoding 2y ago
  Nice overview of sorting methods, thanks for sharing! I also looked a bit into radix and distribution sort at some point over the past year, but in the end high performance sorting is actually too big of a thing to just do quickly on the side, as your post well shows :") In fact I wasn't aware of the associativity issues for radix sort. That's definitely something to keep in mind and investigate. Will definitely refer back to it once I'm looking at sorting again in more detail at some point!
  - mlochbaum 2y ago
    I got stuck on sorting too, was working on SingeliSort (https://github.com/mlochbaum/SingeliSort https://github.com/mlochbaum/SingeliSort) for a while. The basic performance is there but I need to get serious about testing before using it. But the radix sort and counting sort should be very solid. The approach is about the same as the C code currently used in CBQN, linked below. The main complication is to reduce constant overhead for shorter arrays with a small count type and better prefix sums, interleaved SWAR for SingeliSort since it targets generic architecture and shared SIMD utilities in CBQN. Email in my Github profile, feel free to contact me any time if you'd like to talk about algorithms! 32-bit radix sort: https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/grade.h#L163 https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/grad... plus https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/radix.h https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/radi...
curiouscoding 2y ago
Ah yes, I did consider sorting the queries at some point but I guess I then forgot about it again. If the queries are random and much less than the input size, probably most queries will hit different cache lines in the final layer, and I suspect benefits will be limited at maybe 2x best case since the last layer is where the bottleneck is. Also (radix) sorting is very memory bound usually, and we probably need to sort in at 16^2=256 buckets or so to get sufficient reusing of the higher layers, but I don't have the numbers of what a round of radix sort takes. (My guess is order 1ns per query? Maybe I'll find time to investigate and add it to the post.)
- Bulat_Ziganshin 2y ago
  high-performance sorting algos do either merging or partitioning. I.e., you merge R input streams into one, or split one input stream into R (for quick, radix and sample sort). 1. For merge sort of N elements, you have to perform log(N)/log(R) passes 2. For sample sort - C*log(N)/log(R), where С depends on the distribution of your data, there are no strict guarantees 3. For radix sort of K-byte elements exactly K passes (indeed, 256 ways is optimal according to my tests), which is usually larger than the previous value While Mergesort looks preferable since it uses the least and fixed amount of passes, the merging code itself is less efficient - there are not much independent CPU operations, making it slower than samplesort and especially radix sort for small inputs. So, it seems that the best strategy combines two different levels - for larger blocks you absolutely need to minimize the amount of passes [over memory] and employ multithreading, while for smaller blocks we need to minimize the amount of CPU operations and increase ILP. Today two well-recognized algos are IPS4O for larger blocks and Google's SIMD QuickSort for smaller ones.
hinkley 2y ago
There was some work a while back on streaming data past queries, but you need a fairly bounded data set for that to work. Having ten years of historical data in a data set would gum that up severely.

by orlp 2y ago

mikepurvis 2y ago

Interesting stuff, definitely the kind of real world optimization that happens when you’re able to look at actual access characteristics rather highly abstracted models. At one level you could just be saving the results into a hashtable to bubble them out again, but at the extreme end the lookup is actually spread across multiple machines in a cluster, so it’s more like throwing the query to the proper one with the right chunk of the index, along with instructions about where the final RPC is supposed to go with the result.

koverstreet 2y ago

That presumes there's both locality in your queries, and it's not an online system - result latency doesn't matter much. That's not terribly common.

tmyklebu 2y ago

There are theory papers on "buffer trees"---B-trees where each node is augmented with an O(B)-length array of pending updates and queries. I believe there were also some attempts at building SQL databases based on them. It sounds like you're reaching for the same trick.

koverstreet 2y ago
that's a hybrid compacting data structure: compacting within the btree node, normal btree topology otherwise. And it works much better than pure compacting (i.e. the leveldb lineage), because you avoid lock contention at the root on multithreaded update workloads, and the compaction/resort is much lower overhead when it fits in l2. incidentally, there's a filesystem that uses this technique.
- loeg 2y ago
  > incidentally, there's a filesystem that uses this technique. BetrFS?
loeg 2y ago
Sounds like "fractal trees" and TokuDB.

bobmcnamara 2y ago

This works really well for subset testing, especially if sets sorted. Walk the larger tree, using the smaller tree.

natmaka 2y ago

It enhances the throughput (on average everyone waits less) at the price of a higher max latency (some, who posted a request mobilizing a very-recently-out-of-cache-index, will wait way, way more...), isn't it? In the real world those worst cases quite often kill such optimization. The (data size / cache size) ratio and queries local (in time) dispersion are key.

Bulat_Ziganshin 2y ago
higher throughput means we can serve more people, not that anyone will be served faster. it's like a multi-lane highway
- natmaka 2y ago
  Indeed, my point was about "faster" (in the title).

mlochbaum 2y ago

I have explored it, see https://mlochbaum.github.io/BQN/implementation/primitive/sort.html#in-place-partitioning https://mlochbaum.github.io/BQN/implementation/primitive/sor.... I implemented this method in Dyalog 18.0 with BlockQuicksort-like partitioning, using vectorized comparison with bit-boolean output. It's faster than you'd expect, maybe twice as slow as regular binary search when searched values are in cache, and better once they fall out of L2. But Dyalog reverted to 17.1 for later versions so you won't see it in a new download. It'll probably make it into CBQN eventually, perhaps with radix partitioning. Note that both quicksort and radix partitioning can be done and undone in a cache-friendly way. Unlike quicksort, there's no issue of pivot selection since you always choose the midpoint of the searched values. However, there's a complementary issue of memory if the partitions become unbalanced, because the larger partition can require saved memory of roughly the depth times the number of elements. With a bit per comparison it's bounded by the size of the input.

mlochbaum 2y ago
Wasn't the best section link, last paragraph here has more detail: https://mlochbaum.github.io/BQN/implementation/primitive/sort.html#binary-search https://mlochbaum.github.io/BQN/implementation/primitive/sor...
curiouscoding 2y ago
Nice overview of sorting methods, thanks for sharing! I also looked a bit into radix and distribution sort at some point over the past year, but in the end high performance sorting is actually too big of a thing to just do quickly on the side, as your post well shows :") In fact I wasn't aware of the associativity issues for radix sort. That's definitely something to keep in mind and investigate. Will definitely refer back to it once I'm looking at sorting again in more detail at some point!
- mlochbaum 2y ago
  I got stuck on sorting too, was working on SingeliSort (https://github.com/mlochbaum/SingeliSort https://github.com/mlochbaum/SingeliSort) for a while. The basic performance is there but I need to get serious about testing before using it. But the radix sort and counting sort should be very solid. The approach is about the same as the C code currently used in CBQN, linked below. The main complication is to reduce constant overhead for shorter arrays with a small count type and better prefix sums, interleaved SWAR for SingeliSort since it targets generic architecture and shared SIMD utilities in CBQN. Email in my Github profile, feel free to contact me any time if you'd like to talk about algorithms! 32-bit radix sort: https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/grade.h#L163 https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/grad... plus https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/radix.h https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/radi...

curiouscoding 2y ago

Ah yes, I did consider sorting the queries at some point but I guess I then forgot about it again. If the queries are random and much less than the input size, probably most queries will hit different cache lines in the final layer, and I suspect benefits will be limited at maybe 2x best case since the last layer is where the bottleneck is. Also (radix) sorting is very memory bound usually, and we probably need to sort in at 16^2=256 buckets or so to get sufficient reusing of the higher layers, but I don't have the numbers of what a round of radix sort takes. (My guess is order 1ns per query? Maybe I'll find time to investigate and add it to the post.)

Bulat_Ziganshin 2y ago
high-performance sorting algos do either merging or partitioning. I.e., you merge R input streams into one, or split one input stream into R (for quick, radix and sample sort). 1. For merge sort of N elements, you have to perform log(N)/log(R) passes 2. For sample sort - C*log(N)/log(R), where С depends on the distribution of your data, there are no strict guarantees 3. For radix sort of K-byte elements exactly K passes (indeed, 256 ways is optimal according to my tests), which is usually larger than the previous value While Mergesort looks preferable since it uses the least and fixed amount of passes, the merging code itself is less efficient - there are not much independent CPU operations, making it slower than samplesort and especially radix sort for small inputs. So, it seems that the best strategy combines two different levels - for larger blocks you absolutely need to minimize the amount of passes [over memory] and employ multithreading, while for smaller blocks we need to minimize the amount of CPU operations and increase ILP. Today two well-recognized algos are IPS4O for larger blocks and Google's SIMD QuickSort for smaller ones.

hinkley 2y ago

There was some work a while back on streaming data past queries, but you need a fairly bounded data set for that to work. Having ten years of historical data in a data set would gum that up severely.