Data Intensive Systems: Lecture 6

Hash Tables

Hash indexes, hash joins, and hash aggregation all stand on one structure.

Hash table. An unordered associative array that maps keys to values. A hash function computes where a key belongs, so the DBMS can jump to a small part of the structure instead of searching keys in sorted order.

• Space. $O(n)$ in the number of entries.
• Average lookup, insert, delete. $O(1)$ under uniform hashing, because only a small collision set is inspected.
• Worst case. $O(n)$, when many keys collide and the DBMS must inspect many extra slots or pages.

Hash tables serve equality predicates well. They do not preserve key order, so they are weak for ordered scans and range predicates.

A query such as id = 42 can use a hash index directly. A query such as id BETWEEN 40 AND 60 needs ordered access, usually a B$^+$-tree or a scan.

Static Hash Tables

Static hash file. A hash file whose number of primary buckets is fixed when the file is created.

For $N$ primary buckets, the bucket for key $k$ is

$$\text{bucket}(k) = h(k) \bmod N.$$

Bucket. The unit that receives every entry whose hash maps to the same bucket number. On disk, a bucket is one primary page plus, when it fills, a chain of overflow pages.

• Primary page. The normal page for that bucket.
• Overflow chain. Extra pages linked from the primary page when the bucket fills.
• Membership rule. Keys with the same bucket number are stored in the same bucket chain.

The operations are direct:

1. Compute $h(k) \bmod N$.
2. Go to the corresponding primary bucket page.
3. Scan the primary page and any overflow pages in that bucket chain.

The weakness is fixed capacity. If one bucket receives too many keys, its overflow chain grows and the lookup is no longer close to constant time.

The idealized picture assumes:

• the number of entries is known in advance;
• the number of entries stays fixed;
• each search key is unique;
• the hash function is perfect:

$$k_1 \neq k_2 \Rightarrow h(k_1) \neq h(k_2).$$

Real files grow and shrink, search keys may repeat, and collisions are unavoidable because a large key space is mapped into a smaller bucket space.

Hashing therefore has two separate choices:

• Hash function. Computes a numeric hash value from a key.
• Hashing scheme. Stores entries and resolves collisions after two keys land together.

Hash Functions

Hash function. A function that takes a fixed- or variable-length key and produces a fixed-size output.

For a record $r$, hashing uses the search-key field:

1. Convert the key to an integer-like hash value.
2. Reduce the hash value to the bucket range $0,\dots,N-1$.

A simple pattern is

$$h(k) = a \cdot k + b, \qquad \text{bucket}(k) = h(k) \bmod N,$$

with constants $a$ and $b$. Good hashing spreads keys evenly, is fast to compute, and does not try to preserve key order.

Name	Typical use or property
CRC-64	Widely used in networking for error detection.
MurmurHash	Fast, general-purpose.
CityHash	Tuned for strings; strong on short keys (under about 64 bytes).
XXHash	Very fast, with good support for parallel hashing.

Open Addressing and Linear Probing

Open addressing. A collision-handling scheme where all entries live inside one array of slots. If the home slot is occupied, the DBMS follows a probe sequence to alternative slots.

Common probe sequences differ only in the next position they try:

• Linear probing. Step by $1$ slot each time.
• Quadratic probing. Use displacements $1^2,2^2,3^2,\dots$.
• Double hashing. Compute the step size from a second hash function.

Linear probing. A static open-addressing scheme where, if the home slot is occupied, the DBMS checks the next slot, then the next, until it finds the key or a free slot. The probe sequence is

$$\text{slot}_i(k) = \bigl(h(k) + i\bigr) \bmod N, \qquad i = 0,1,2,\dots$$

Each slot stores both key and value. The key is needed because a probe must compare the searched key against the keys it passes.

Lookup is:

1. Compute the home slot $h(k) \bmod N$.
2. Compare the stored key with $k$.
3. If the slot has a different key, move to the next slot in the probe sequence.
4. Stop when $k$ is found or when a truly empty slot is reached.

A truly empty slot proves absence because no later key in that probe run could have jumped over it.

Example 1. Five insertions colliding at slot 2.

Inserting in order $A,B,C,D,E$ shows how later keys are displaced forward from their home slots along the probe run.

