Unchained hashtable

[hbirler]

Hello! This is not an "issue" but I just found it cool that someone else also tried to implement the unchained hash table for the contest.

We started with a chaining hash table then tried the unchained one. The unchained one was only a couple percentage points faster and it was a bit close to the deadline so we decided to stick with the chaining hash table: https://github.com/umbra-db/contest-sigmod2025/blob/master/engine/op/Hashtable.hpp

So, the JOB queries are relatively small, and for many queries, the tables can fit into L1/L2/L3 caches. When that happens, instruction counts are often more important than memory layout as memory accesses will be fast. So, I would expect the builds for the unchained hash table to be noticeably slower than the builds of the chaining hash table. For probes, I would expect the unchained table to be always somewhat faster (and much faster with long chains and a lot of data that does not fit into caches). Also, the memory allocation strategy can also have a huge impact on hash table performance, sometimes even more so than the design of the table.

[clflushopt]

First of all thanks for the "issue" and congratulations on the win. So yes, initially I went down the rabbit hole of implementing the hash table, I've read the paper a few months back but just didn't have an excuse to work on it.
I did go down several wrong paths implementation wise and now having yours as a source of truth is very helpful. I didn't particularly look at all the queries but I did come to the same conclusion that they can fit into L1/L2/L3 caches and that optimizing for total instruction count yields better result, the other thing I didn't try or do is implementing the bump allocator and morsel driven scheduling which I guess could have made things much faster.

Thanks again for pinging me about this ! Also amazing work on the implementation you folks went the extra mile with DP query optimization (I thought would be overkill but I guess I was wrong 😛 ).