Comment by puzpuzpuz-hn | Hacker News Reader

Comment by puzpuzpuz-hn | Hacker News Reader

Parent Full thread

> 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

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

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

Reply on news.ycombinator.com