Key	Home	Final	What happens
A	2	2	Slot 2 is free, so $A$ is stored there.
B	0	0	Slot 0 is free, so $B$ is stored there.
C	2	3	Slot 2 holds $A$, so probe the next slot.
D	3	4	Slot 3 is occupied, so move one more step.
E	2	5	Slots 2, 3, 4 are occupied, so scan to slot 5.

The same probe supports all operations:

1. Lookup. Stop at the key or a truly empty slot.
2. Insertion. Stop at the first reusable slot.
3. Deletion. Find the key first, then remove it without breaking later probes.

Deletion is the subtle operation. If $C$, $D$, and $E$ lie in one probe run, deleting $C$ cannot make its slot truly empty. Otherwise a later lookup for $D$ may stop at that empty slot and wrongly report absence.

Tombstone. A marker meaning the slot once held an entry that has been logically deleted. It is not treated as a free slot during lookup, so probing continues past it; a new insertion may reuse it.

Action	Reason
Delete $C$	The slot must not become fully empty, or lookups for keys farther along the same probe run stop too early.
Get $D$	The search continues past the tombstone, because $D$ may appear later in the run.
Insert $F$	The tombstone slot is reusable, so deletion still frees space.

Tombstones preserve correctness, but too many of them lengthen probe runs, so the table needs periodic cleanup or rebuilding. Other open-addressing designs (cuckoo, hopscotch, Robin Hood, Swiss tables) solve the same problem with different trade-offs in speed, memory, probe length, and update cost.

A probe run may only ever be interrupted by a truly empty slot; everything a deletion leaves behind must look "still occupied" to lookups.

Non-unique search key. A key value that may match more than one record.

Two storage choices are common:

• Separate value list. Store one copy of the key in the hash structure and keep matching values or RIDs in a list.
• Redundant keys. Store one hash-table entry per matching value, even when the key repeats.

Why Static Hashing Breaks Down

Static hashing is fast when the size estimate is right. It breaks down when that estimate becomes wrong.

• Growth creates long overflow chains or probe runs.
• Shrinkage leaves unused primary space.
• Resizing usually means rebuilding many or all pages.
• Rebuilding can block the index during reorganization.

Dynamic hashing. A family of schemes that resize incrementally instead of rebuilding the whole hash file at once.

Chained Hashing

Chained hashing. Each directory slot points to a bucket, and all entries hashing to that slot stay in its bucket; when a bucket fills, it continues through overflow pages linked into a chain.

The structure has two levels:

• Directory. An array of pointers indexed by the hash value.
• Bucket chain. The primary bucket page plus any overflow pages for that directory slot.

Operations use the same path:

1. Hash the key to a directory slot.
2. Follow the pointer to the bucket chain.
3. Scan the chain until the key is found or the chain ends.
4. Insert or delete in that chain.

Chaining avoids probe runs across the whole table, but one bucket chain can still grow too long. Splitting the overflowing bucket is the next improvement.

Extendible Hashing

Extendible hashing. A dynamic scheme with a directory of pointers to buckets. It splits only the bucket that overflows and doubles the directory only when the split needs one more hash bit.

Two depths control the structure:

• Global depth. The number of hash bits used to index the directory. At depth $d$, the directory has $2^d$ entries.
• Local depth. The number of hash bits that identify one bucket. If a bucket's local depth is below the global depth, several directory entries point to that bucket.

The gap is the sharing: a bucket with local depth $\ell$ under global depth $d$ is pointed to by $2^{d-\ell}$ directory entries.

Assume the directory is indexed with the least significant bits of the hash. At global depth $2$, $h(r)=5=101_2$ goes to entry $01$, and $h(r)=7=111_2$ goes to entry $11$.

Bucket A has local depth $2$, so it is identified by two final bits. Bucket B has local depth $1$, so both directory entries ending in $1$ point to it.

Insertion is:

1. Use the last $d$ hash bits to find the directory entry, where $d$ is the global depth.
2. Follow the pointer to the target bucket.
3. If the bucket has room, insert the entry.
4. If the bucket is full and its local depth is less than the global depth, split that bucket.
5. If the bucket is full and its local depth equals the global depth, double the directory, then split that bucket.

Splitting a bucket is:

1. Increase the bucket's local depth by $1$.
2. Allocate one new bucket with the same local depth.
3. Redistribute the old entries and the new entry using the new local-depth bit.
4. Update only the directory entries that should now point to the new bucket.

The benefit is locality. The DBMS touches the overflowing bucket and the directory entries that reference it, not the whole hash file.

