3 ms·
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 v
by 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 agoThanks 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.
- nikita 6y agoThis 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 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)
- tmostak 6y agoHi @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.
- nikita 6y agoYes, 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.