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.
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.
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
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.
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.
And of course there is no branching in MemSQL for this use case. And also no hashing b/c number of groups is small and you can use an array and not a hashtable.
Finally if you compress data rather than do the sum on an uncompressed array you will have a lot more compact data representation which would allow you not hit the memory bandwidth ceiling this quickly (4 threads)
When you say an array and not a hash table, do you just mean a simple perfect hash table indexed by the offset of the dictionary id? We use this fairly extensively for inputs of bounded domain (i.e. dictionary-encoded strings, moderately-sized integer ranges, even binned values, numeric or timestamp), but call it a perfect hashing. Assume we're talking about the same thing but wanted to clarify.
I’m still of an opinion that it’s important to demonstrate performance on more complex queries with joins, subqueries, subselects, and clustered data movements. The count(*), group by query is a very very simple case.
Comments
(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.
I wonder what does this query compile to? In terms of C-code equivalent?
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.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
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...
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.
This sounds about right. The query is using count and not sum which i believe can be a bit faster.
Yes. Branching will absolutely hurt. Good old x100 paper teaches how to avoid branching: http://cidrdb.org/cidr2005/papers/P19.pdf.
And of course there is no branching in MemSQL for this use case. And also no hashing b/c number of groups is small and you can use an array and not a hashtable.
Finally if you compress data rather than do the sum on an uncompressed array you will have a lot more compact data representation which would allow you not hit the memory bandwidth ceiling this quickly (4 threads)
Hi @nikita, good to reconnect.
When you say an array and not a hash table, do you just mean a simple perfect hash table indexed by the offset of the dictionary id? We use this fairly extensively for inputs of bounded domain (i.e. dictionary-encoded strings, moderately-sized integer ranges, even binned values, numeric or timestamp), but call it a perfect hashing. Assume we're talking about the same thing but wanted to clarify.
Yes, that’s it.
I’m still of an opinion that it’s important to demonstrate performance on more complex queries with joins, subqueries, subselects, and clustered data movements. The count(*), group by query is a very very simple case.