Example 2. Inserting into the current directory, with $h(x)=x$.

Insert $21=(10101)_2$ with $h(x)=x$. The last two bits are $01$, so the entry targets bucket B. B is full, and its local depth $1$ is below the global depth $2$, so the bucket splits without directory doubling.

The split separates the old shared bucket:

• $7=111_2$ ends in $11$ and moves to new bucket D.
• $1,5,13,21$ end in $01$ and stay in bucket B.

Insert $19=(10011)_2$ and $15=(01111)_2$. Both end in $11$, so both go to bucket D if it has room.

Insert $20=(10100)_2$. The last two bits are $00$, so it targets bucket A. If A is full and its local depth already equals the global depth, the directory doubles from $2^2$ to $2^3$ entries before A splits.

A directory can use least significant bits (LSB) or most significant bits (MSB). The logical rule is the same. The implementation differs: with LSB, doubling copies the old directory and appends the copy; with MSB, earlier pointer positions must be rewritten more carefully.

Linear Hashing

Linear hashing. A dynamic scheme with no directory. It permits temporary overflow pages but controls them by splitting buckets gradually in a fixed round-robin order rather than splitting the bucket that overflowed.

Linear hashing keeps a pointer called next. When any bucket overflows, the DBMS splits bucket next, then advances the pointer. The bucket that overflows is not necessarily the bucket that splits.

Linear hashing uses one hash family:

$$h_i(k) = h(k) \bmod \left(2^i N\right),$$

where $N$ is the initial bucket count and $i$ is the current level. Each level doubles the hash range.

With $N=4$: $h_0(k)=h(k)\bmod 4$, $h_1(k)=h(k)\bmod 8$, and $h_2(k)=h(k)\bmod 16$.

The state is:

• Level. The current round number. At level $i$, the table is moving from range $2^iN$ toward $2^{i+1}N$.
• Next. The pointer to the next bucket that must be split.

A round starts with

$$N_{\text{level}} = N \cdot 2^{\text{level}}$$

base buckets.

• Buckets $0,\dots,\text{next}-1$ have already split in the current round.
• Buckets $\text{next},\dots,N_{\text{level}}-1$ have not split yet.
• A round ends when next reaches $N_{\text{level}}$. Then level increases by $1$ and next resets to $0$.

Behind the next pointer the world uses one more bit; in front of it the old function is still right.

Search chooses the hash function from next:

1. Compute $b=h_{\text{level}}(k)$.
2. If $b \geq \text{next}$, search bucket $b$.
3. If $b < \text{next}$, bucket $b$ has already split, so recompute $b=h_{\text{level}+1}(k)$ and search that bucket.

Insertion uses the same bucket choice:

1. Find the target bucket by the search rule.
2. If the bucket has space, insert the entry.
3. If the bucket is full, place the entry in an overflow page.
4. Split bucket next using $h_{\text{level}+1}$.
5. Advance next; if the round is complete, increment level and reset next to $0$.

Linear hashing grows without a directory. Rehashing is spread across insertions, and only one bucket is reorganized per split.

Example 3. One overflow triggers a split.

Start with $N=4$ buckets and $\text{next}=0$, holding bucket $0:\{8,20\}$, bucket $1:\{5,9,13\}$ (full), bucket $2:\{6\}$, bucket $3:\{7,11\}$.

Searching for $6$ gives $6\bmod 4 = 2$. Since $2\ge\text{next}$, bucket $2$ has not split, so no recomputation is needed.

Inserting $17$ gives $17\bmod 4=1$. Bucket $1$ is full, so $17$ goes to an overflow page. That overflow triggers a split of bucket $\text{next}=0$, not bucket $1$.

The split uses $h_1(k)=k\bmod 8$:

• $8\bmod 8=0$, so $8$ stays in bucket $0$.
• $20\bmod 8=4$, so $20$ moves to new bucket $4$.
• next advances to $1$.

Bucket	Contents	Comment
0	$8$	already split this round
1	$5, 9, 13$ and overflow $17$	not split yet
2	$6$	not split yet
3	$7, 11$	not split yet
4	$20$	new bucket from the split

After the split, searching for $20$ first gives $20\bmod 4=0$. Since $0<\text{next}$, bucket $0$ has split, so recompute $20\bmod 8=4$ and search bucket $4$. Searching for $9$ gives $9\bmod 4=1$, and $1\ge\text{next}$, so bucket $1$ has not split and no recomputation is needed.

