Day 16 Branch: View the exact code for this day at dmanchon/simpledb (
day16) (diff fromday15).
Architectural Overview: The GROUP BY Challenge
In SQL analytics, GROUP BY is fundamental for answering “how many” or “how much” per category. For small cardinalities (e.g., grouping by 50 US states), the database can easily maintain a hash table in CPU caches (L2/L3) and perform ultra-fast in-memory aggregations.
However, analytical databases must also handle high-cardinality aggregations—grouping by millions of unique users, IP addresses, or tracking IDs. When the number of distinct groups grows beyond what physical RAM can hold, an in-memory hash table will encounter frequent cache misses, and eventually trigger an Out-Of-Memory (OOM) panic or swap thrashing.
To aggregate arbitrarily large datasets under a strict memory budget, we use Partitioned Grace Hash Aggregation.
The Grace Hash Aggregation Pipeline
Grace Hash Aggregation solves the unbounded memory problem by dividing it into two phases: Partitioning and Aggregation.
Phase 1: Partitioning (Spilling to Disk)
As records stream in, we hash the GROUP BY key. We use this hash to assign the record to one of P partitions (e.g., hash(key) % P).
Instead of attempting to keep all unique groups in memory simultaneously, we maintain small memory buffers for each partition. When a partition’s buffer fills up, it is spilled to disk as a temporary run.
This ensures that records with the same group key always land in the same partition, regardless of when they arrived!
Phase 2: In-Memory Aggregation (Merging)
Once all input has been partitioned, the aggregator processes each partition one by one.
Because we know that all rows for a given group key are contained within a single partition, we can safely load the entire partition into an in-memory hash table, perform the final aggregation (SUM, COUNT), and yield the results. After one partition is aggregated and its results emitted, its memory is cleared and reused for the next partition.
Incoming Streaming Rows (Keys: 5, 2, 9, 5, 1, ...)
│
▼ Hash(Key) % P
┌─────┴─────┬───────────┐
▼ ▼ ▼
[Part 0] [Part 1] [Part 2]
(Keys: 2) (Keys: 9) (Keys: 5, 1)
│ │ │
(Spill) (Spill) (Spill)
│ │ │
▼ ▼ ▼
[Mem Hash] [Mem Hash] [Mem Hash]
│ │ │
▼ ▼ ▼
Results Results Results
By ensuring P is large enough, each individual partition’s unique groups will easily fit into the allocated memory limit, allowing simpledb to aggregate datasets infinitely larger than RAM without thrashing.
C Header: The Grace Hash Aggregator API
We define the grace_hash_agg_t structure in C11 to manage the memory buffers, the file pointers for disk spills, and the state for the output phase.
include/simpledb/grace_hash_agg.h
#pragma once
#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
// A record representing an input row for aggregation.
// We assume a simple GROUP BY (1 int32 key) and one SUM/COUNT aggregation (1 int32 value).
typedef struct {
int32_t group_key;
int32_t agg_value;
} agg_input_record_t;
// A record representing the aggregated output.
typedef struct {
int32_t group_key;
int64_t sum_value;
int64_t count_value;
} agg_output_record_t;
// Grace Hash Aggregator state
typedef struct grace_hash_agg_t {
char temp_dir[256];
size_t num_partitions;
size_t mem_limit_records;
// In-memory buffer for incoming records before they are partitioned/spilled
agg_input_record_t *in_mem_buf;
size_t in_mem_count;
// File pointers for each partition's spill file
FILE **partition_files;
char **partition_paths;
// Total records spilled to each partition
size_t *partition_counts;
bool finished_ingestion;
// For the output phase: current partition being aggregated in memory
size_t current_partition_idx;
// In-memory hash table for the current partition
// (Mock implementation will use a simple array or similar structure)
agg_output_record_t *current_hash_table;
size_t hash_table_size;
size_t hash_table_capacity;
size_t hash_table_iter_idx;
} grace_hash_agg_t;
// Create and destroy the Grace Hash Aggregator
grace_hash_agg_t *grace_hash_agg_create(const char *temp_dir, size_t mem_limit_records, size_t num_partitions);
void grace_hash_agg_destroy(grace_hash_agg_t *agg);
// Push a batch of records into the aggregator.
// If buffers fill up, records are hashed and spilled to partition files.
int grace_hash_agg_push(grace_hash_agg_t *agg, const agg_input_record_t *records, size_t count);
// Seal ingestion, flush all buffers to disk, and prepare for output phase
int grace_hash_agg_finish(grace_hash_agg_t *agg);
// Pull the next aggregated result. Returns true if a record was found, false on EOF.
bool grace_hash_agg_next(grace_hash_agg_t *agg, agg_output_record_t *out_record);
Unit Testing Grace Hash Aggregation
We simulate a workload with 10 unique groups, pushing 500 records. With a memory limit of 100 records and 4 partitions, the aggregator will be forced to spill to disk during ingestion and load partitions back into memory during the _next yield phase.
tests/test_db.c
static void test_grace_hash_agg(void) {
printf("Testing Partitioned Grace Hash Aggregation...\n");
// Memory limit of 100 records, 4 partitions
grace_hash_agg_t *agg = grace_hash_agg_create("test_grace_agg_tmp", 100, 4);
assert(agg != NULL);
size_t total_records = 500; // Will force spilling
agg_input_record_t *records = malloc(total_records * sizeof(agg_input_record_t));
for (size_t i = 0; i < total_records; i++) {
records[i].group_key = i % 10; // 10 unique groups
records[i].agg_value = 5;
}
// Phase 1: Ingestion & Partitioning
assert(grace_hash_agg_push(agg, records, total_records) == 0);
assert(grace_hash_agg_finish(agg) == 0);
// Phase 2: Aggregation & Merging
agg_output_record_t out_rec;
size_t out_count = 0;
while (grace_hash_agg_next(agg, &out_rec)) {
// We pushed 500 records. 10 groups, so each group has 50 records.
// Sum should be 50 * 5 = 250, count should be 50.
assert(out_rec.count_value == 50);
assert(out_rec.sum_value == 250);
out_count++;
}
assert(out_count == 10); // 10 unique groups
grace_hash_agg_destroy(agg);
free(records);
printf("Grace Hash Aggregation tests passed!\n");
}
Implementation Guide: Building Phase 1 (Ingestion & Spilling)
When translating the grace_hash_agg_t design into C, the boilerplate memory management is straightforward, but the spilling logic in grace_hash_agg_push requires careful orchestration.
Step 1: The Setup (_create and _destroy)
- Allocate the
grace_hash_agg_tstruct andin_mem_bufto holdmem_limit_records * sizeof(agg_input_record_t). - Allocate the arrays to hold the partition metadata (
partition_files,partition_paths,partition_counts). - In
_destroy, ensure any open file pointers are closed, temporary partition files are deleted, and all arrays are freed.
Step 2: Phase 1 Ingestion (_push)
As rows stream in, you append them to agg->in_mem_buf. When agg->in_mem_count == agg->mem_limit_records, the buffer is full. At this point, you must execute the spill:
- Loop over the in-memory buffer.
- Compute the target partition using a simple modulo hash:
uint32_t p = record.group_key % agg->num_partitions;. - Open that partition’s file in append mode (
"ab"). fwritethe record and incrementpartition_counts[p].- Once the loop finishes, reset
in_mem_count = 0and resume accepting new rows.
Step 3: Sealing the Ingestion (_finish)
When the query engine has exhausted the input table, it calls _finish().
- Perform one final spill: iterate over the remaining records currently residing in
in_mem_buf(up toin_mem_count) and write them out to their respective partitions just like in_push. - Set
agg->finished_ingestion = true.
This completes Phase 1! The records are now safely resting on disk, strictly partitioned by their group keys.
Socratic Q&A: Memory Management
Q: Should the dynamic arrays for partitions and buffers be allocated inside _create?
Yes! In C, _create acts as the constructor. Since num_partitions and mem_limit_records are only known at runtime, the struct’s internal arrays (in_mem_buf, partition_files, partition_paths, partition_counts) must be dynamically allocated inside _create immediately after allocating the main struct. This ensures the struct is fully initialized and ready to use by the time it is returned to the caller. Conversely, _destroy acts as the destructor, where you must walk through and free all these dynamically allocated arrays before freeing the main struct itself.
Q: What are some common pitfalls when initializing these arrays? Three common bugs often happen here:
- Size Mismatches: Mixing up
num_partitionsandmem_limit_records. The buffer size ismem_limit_records, but the file and path arrays must be sized bynum_partitions. - Garbage Counters: Using
mallocforpartition_counts. If you incrementcounts[p]++, it will start from a random garbage memory address! Always usecallocfor counters so they strictly start at0. - 2D String Arrays: Allocating
sizeof(char *) * num_partitionsonly allocates an array of pointers. You still must loop through and allocate/format the actual string buffers for the file paths (e.g.,"%s/part_%zu.bin", temp_dir, i).
Q: Are there pitfalls during the teardown in _destroy?
Yes! The most dangerous bug in a destructor is the Use-After-Free (UAF). If you free() your metadata arrays (like partition_files or partition_paths) before you loop through them to close and delete the temporary files, your loop will read from freed memory, resulting in undefined behavior or a crash.
Always perform your cleanup logic (closing files with fclose, deleting them with remove()) before you free the backing arrays! Furthermore, always check if a FILE* is non-NULL before passing it to fclose.
Q: Wait, do I really need to allocate every single string in a 2D string array?
Yes! This is a classic C memory concept. In Python or Java, strings are managed objects. But in C, char **partition_paths is just a “pointer to a pointer.”
When you do malloc(sizeof(char *) * num_partitions), you are only asking the OS for a block of memory to hold N memory addresses. However, those addresses initially point to random garbage. If you try to run snprintf(partition_paths[0], ...) without allocating the inner string, C will attempt to write text to a garbage memory address and immediately trigger a Segmentation Fault.
You must explicitly tell C: “Here is the array of pointers, and by the way, make each pointer point to a brand new 256-byte block of memory where I can safely write my file path.”
Q: Can we optimize this by allocating one giant flat buffer (256 * num_partitions) instead of calling malloc in a loop?
Absolutely! This is a brilliant systems-programming optimization called Arena Allocation or Flat Allocation. Calling malloc hundreds of times fragments the heap and incurs heavy syscall overhead.
Instead, you can allocate the entire string storage in one contiguous block of memory, and then manually slice it up by pointing the char ** array into specific offsets of that flat block:
// 1. Allocate the array of pointers
agg->partition_paths = malloc(sizeof(char *) * num_partitions);
// 2. Allocate ALL string memory in one single contiguous block
char *flat_string_buffer = malloc(256 * num_partitions);
// 3. Map the pointers to offsets within the flat block
for (size_t i = 0; i < num_partitions; i++) {
agg->partition_paths[i] = flat_string_buffer + (i * 256);
}
Q: In _push, should I spill records one by one as they arrive?
No! A high-performance database never writes to disk one row at a time. The entire purpose of in_mem_buf is to batch rows together.
Here are the exact logical steps for the _push write path:
- Outer Loop: Iterate through the incoming
recordsarray (fromi = 0tocount). - Buffer: Copy
records[i]intoagg->in_mem_buf[agg->in_mem_count]and incrementin_mem_count. - Check Limit: If
agg->in_mem_count == agg->mem_limit_records, the buffer is full and a Bulk Spill is triggered. - The Bulk Spill (Inner Loop):
- Iterate over the buffered records (from
j = 0toin_mem_count). - For each buffered record, calculate its partition:
uint32_t p = agg->in_mem_buf[j].group_key % agg->num_partitions. - If
agg->partition_files[p]isNULL, lazily open the file:fopen(agg->partition_paths[p], "ab"). - Write the single buffered record:
fwrite(&agg->in_mem_buf[j], sizeof(agg_input_record_t), 1, agg->partition_files[p]). - Increment
agg->partition_counts[p].
- Iterate over the buffered records (from
- Reset: After the inner spill loop completes, set
agg->in_mem_count = 0. The outer loop then continues processing any remaining incoming records.
Note: During this Phase 1 ingestion, do not attempt to build or access the hash table (current_hash_table)! Phase 1 is strictly for routing raw records to disk partitions.
Q: Why do functions like _push and _finish return int, while _next returns bool?
This follows classic POSIX/C conventions for API design:
- Returning
int(Action/Status): Used for functions that perform an action that could fail for multiple reasons (e.g., Out Of Memory, Disk Full, I/O Error). By convention,0meansSUCCESS, and any non-zero value (often negative) indicates a specific error code._pushand_finishperform disk I/O, which can fail! - Returning
bool(Question/Iterator): Used for functions that answer a binary question. For an iterator like_next,truemeans “I successfully yielded the next record”, andfalsemeans “EOF (End of File) - there are no more records”.
Q: What is the exact intent of _finish? Why can’t _push just do everything?
_push is called repeatedly while streaming data, but _push only spills when the buffer is 100% full. When the query engine reaches the end of the input table, there are usually leftover records still sitting in in_mem_buf (e.g., the buffer has 450 records, but the limit is 500). If we don’t flush them, those records are lost forever!
The intent of _finish is to seal Phase 1:
- Flush the Leftovers: It executes the exact same bulk-spill loop as
_push, but only for thein_mem_countrecords remaining in the buffer. - Close for Reading: It loops through
partition_filesand callsfcloseon any open files. In Phase 1 we opened them in"ab"(append) mode. To read them in Phase 2, we must close them so the OS flushes them to disk, allowing Phase 2 to safely reopen them in"rb"(read) mode! - Lock the State: It sets
agg->finished_ingestion = trueto signal the state machine can transition to Phase 2.
Q: Doesn’t this mean if we aggregate a massive amount of data, we write a massive amount of temporary files to disk? Yes! This is the fundamental physical limitation of Out-of-Core algorithms, known as Write Amplification. If you aggregate 100GB of data, you write 100GB to disk, just to read it back seconds later. Real databases mitigate this bottleneck using two techniques:
- Narrow Projections: We never spill wide rows. Notice our
agg_input_record_tis only 8 bytes (int32_tkey,int32_tvalue). Even 1 billion rows will only write 8 GB to disk! - Partial Pre-Aggregation: Before executing the inner spill loop, a production database will attempt to aggregate duplicates inside
in_mem_buf. If the 10,000 buffered rows only contain 50 unique keys, it aggregates them in memory and only spills 50 rows to disk! This drastically slashes disk I/O.
Implementation Guide: Building Phase 2 (Aggregation & Merging)
Phase 1 successfully routed all incoming records to strictly segregated disk partitions. Now, the state machine transitions to Phase 2.
The Intent of _next
The query execution pipeline operates as a pull-based iterator. It will call while (grace_hash_agg_next(agg, &out_record)) repeatedly until it returns false.
The intent of _next is to yield one fully aggregated row (a group_key with its final sum and count) per call.
Because we used Grace Hash partitioning, we have a mathematical guarantee: all records with the same group_key are located in the exact same partition file. Therefore, we never need to load the entire dataset into memory! We only process one partition at a time.
The _next State Machine:
- Load a Partition: If
current_hash_tableis empty, checkcurrent_partition_idx. If we have exhausted allnum_partitions, returnfalse(EOF). Otherwise, openpartition_paths[current_partition_idx]in"rb"(read) mode. - Build the In-Memory Hash Table: Read all records from the file. Insert each record into
current_hash_table. If thegroup_keyalready exists, update itssum_valueandcount_value. If it’s new, insert it. - Yield: Once the hash table is built (or if it was already built on a previous call), yield the record at
hash_table_iter_idx, increment the iterator, and returntrue. - Advance: When
hash_table_iter_idxreaches the end of the hash table, free the hash table, incrementcurrent_partition_idx, and on the next call to_next, the state machine will automatically load the next partition!
Conceptual Logic Flow for _next:
- Advance: Check if a hash table currently exists in memory and if its iterator has reached its size. If so, free the hash table, set it to NULL, and increment the partition index.
- Skip Empties: If the hash table is NULL, use a
whileloop to advance the partition index past any partitions that have a count of 0 (empty partitions). - EOF Check: If the partition index has reached the total number of partitions, return
false—the query is completely finished! - Build: If the hash table is NULL (and we found a valid partition file with data), open that specific partition file in read mode. Use a
whileloop to read every singleagg_input_record_tfrom the file. Hash each record into a dynamically sized array ofagg_output_record_t. If it exists, update sum and count. If not, insert it with a count of 1. When the file is empty, close the file. - Yield: At the very end of the function (outside all the above
ifblocks), copy the record at the current iterator index intoout_record, increment the iterator, and returntrue.
Q: The nested loops in _next make the code hard to read. How do we improve C readability?
When C code suffers from the “Arrow Anti-Pattern” (code that is indented so deeply it looks like >), the best solution is to extract the inner logic into a static helper function.
In _next, the logic to search the hash table, resize it, and insert a new record takes up 20 lines inside a while loop! You should extract this into a helper function:
static void insert_or_update(grace_hash_agg_t *agg, agg_input_record_t in);
This reduces the fread loop to a single, beautiful line of code, vastly improving the readability of the state machine.
(Additionally, always run clang-format -i src/grace_hash_agg.c to automatically fix messy indentation!)
The Final Listing
Here is the complete, working implementation of our Grace Hash Aggregation operator (src/grace_hash_agg.c).
#include "simpledb/grace_hash_agg.h"
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/signal.h>
#include <sys/stat.h>
grace_hash_agg_t *grace_hash_agg_create(const char *temp_dir, size_t mem_limit_records,
size_t num_partitions) {
grace_hash_agg_t *agg = calloc(1, sizeof(*agg));
agg->in_mem_count = 0;
agg->mem_limit_records = mem_limit_records;
agg->in_mem_buf = malloc(sizeof(agg_input_record_t) * mem_limit_records);
if (!agg->in_mem_buf) {
free(agg);
return NULL;
}
agg->partition_counts = calloc(sizeof(size_t), num_partitions);
if (!agg->partition_counts) {
free(agg->in_mem_buf);
free(agg);
return NULL;
}
agg->partition_files = calloc(sizeof(FILE *), num_partitions);
if (!agg->partition_files) {
free(agg->in_mem_buf);
free(agg->partition_counts);
free(agg);
return NULL;
}
agg->partition_paths = malloc(sizeof(char *) * num_partitions);
if (!agg->partition_paths) {
free(agg->in_mem_buf);
free(agg->partition_counts);
free(agg->partition_files);
free(agg);
return NULL;
}
char *flat_buffer = calloc(sizeof(char), 256 * num_partitions);
for (size_t i = 0; i < num_partitions; i++) {
agg->partition_paths[i] = flat_buffer + (i * 256);
snprintf(agg->partition_paths[i], 256, "%s/part_%zu.bin", temp_dir, i);
remove(agg->partition_paths[i]);
}
agg->num_partitions = num_partitions;
snprintf(agg->temp_dir, sizeof(agg->temp_dir), "%s", temp_dir);
mkdir(agg->temp_dir, 0755);
return agg;
}
void grace_hash_agg_destroy(grace_hash_agg_t *agg) {
if (!agg)
return;
free(agg->partition_counts);
free(agg->in_mem_buf);
for (size_t i = 0; i < agg->num_partitions; i++) {
if (agg->partition_files[i]) {
fclose(agg->partition_files[i]);
remove(agg->partition_paths[i]);
}
}
free(agg->partition_files);
free(agg->partition_paths[0]);
free(agg->partition_paths);
free(agg);
}
int grace_hash_agg_push(grace_hash_agg_t *agg, const agg_input_record_t *records, size_t count) {
for (size_t i = 0; i < count; i++) {
agg->in_mem_buf[agg->in_mem_count++] = records[i];
if (agg->in_mem_count == agg->mem_limit_records) {
for (size_t j = 0; j < agg->mem_limit_records; j++) {
uint32_t p = agg->in_mem_buf[j].group_key % agg->num_partitions;
if (agg->partition_files[p] == NULL) {
// new file
agg->partition_files[p] = fopen(agg->partition_paths[p], "wb");
if (!agg->partition_files[p]) {
return -1;
}
}
fwrite(&agg->in_mem_buf[j], sizeof(agg_input_record_t), 1, agg->partition_files[p]);
agg->partition_counts[p]++;
}
agg->in_mem_count = 0;
}
}
return 0;
}
int grace_hash_agg_finish(grace_hash_agg_t *agg) {
for (size_t j = 0; j < agg->in_mem_count; j++) {
uint32_t p = agg->in_mem_buf[j].group_key % agg->num_partitions;
if (agg->partition_files[p] == NULL) {
// new file
agg->partition_files[p] = fopen(agg->partition_paths[p], "wb");
if (!agg->partition_files[p]) {
return -1;
}
}
fwrite(&agg->in_mem_buf[j], sizeof(agg_input_record_t), 1, agg->partition_files[p]);
agg->partition_counts[p]++;
}
for (size_t p = 0; p < agg->num_partitions; p++) {
if (agg->partition_files[p] != NULL) {
fclose(agg->partition_files[p]);
}
}
agg->finished_ingestion = true;
return 0;
}
bool grace_hash_agg_next(grace_hash_agg_t *agg, agg_output_record_t *out_record) {
if (!agg) {
return false;
}
while (agg->hash_table_iter_idx >= agg->hash_table_size || !agg->current_hash_table) {
if (agg->current_partition_idx >= agg->num_partitions)
return false;
// reset state
free(agg->current_hash_table);
agg->current_hash_table = NULL;
agg->hash_table_size = 0;
agg->hash_table_iter_idx = 0;
agg->hash_table_capacity = 0;
// next partition
agg_input_record_t in;
agg->partition_files[agg->current_partition_idx] =
fopen(agg->partition_paths[agg->current_partition_idx], "rb");
if (agg->partition_files[agg->current_partition_idx] == NULL) {
agg->current_partition_idx++;
continue;
}
while (fread(&in, sizeof(in), 1, agg->partition_files[agg->current_partition_idx]) == 1) {
bool exists = false;
for (size_t i = 0; i < agg->hash_table_size; i++) {
if (agg->current_hash_table[i].group_key == in.group_key) {
exists = true;
agg->current_hash_table[i].count_value++;
agg->current_hash_table[i].sum_value += in.agg_value;
}
}
if (!exists) {
if (agg->hash_table_size >= agg->hash_table_capacity) {
// resize
agg->hash_table_capacity =
(agg->hash_table_capacity > 0) ? agg->hash_table_capacity * 2 : 16;
agg->current_hash_table = realloc(
agg->current_hash_table, sizeof(*out_record) * agg->hash_table_capacity);
}
agg_output_record_t new = {
.count_value = 1, .sum_value = in.agg_value, .group_key = in.group_key};
agg->current_hash_table[agg->hash_table_size++] = new;
}
};
fclose(agg->partition_files[agg->current_partition_idx]);
agg->partition_files[agg->current_partition_idx] = NULL;
remove(agg->partition_paths[agg->current_partition_idx]);
agg->current_partition_idx++;
}
*out_record = agg->current_hash_table[agg->hash_table_iter_idx++];
return true;
}
Day 16 Branch: View the exact code for this day at dmanchon/simpledb (
day16) (diff fromday15).