Hacker News Reader

Comment by bluestreak | Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com