Building a faster hash table for high performance SQL joins
1–10 of 36 posts
Re: Building a faster hash table for high performance SQL joins
#2Serious 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 stuff), and get to "enjoy" GC pauses in the middle of your hot loops, and with fewer safety guarantees than something like Rust.
Re: Building a faster hash table for high performance SQL joins
#3I 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/
Re: Building a faster hash table for high performance SQL joins
#4Serious 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…
this is THE number one question being asked about QuestDB :) There is a thread that might help https://news.ycombinator.com/item?id=37557880
Re: Building a faster hash table for high performance SQL joins
#5Serious 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…
They started with Java and tried to use as little GC as possible and started writing hot loops in C, C++ and Rust. Logic is in Java, other stuff is mostly native.
https://questdb.io/blog/leveraging-rust-in-our-high-performa...
Re: Building a faster hash table for high performance SQL joins
#6Serious 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…
this is THE number one question being asked about QuestDB :) There is a thread that might help https://news.ycombinator.com/item?id=37557880
I see... but that seems a little weak considering it's a funded product, the first adjective they use to describe it is "fast", and good old C++ would totally slay it. The author has a C++ background, maybe he could spend an afternoon trying that?
I couldn't even try to count the number of great posts I've read about fast hash tables from e.g. Paul Khuong alone...
Re: Building a faster hash table for high performance SQL joins
#7From 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 compared to random bouncing around inside ram – very much faster then random memory accesses. So I can't see how it make a difference.
Okay, I'll read the article now…
Edit:
"If you insert "John" and then "Jane" string keys into a FastMap, then that would later become the iteration order. While it doesn't sound like a big deal for most applications, this guarantee is important in the database world.
If the underlying table data or index-based access returns sorted data, then we may want to keep the order to avoid having to sort the result set. This is helpful in case of a query with an ORDER BY clause. Performance-wise, direct iteration over the heap is also beneficial as it means sequential memory access."
but "...if the underlying table data or index-based access returns sorted data..." Then you've got sorted data, in which case use a merge join instead of a hash join surely.
Re: Building a faster hash table for high performance SQL joins
#8Since 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...
Re: Building a faster hash table for high performance SQL joins
#9Serious 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…
this is THE number one question being asked about QuestDB :) There is a thread that might help https://news.ycombinator.com/item?id=37557880
In the most non-inflammatory way possible: I am not sure I'm convinced of the performance benefits of crossing a JNI boundary to invoke a method in another language, versus letting the JVM JIT and optimize native JVM code.
Would be interesting to see benchmarks here, do you know if there are any public ones available, specific to QuestDB's interop code?
Re: Building a faster hash table for high performance SQL joins
#10Earlier quoted context omitted.
this is THE number one question being asked about QuestDB :) There is a thread that might help https://news.ycombinator.com/item?id=37557880
In the most non-inflammatory way possible: I am not sure I'm convinced of the performance benefits of crossing a JNI boundary to invoke a method in another language, versus letting the JVM JIT and optimize native JVM code. Would be interesting to see benchmarks here, do you know if there are any public ones available, specific to QuestDB's interop code?
In certain situations, crossing the JNI boundary can be advantageous. When data resides in "native" memory, outside the Java heap, the coordination of concurrent execution logic can be handled in Java, while the actual execution occurs in C++ or Rust. In this context, the negligible penalty for crossing the JNI boundary once per 10 million rows pales in comparison to the substantial benefits achievable through C++ optimization or CPU-specific assembly.