The split pointer eventually reaches every bucket, so overflow chains are reduced in round-robin order. Linear hashing still depends on a good hash function, and temporary overflow pages can lengthen lookups.

Disk-Oriented Sorting

A disk-oriented DBMS cannot assume that a table or query result fits in main memory. Algorithms run through the buffer pool and may spill data to disk. Good disk algorithms therefore favor large sequential reads and writes.

Sorting is needed for:

• ORDER BY;
• duplicate elimination for DISTINCT;
• grouping for GROUP BY;
• efficient bulk-loading of a B$^+$-tree.

External sorting. Sorting a file that is too large to fit in memory by creating sorted runs on disk and repeatedly merging them.

Run. A sorted piece of the file produced during external sorting.

2-way external sort. A baseline external sort where each merge step combines two runs into one larger run.

The algorithm is:

1. Pass 0. Read one page, sort it in memory, and write it back as a one-page sorted run. Repeat for all $N$ pages.
2. Merge passes. Merge pairs of runs. Each pass doubles the run length.
3. Stop. Finish when one sorted run remains.

A 2-way merge needs three buffer pages: one input page per run and one output page.

Each pass reads and writes every page exactly once, so a pass costs $2N$ I/Os. The number of passes is $1+\lceil\log_2 N\rceil$, giving a total of

$$2N\left(1+\lceil\log_2 N\rceil\right)$$

I/Os.

External merge sort with $B$ buffers. The practical version uses all available buffer pages.

Pass 0 creates

$$R_0 = \left\lceil \frac{N}{B} \right\rceil$$

initial runs.

The algorithm is:

1. Pass 0. Read up to $B$ pages, sort them in memory, and write one sorted run.
2. Merge passes. Use $B-1$ input buffers and one output buffer, so each merge pass combines up to $B-1$ runs.
3. Stop. Finish when one run remains.

The pass count is

$$P = 1 + \left\lceil \log_{B-1} R_0 \right\rceil.$$

The total I/O cost is

$$2N \cdot P.$$

Every pass reads and writes every page exactly once, so the cost is always $2N$ per pass; all sorting optimization is about reducing the number of passes.

A larger buffer pool creates fewer initial runs and gives each merge pass a larger fan-in.

Example 4. Sorting $N=108$ pages with $B=5$ buffers.

Pass	Runs after the pass	What happens
0	$\lceil 108/5\rceil=22$	$22$ sorted runs of $5$ pages, except the last with $3$ pages.
1	$\lceil 22/4\rceil=6$	Merge $4$ runs at a time into $6$ runs; most are $20$ pages, the last is $8$.
2	$\lceil 6/4\rceil=2$	Merge again into $2$ runs of $80$ and $28$ pages.
3	$1$	A final merge produces one sorted file of $108$ pages.

The pass count is $1+\lceil\log_4 22\rceil = 1+3 = 4$, matching the four rows.

Double buffering. An I/O technique that prefetches the next page or run fragment while the current buffer is being processed.

Double buffering overlaps CPU work with disk transfer. It can reduce elapsed time, but it reserves extra buffers, so the effective merge fan-in may be smaller than $B-1$.

The pass count $P$ for different file and buffer sizes shows how sharply memory helps.

$N$	$B=3$	$B=5$	$B=9$	$B=17$	$B=129$	$B=257$
100	7	4	3	2	1	1
1,000	10	5	4	3	2	2
10,000	13	7	5	4	2	2
100,000	17	9	6	5	3	3
1,000,000	20	10	7	5	3	3
10,000,000	23	12	8	6	4	3
100,000,000	26	14	9	7	4	4
1,000,000,000	30	15	10	8	5	4

With little memory, sorting needs many passes. With more memory, pass count drops sharply, and each avoided pass saves about $2N$ I/Os.

Sorting with a B+-Tree

When a table already has a B$^+$-tree index on the sort attribute, the DBMS may avoid external sorting by scanning the index in key order.

The index-order scan is:

1. Go to the left-most leaf page.
2. Scan leaf pages from left to right.
3. Fetch records in the order given by the leaf entries.

Clustering determines whether this is good:

• Clustered B$^+$-tree. Usually strong for sorting, because records are stored close to leaf order and reads are mostly sequential.
• Unclustered B$^+$-tree. Usually weak for large sorts, because leaf entries are sorted but record fetches may be random. In the worst case, the cost is close to one I/O per record.