Cloud Data Warehouse

for

Data Intensive Applications

Mosha Pasumansky - moshap@firebolt.io

NWDS 2024

Architecture

Architecture

3D Engine 💪

Sparse Index ☝

WAL Lookup 🫣

FireJoin🔥

Shuffle 💨

The Hash-Join Algorithm

Aim: Compute SELECT a, c FROM R JOIN S ON R.a = S.b

​

​

Hash-Join algorithm to the rescue!

• Well known, proposed in the late 1970s
• Most commonly used join algorithm in analytical DBs

​

​

Two Phases:

1. Build
2. Probe

Hash-Join: 1) Build Phase

Idea: Go over S row-by-row and build a “hashtable”

= data structure that can map key => value

​

Right table: S Conceptually Details hashtable

Hash-Join: 1) Build Phase

Idea: Go over S row-by-row and build a “hashtable”

= data structure that can map key => value

​

Right table: S Conceptually Details hashtable

hash_bucket(� 1)� �=> 1’001

Hash-Join: 1) Build Phase

Idea: Go over S row-by-row and build a “hashtable”

= data structure that can map key => value

​

Right table: S Conceptually Details hashtable

hash_bucket(� 2)� �=> 1’234’567

Hash-Join: 1) Build Phase

Idea: Go over S row-by-row and build a “hashtable”

= data structure that can map key => value

​

Right table: S Conceptually Details hashtable

hash_bucket(� 5’000’000)� �=> 1’001

Hash-Join: 1) Build Phase

Idea: Go over S row-by-row and build a “hashtable”

= data structure that can map key => value

​

Right table: S Conceptually Details hashtable

hash_bucket(� 10’000’000)� �=> 5’555’555

Hash-Join: 2) Probe Phase

Idea: Go over R row-by-row and probe the “hashtable”

= data structure that can map key => value

​

Left table: R Conceptually Details hashtable

​

​

​

​

​

​

​

​

Result:

​

Hash-Join: 2) Probe Phase

Idea: Go over R row-by-row and probe the “hashtable”

= data structure that can map key => value

​

Left table: R Conceptually Details hashtable

​

​

​

​

​

​

​

​

Result:

​

Hash-Join: 2) Probe Phase

Idea: Go over R row-by-row and probe the “hashtable”

= data structure that can map key => value

​

Left table: R Conceptually Details hashtable

​

​

​

​

​

​

​

​

Result:

​

hash_bucket(� 5’000’000)� �=> 1’001

Hash-Join: 2) Probe Phase

Idea: Go over R row-by-row and probe the “hashtable”

= data structure that can map key => value

​

Left table: R Conceptually Details hashtable

​

​

​

​

​

​

​

​

Result:

​

hash_bucket(� 5’000’000)� �=> 1’001

Hash-Join: 2) Probe Phase

Idea: Go over R row-by-row and probe the “hashtable”

= data structure that can map key => value

​

Left table: R Conceptually Details hashtable

​

​

​

​

​

​

​

​

Result:

​

hash_bucket(� 5’000’000)� �=> 1’001

Encoding of Tuples

How to encode ?

​

“Vanilla”, as 8 byte ints: 40 4B 4C 00 00 00 00 00, 2A 00 00 00 00 00 00 00

=> 16 bytes

​

Encoding of Tuples

How to encode ?

​

“Vanilla”, as 8 byte ints: 40 4B 4C 00 00 00 00 00, 2A 00 00 00 00 00 00 00

=> 16 bytes

​

​

FireHashJoin: 40 4B 4C, 2A

=> 4 bytes

Why?

• Stats-collection pass �For all rows, find max # bytes needed for each column

​

• Here for all 10M rows: 3 bytes for column b, 1 byte for column c

Memory-Layout of the Hashtable

Common “chaining” hashtable

​

​

​

​

​

​

​

​

​

​

​

​

​

=> 830 MB (with RowRefs)

8 byte ptr

8 byte ptr

8 byte int

8 byte int

Memory-Layout of the Hashtable

Common “chaining” hashtable FireHashTable

​

​

​

​

​

​

​

​

​

​

​

​

​

=> 830 MB (with RowRefs)

8 byte ptr

8 byte ptr

8 byte int

8 byte int

Tuples laid out back-to-back

in a byte-array��Each tuple as �“4-bytes blob”�in the compact

encoding.

​

Bucket 1’001:�01 00 00 2F

40 4B 4C 2A

​

​

​

Bucket 1’001

Bucket 1’234’567

Bucket 5’555’555

Memory-Layout of the Hashtable

Common “chaining” hashtable FireHashTable

​

​

​

​

​

​

​

​

​

​

​

​

​

=> 830 MB (with RowRefs) => 90 MB

8 byte ptr

8 byte ptr

8 byte int

8 byte int

~1.5 bytes

3 bytes

1 byte

Tuples laid out back-to-back

in a byte-array��Each tuple as �“4-bytes blob”�in the compact

encoding.

​

Sorted by hash/bucket

Thank you for your time