Constructing a sooner hash desk for prime efficiency SQL joins

Should you run a JOIN or a GROUP BY in a database of your selection, there’s a
good likelihood that there’s a hash desk on the core of the info processing. At
QuestDB, now we have FastMap, a hash desk used for hash be a part of and mixture
dealing with. Whereas excessive performing, its design is a bit unconventional because it
differs from most general-purpose hash tables.

On this article, we’ll inform you why hash tables are necessary to databases, how
QuestDB’s FastMap works and why it quickens SQL execution.

Database + hash desk = ❤️#

QuestDB is an open-source time-series database that helps
InfluxDB Line Protocol for quick streaming
ingestion and SQL over Postgres wire protocol
and HTTP for versatile and environment friendly querying. Like
most SQL databases, we help JOINs:

The above question includes an implicit
INNER JOIN and returns one thing like
the next outcome set:

What precisely does the database do to return this outcome? There are a number of
approaches to processing a JOIN, one among which is the so-called
hash join.

To finish a hash be a part of, we first iterate the joined desk (firms in our
instance) and retailer all be a part of key to row mappings in a hash desk. Then, we will
iterate the primary desk (staff) whereas utilizing the hash desk to search out the
joined rows:

It is a simplified model of what just about any database does when it
decides to execute a hash be a part of. Discover that the hash desk is utilized in a
grow-only method. Which means that as soon as information is added to the hash desk, it’s
not eliminated or modified – the desk will solely develop in measurement.

Consequently, we solely see get()/put() operations, for retrieval and
addition respectively. For sure, a quick hash desk is important for
robust hash be a part of efficiency.

Our second use case has to do with GROUP BY and
SAMPLE BY, our time-series SQL extension.
Let’s rely folks with the identical surnames with a easy GROUP BY:

The above question will return one thing like this:

Once more, what sort of magic does the database do to course of such a question? The
reply is that, effectively, it makes use of a hash desk:

Discover that we use a cursor over the hash desk to traverse and iterate over the
outcome set. Every little thing is simple:

1. We retailer GROUP BY column values (last_name) as hash desk keys
2. Combination capabilities (rely()) go to hash desk values

Think about that we run this question over a couple of hundred million rows. This implies at
least a couple of hundred million hash desk operations. As you may think, a gradual
hash desk would make for a slower question. A sooner hash desk? Quicker queries!

We would like a sooner desk. Let’s talk about what makes FastMap completely different from a
general-purpose information construction. The remainder of the put up assumes that you simply’re
conversant in hash desk fundamentals and design choices, so if that is not the case,
we suggest studying the
Hash table Wikipedia page.

FastMap internals#

Choose to learn the code? Leap over to FastMap within the
QuestDB GitHub repository.

FastMap is written in Java and makes use of
Unsafe
closely to retailer information outdoors of JVM’s heap, in native reminiscence.

At a look, FastMap is only a hash desk with open addressing and linear
probing. The load issue is stored comparatively low (0.7) and hash codes are cached
to mitigate hash collision impression. Nothing stunning up to now. The fascinating
half is that the hash desk is grow-only, and helps var-size keys, however solely
fixed-size values.

FastMap consists of two foremost elements:

1. An array of offsets and hash codes, i.e. the hash desk itself
2. a so-called heap, i.e. a grow-only chunk of native reminiscence

These two elements will be illustrated with the next diagram:

Every offset worth is a compressed 32-bit offset pointing at a key-value pair
saved within the heap. Key-value pair addresses are 8 byte-aligned, therefore we will
compress 35-bit offsets to 32-bit. Which means that a FastMap is able to
holding as much as 32GB of knowledge. Curiously, OpenJDK does the same trick with
object tips about 64-bit programs when
CompressedOops
function is enabled.

Since offsets aren’t reminiscence addresses, however deal with deltas, they continue to be the identical
if the heap is reallocated. In different phrases, there is no such thing as a must replace the
offsets when the heap must develop.

The heap itself incorporates key-value pairs saved in insertion order. Because of
our SQL use instances, we will restrict FastMap to grow-only API. In different phrases: It
solely helps insert and replace operations, however does not help key deletion.

Consequently, we needn’t cope with tombstones and periodical heap
compaction. As soon as a SQL question execution finishes, we will merely zero the offsets
array and deal with the heap as empty.

Every key-value pair saved on the heap has the next format:

The important thing size is saved in bytes on the entry header, permitting for fast
navigation to the worth. That is notably helpful for variable-size keys,
resembling a single STRING column worth. Following the header, the pair reminiscence
incorporates all key column values (much like fields), after which the worth column
values.

FastMap is designed to help solely fixed-size values, resembling a number of
INT columns. This design selection results in simplified updates to the worth
when mandatory.

One other good aspect impact of this indirection with the heap is the assured
insertion order on hash desk iteration. Most hash tables haven’t any iteration
order ensures as a result of nature of hash capabilities. However FastMap is
completely different.

Should you insert “John” after which “Jane” string keys right into a FastMap, then that
would later turn into the iteration order. Whereas it does not sound like an enormous deal
for many functions, this assure is necessary within the database world.

If the underlying desk information or index-based entry returns sorted information, then we
might wish to hold the order to keep away from having to kind the outcome set. That is
useful in case of a question with an ORDER BY clause. Efficiency-wise, direct
iteration over the heap can be useful because it means sequential reminiscence entry.

See Also

Financial institution of America’s unrealized losses on securities rose to $131.6 bln

The hash perform utilized in FastMap can be considerably unconventional. We took a
lengthy path utilizing Java String‘s
hash function
(the polynomial hash perform from The C Programming Language guide by Kernighan
& Ritchie), then xxHash64, then one other
polynomial perform impressed by this
Peter Lawrey’s post:

Right here we calculate the hash code first in 8-byte chunks (lengthy kind), then in
4 bytes (int) and, lastly, byte-by-byte. This gives a lot better pace
than a single byte-size loop and is called the
SWAR method.

Sure, this perform has a worse high quality than xxHash, however that is mitigated by its
compactness and the truth that we cache hash codes. A small executable is
necessary for smaller keys.

A perform that occupies many i-cache
traces might present worse outcomes than a less complicated one. Until hash code calculation in
a decent loop is all the things that your code does, a extra complicated hash perform
with higher high quality just isn’t essentially higher (wink-wink benchmarks that present
spectacular hash perform throughput).

Bear in mind how we additionally cached hash codes for the inserted keys? Because of that, we
needn’t re-calculate them on look-ups, saving treasured CPU cycles for extra
necessary issues.

However is all of the complexity price it? Why not simply use a very good outdated
java.util.HashMap from the usual Java library? Let’s run a couple of
microbenchmarks
to match them. The
first
benchmark verifies how lengthy it takes to lookup a brief string key in a hash
map:

On common it takes 309 nanoseconds for FastMap to search out the worth for the
given key whereas for HashMap it takes 367 nanoseconds.

The
next
benchmark checks how lengthy it takes to insert a string key in a map:

Once more, FastMap is barely sooner than HashMap which is critical
contemplating that the usual hash desk had an extended optimization path throughout so
many Java variations. QuestDB’s hash desk additionally has the benefit of being
zero-GC. It does not put any strain on the rubbish collector because the information is
saved off-heap.

For many who wish to run the benchmarks and examine the outcomes, on this case
we used Ubuntu 22.04, OpenJDK 64-bit 17.0.8.1, and an Intel i7-1185G7 CPU to get
the outcomes.

Whereas now we have the microbenchmarks in place, we choose counting on the question
execution occasions as the first metric. With among the described FastMap
enhancements touchdown in QuestDB not too long ago, we lowered GROUP BY / SAMPLE
BY question execution occasions by 20-30%.

What’s subsequent?#

So, is QuestDB’s FastMap the perfect factor since sliced bread? After all, it is
not. As with all the things in engineering, it is a matter of trade-offs. FastMap
works properly for us, but it surely does not imply that it could be a good selection for,
say, an online utility and even for an additional database. In addition to that, there are
at all times some issues to be optimized and improved. For instance, the so-called
disk spill could possibly be added to
FastMap to deal with big be a part of conditions.

N.B. Because of the precious suggestions we obtained from the group after
publishing this put up, we have began experimenting with additional optimizations.
Essentially the most noticeable one is
Robin Hood hashing,
a linear probing enhancement aimed to reduce the variety of look-up probes for
the keys. Should you choose leaping to the code, the pull request is
here.

As standard, we encourage you to strive the newest QuestDB launch and share your
suggestions with our Slack Community. You can too
play with our live demo to see how briskly it executes
your queries.