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

31–36 of 36 posts

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

#31

Post by puzpuzpuz-hn »

mlochbaum wrote: post #25
senderista wrote: post #23

Earlier quoted context omitted.

Thanks for the links; the BQN impl looks really interesting. I believe TFA deals with only hash codes and offsets in the hash table proper (keys and values are stored separately in a dynamic array), so fixed-width keys/values still apply. It's true that you can't use keys interchangeably with hash codes for variable-length keys like I do for integer keys, but I don't expect that to affect the relative performance of…

Looks like full keys are always compared if hash codes test equal, which is what I'd expect. For example: https://github.com/questdb/questdb/blob/master/core/src/main...

That's correct. In practice, there is an insignificant amount of hash collisions, so false comparisons are extremely rare.

And thanks for sharing your experience with RH and the links!

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

#32

Post by puzpuzpuz-hn »

rkerno wrote: post #18

Hi, I'm curious how you deal with the potential for hash collisions across a large data set - is that a post-join check?

Hi, if you're asking about the hash table itself, then currently we use linear probing, i.e. k/v pairs with a collision are inserted sequentially starting with the hash%capacity index.

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

#33

Post by _a_a_a_ »

puzpuzpuz-hn wrote: post #17
_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…

> In a GROUP BY, you may have a few hundred million rows, but only a few hundred groups within them

ISWYM although that is rather a specific case. For your purposes though it may be a common case, I don't know.

> 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.

If data is already sorted and you have an 'order by' then just use the data directly – bingo, instant merge join, no hash table needed.

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

#34

Post by dimgl »

winrid wrote: post #28
dimgl wrote: post #15

Earlier quoted context omitted.

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.

Isn't javas DX pretty great? I mean not the huge XML heavy frameworks but Java itself and the IDEs work well...

Maybe it's inexperience but I never want to deal with Maven/Gradle again.

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

#35

Post by babol »

_a_a_a_ wrote: post #33
puzpuzpuz-hn wrote: post #17

Earlier quoted context omitted.

> 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…

> In a GROUP BY, you may have a few hundred million rows, but only a few hundred groups within them ISWYM although that is rather a specific case. For your purposes though it may be a common case, I don't know. > 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. If data is already sorted and you have an 'o…

> > 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.

> If data is already sorted and you have an 'order by' then just use the data directly – bingo, instant merge join, no hash table needed.

I reckon keeping data on heap in insertion order isn't that useful for joins because hash table is used for lookups while iterating the other table (so the main table determines output order). Where it could help is e.g. storing results of GROUP BY. For query such as:

SELECT timestamp, key, sum(value) from data GROUP BY timestamp, key order by timestamp

if data table stores data ordered by timestamp and hash table maintains insertion order then sorting is not required after aggregating all rows because iterating heap produces the right order.

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

#36

Post by winrid »

dimgl wrote: post #34
winrid wrote: post #28

Earlier quoted context omitted.

Isn't javas DX pretty great? I mean not the huge XML heavy frameworks but Java itself and the IDEs work well...

Maybe it's inexperience but I never want to deal with Maven/Gradle again.

Gradle's upgrades can be pretty terrible. I don't know why they keep changing it.
Post reply on HN