5 ms·

Whenever I look at large aggregation benchmarks like this, I try to estimate cycles/value or better cycles/byte. Take this query: SELECT cab_type,

Whenever I look at large aggregation benchmarks like this, I try to estimate cycles/value or better cycles/byte. Take this query: SELECT cab_type, count(*) FROM trips GROUP BY cab_type; This is just counting occurrences of distinct values from a bag of total values sized @ 1.1B. He's got 8 cores @ 2.7GHz, which presumably can clock up for short bursts at least a bit even when they're all running all out. Let's say 3B cycles/core/second. So in .134 seconds (the best measured time) he's burning ~3.2B cycles to aggregate 1.1B values, or about 3 cycles/value. While that's ridiculously efficient for a traditional row-oriented database, for a columnar scheme as I'm sure OmniSciDB is using, it's less efficient than I might have expected. Presumably the # of distinct cab types is relatively small, and you could dictionary-encode all possible values in a byte at worst. I'd expect opportunities both for computationally friendly compact encoding ("yellow" is presumably a dominant outlier and could make RLE quite profitable) and SIMD data parallel approaches that should let you roll through 4,8,16 values in a cycle or two. Even adding LZ4 should only cost you about a cycle a byte. That's not to denigrate OmniSciDB: They're already several orders of magnitude better than traditional database solutions, and plumbing all the way down from high-level SQL to bit twiddling SIMD is no small feat. More that there's substantial headroom to make systems like this even faster, at least until you hit the memory bandwidth wall.

alexbaden 6y ago
(disclaimer: I work for OmniSci) I think this is a good point. On GPUs, SIMT is effectively automatic vectorization, so our focus has been on the memory bandwidth wall (we make use of cuda shared memory in nvidia GPU mode for aggregates like the above query). Non-random access compression on GPUs also has been a nonstarter, at least historically. With more recent GPUs and more recent versions of CUDA, perhaps this is changing. But on CPUs, we have started looking into vectorization. There is a tradeoff, though -- the vectorization LLVM passes do add time to the compilation phase, and at subsecond query speeds that time isn't always worth it. There are also a few other tricks to get closer to roofline performance. If you sort the input data on the key you're grouping by you can see small performance improvements, mostly from better cache locality. But, part of the "magic" of OmniSciDB is that you can group on any key and get good performance without ingesting, reindexing, etc.
- bluestreak 6y ago
  I wonder what does this query compile to? In terms of C-code equivalent? SELECT cab_type, count(*) FROM trips GROUP BY cab_type; From execution time it seems to me that this is a straight sum() of 32-bit integers. "cab_type" has two distinct values and if stored 32bit value for "green" is 0 and "yellow" is 1, straight sum of these integers will produce the desired outcome and explain performance. That said the same performance will not extend to key that has three or more distinct values.
  - nikita 6y ago
    In a naive case it compiles to a loop over all the elements and hash table prob for each element. Now the magic comes from a few observations: - cab_type has very few distinct values. so you can encode those values from 1 .. N and use an array of size N instead of the hash table - you can build a “parallel scan”: split the rows evenly across many threads and each thread processes it’s on chunk - the operation per row is very basic: you need to look up in the array and increment a value. so you can use SIMD to perform operations on multiple rows at the same time - using some bit manipulation magic you can do the above on “encoded values”: you never need to convert cab_type bit represetation to an integer from 1..N
    - deleted 6y ago
      [deleted]
    - bluestreak 6y ago
      Thanks for the explanation Nikita. Any branching, hashing etc will increase execution time. The execution example is on laptop, which has 2 memory channels. 0.13s is absolute max that this laptop is able to muster as far as memory throughput goes. Usually 4 threads is enough to saturate memory. I have written this piece of code: https://github.com/questdb/questdb/blob/master/core/src/main/c/share/vec_agg.cpp#L147 https://github.com/questdb/questdb/blob/master/core/src/main... This sums 64bit values and using AVX2 it will sum 1Bn in 0.26s. Incrementing conditionally will not be as fast and will throw vectorization out of the window too.
AdamProut 6y ago
As someone who has built a columnstore database and tested it on that query shape (group-by over a column with only a few distinct values) Its possible to go faster than 1 cycle per row via SIMD and operating directly on compressed data (0.87 cycles per row). This blog post gives some details on how it’s done (https://www.memsql.com/blog/how-to-process-trillion-rows-per-second-ad-hoc-analytic-queries/ https://www.memsql.com/blog/how-to-process-trillion-rows-per...)
MuffinFlavored 6y ago
What would it take to get it to be 1 cycle/value? Does 1 cycle here mean 1 instruction? If not, how many instructions does it allow? It's just a matter of copying (in user-space I'm guessing) memory around, right?
- twoodfin 6y ago
  Modern superscalar CPUs with multi-layer caches, hyperthreading, vector extensions, ... have an incredibly complex, dynamic relationship between cycles and instructions executed. For any particular implementation of a tight inner loop like this, you could measure IPC via internal counters and it would be quite consistent, but it’s really hard to estimate without them. And does it matter? Ultimately you care about how many cores at how many GHz you need to get the job done.
