Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building a faster hash table for high performance SQL joins

questdb.io

Post reply on HN
Print view View original

11–20 of 36 posts

Re: Building a faster hash table for high performance SQL joins

#11

Post by toasted-subs »

pixelpoet wrote: post #2

Serious question, if performance is the lynchpin, why write it in Java? Especially considering they use unsafe "heavily", for big joins they could easily just call out to some native code if the surrounding code reaaaaally must be Java (again, why?). It's the worst of both worlds using unsafe Java: you don't get native speed, there's loads of memory overhead from everything being an Object (besides the rest of the VM…

Yeah, I genuinely don't understand why so many people reach for Java for everything.

Re: Building a faster hash table for high performance SQL joins

#12

Post by jerrinot »

senderista wrote: post #8

Since the blog post mentioned a PR to replace linear probing with Robin Hood, I just wanted to mention that I found bidirectional linear probing to outperform Robin Hood across the board in my Java integer set benchmarks: https://github.com/senderista/hashtable-benchmarks/blob/mast... https://github.com/senderista/hashtable-benchmarks/wiki/64-b...

A QuestDB engineer here: These are cool benchmarks! The idea to try Robin Hood probing came to me after receiving some feedback on Reddit. I ran initial experiments, and the results were promising, leading to its integration into our codebase. Thank you so much for sharing your repository. Perhaps one day we'll explore bidirectional probing as well!

A snapshot of my happiness after running first experiments with Robin Hood: https://twitter.com/jerrinot/status/1730147245285150743 :)

Re: Building a faster hash table for high performance SQL joins

#13

Post by puzpuzpuz-hn »

senderista wrote: post #8

Since the blog post mentioned a PR to replace linear probing with Robin Hood, I just wanted to mention that I found bidirectional linear probing to outperform Robin Hood across the board in my Java integer set benchmarks: https://github.com/senderista/hashtable-benchmarks/blob/mast... https://github.com/senderista/hashtable-benchmarks/wiki/64-b...

Thanks! We're still benchmarking Robin Hood hashing and are open to further experiments. The benchmarks look promising.

Re: Building a faster hash table for high performance SQL joins

#14

Post by puzpuzpuz-hn »

gavinray wrote: post #3

I always enjoy reading stuff written by Andrey, he's a brilliant fellow for sure. Can highly recommend his personal blog as well: https://puzpuzpuz.dev/

Thanks, Gavin, I'm pleased to hear that. And thanks for recommending my blog!

Re: Building a faster hash table for high performance SQL joins

#15

Post by dimgl »

pixelpoet wrote: post #2

Serious question, if performance is the lynchpin, why write it in Java? Especially considering they use unsafe "heavily", for big joins they could easily just call out to some native code if the surrounding code reaaaaally must be Java (again, why?). It's the worst of both worlds using unsafe Java: you don't get native speed, there's loads of memory overhead from everything being an Object (besides the rest of the VM…

Interestingly I recently saw an MQ broker written in Java and it seemed to have some pretty impressive performance. I'm not a huge fan of Java's DX but I have to admit, that's some serious performance. Can't remember the name but it was on the homepage this week I believe.

Re: Building a faster hash table for high performance SQL joins

#16

Post by marginalia_nu »

toasted-subs wrote: post #11
pixelpoet wrote: post #2

Serious question, if performance is the lynchpin, why write it in Java? Especially considering they use unsafe "heavily", for big joins they could easily just call out to some native code if the surrounding code reaaaaally must be Java (again, why?). It's the worst of both worlds using unsafe Java: you don't get native speed, there's loads of memory overhead from everything being an Object (besides the rest of the VM…

Yeah, I genuinely don't understand why so many people reach for Java for everything.

It's a very well rounded language is why, and whatever papercuts exist are either on the way out in newer/future java versions, or made up for by the tooling ecosystem.

Re: Building a faster hash table for high performance SQL joins

#17

Post by puzpuzpuz-hn »

_a_a_a_ wrote: post #7

From article "Imagine that we run this query over a few hundred million rows. This means at least a few hundred million hash table operations. As you might imagine, a slow hash table would make for a slower query. A faster hash table? Faster queries!" I'll read the article properly after this, this is just a quick skim, but I can't see this quote can be correct. Unless I'm missing something, hashing function is fast…

> Unless I'm missing something, hashing function is fast compared to random bouncing around inside ram – very much faster then random memory accesses. So I can't see how it make a difference.

In a GROUP BY, you may have a few hundred million rows, but only a few hundred groups within them. A slow function would slow down things dramatically in that case since the hash table remain small and data access is potentially linear.

> Then you've got sorted data, in which case use a merge join instead of a hash join surely.

This property is beneficial for GROUP BY which includes a timestamp or a function over timestamp. QuestDB organizes data sorted by time, so relying on insertion order may help to avoid redundant sorting if there is an ORDER BY clause with the timestamp column.

As for merge join, we also use it in ASOF join: https://questdb.io/docs/reference/sql/join/#asof-join

Re: Building a faster hash table for high performance SQL joins

#19

Post by [deleted] »

marginalia_nu wrote: post #16
toasted-subs wrote: post #11

Earlier quoted context omitted.

Yeah, I genuinely don't understand why so many people reach for Java for everything.

It's a very well rounded language is why, and whatever papercuts exist are either on the way out in newer/future java versions, or made up for by the tooling ecosystem.

[deleted]

Re: Building a faster hash table for high performance SQL joins

#20

Post by mlochbaum »

senderista wrote: post #8

Since the blog post mentioned a PR to replace linear probing with Robin Hood, I just wanted to mention that I found bidirectional linear probing to outperform Robin Hood across the board in my Java integer set benchmarks: https://github.com/senderista/hashtable-benchmarks/blob/mast... https://github.com/senderista/hashtable-benchmarks/wiki/64-b...

Worth pointing out that this can depend a lot more on fiddly details than you might expect. In particular, you're dealing with a small fixed width allowing the hash to be stored in the table instead of the key. The article emphasizes variable-length keys, and I don't see any specialization on key sizes (if 4- and 8-byte keys aren't common then this makes sense; if they are then I'd expect dedicated table code for those sizes to be valuable). And set lookups are also just a bit different from value lookups. I think these cases are different enough that I have no idea if the results would carry over, although I can see how the bidirectional approach would reduce probing more than RH which seems good.

...and since I've done a lot of work with Robin Hood on small-key lookups, I can point out some little tweaks that have made a big difference for me. I have 8-byte lookups at just over 3ns/lookup[0], albeit at a very low load factor, typically or greater hash, probing just finds the first slot that's greater than or equal to the requested key's hash. So the lookup code[1] is very simple (the rest, not so much). The while loop is only needed on a hash collision, so at a low load factor a lookup is effectively branchless. However, these choices are specialized for a batched search where the number of insertions never has to be higher than the number of searches, and all the insertions can be done first. And focused on small-ish (under a million entries) tables.

[0] https://mlochbaum.github.io/bencharray/pages/search.html

[1] https://github.com/dzaima/CBQN/blob/5c7ab3f/src/singeli/src/...

Post reply on HN