hugh-avherald 6y ago
But for the inferences you've made (e.g. the # of distinct cab types is relatively small) you need knowledge of the whole data. What if someone uses the wrong column name? Getting the correct summary of data quickly is easy -- if you already know the answer. Something like `count(*)` needs to work well where you have no idea at all about the data.

alexbaden 6y ago

(disclaimer: I work for OmniSci) I think this is a good point. On GPUs, SIMT is effectively automatic vectorization, so our focus has been on the memory bandwidth wall (we make use of cuda shared memory in nvidia GPU mode for aggregates like the above query). Non-random access compression on GPUs also has been a nonstarter, at least historically. With more recent GPUs and more recent versions of CUDA, perhaps this is changing. But on CPUs, we have started looking into vectorization. There is a tradeoff, though -- the vectorization LLVM passes do add time to the compilation phase, and at subsecond query speeds that time isn't always worth it. There are also a few other tricks to get closer to roofline performance. If you sort the input data on the key you're grouping by you can see small performance improvements, mostly from better cache locality. But, part of the "magic" of OmniSciDB is that you can group on any key and get good performance without ingesting, reindexing, etc.

bluestreak 6y ago
I wonder what does this query compile to? In terms of C-code equivalent? SELECT cab_type, count(*) FROM trips GROUP BY cab_type; From execution time it seems to me that this is a straight sum() of 32-bit integers. "cab_type" has two distinct values and if stored 32bit value for "green" is 0 and "yellow" is 1, straight sum of these integers will produce the desired outcome and explain performance. That said the same performance will not extend to key that has three or more distinct values.
- nikita 6y ago
  In a naive case it compiles to a loop over all the elements and hash table prob for each element. Now the magic comes from a few observations: - cab_type has very few distinct values. so you can encode those values from 1 .. N and use an array of size N instead of the hash table - you can build a “parallel scan”: split the rows evenly across many threads and each thread processes it’s on chunk - the operation per row is very basic: you need to look up in the array and increment a value. so you can use SIMD to perform operations on multiple rows at the same time - using some bit manipulation magic you can do the above on “encoded values”: you never need to convert cab_type bit represetation to an integer from 1..N
  - deleted 6y ago
    [deleted]
  - bluestreak 6y ago
    Thanks for the explanation Nikita. Any branching, hashing etc will increase execution time. The execution example is on laptop, which has 2 memory channels. 0.13s is absolute max that this laptop is able to muster as far as memory throughput goes. Usually 4 threads is enough to saturate memory. I have written this piece of code: https://github.com/questdb/questdb/blob/master/core/src/main/c/share/vec_agg.cpp#L147 https://github.com/questdb/questdb/blob/master/core/src/main... This sums 64bit values and using AVX2 it will sum 1Bn in 0.26s. Incrementing conditionally will not be as fast and will throw vectorization out of the window too.

AdamProut 6y ago

As someone who has built a columnstore database and tested it on that query shape (group-by over a column with only a few distinct values) Its possible to go faster than 1 cycle per row via SIMD and operating directly on compressed data (0.87 cycles per row). This blog post gives some details on how it’s done (https://www.memsql.com/blog/how-to-process-trillion-rows-per-second-ad-hoc-analytic-queries/ https://www.memsql.com/blog/how-to-process-trillion-rows-per...)

MuffinFlavored 6y ago

What would it take to get it to be 1 cycle/value? Does 1 cycle here mean 1 instruction? If not, how many instructions does it allow? It's just a matter of copying (in user-space I'm guessing) memory around, right?

twoodfin 6y ago
Modern superscalar CPUs with multi-layer caches, hyperthreading, vector extensions, ... have an incredibly complex, dynamic relationship between cycles and instructions executed. For any particular implementation of a tight inner loop like this, you could measure IPC via internal counters and it would be quite consistent, but it’s really hard to estimate without them. And does it matter? Ultimately you care about how many cores at how many GHz you need to get the job done.

hugh-avherald 6y ago

But for the inferences you've made (e.g. the # of distinct cab types is relatively small) you need knowledge of the whole data. What if someone uses the wrong column name? Getting the correct summary of data quickly is easy -- if you already know the answer. Something like `count(*)` needs to work well where you have no idea at all about the data.