Day 2 Branch: View the exact code for this day at dmanchon/simpledb (day2) (diff from day1).

Building upon 64-byte aligned allocators, physical query execution operators require a mechanism to inspect column data without copying underlying memory or managing buffer lifecycles.

1. Memory Ownership in Query Execution

In object-oriented architectures, data movement between execution operators frequently involves vector allocation or copy construction. In an analytical engine scanning 100 million rows, copying column vectors introduces latency and consumes memory bandwidth.

Physical query operators (such as SIMD filters, scans, and hash aggregations) read data sequentially without needing to modify or take ownership of the input columns.

                      Zero-Copy Window (O(1) Time, 0 Bytes Allocated)
                       ┌──────────────────────────────────────────────┐
                       │                                              │
Full Column Array:     [ 100 │ 200 │ 300 │ 400 │ 500 │ 600 │ 700 │ 800 ]
                                     ▲
                                     │  slice_i32_t { .data = ptr + 2, .len = 4 }

2. Zero-Copy Typed Slices

A slice provides a non-owning window view over a contiguous memory array.

typedef struct {
    const int32_t* data;
    size_t len;
} slice_i32_t;

Slices offer three core structural benefits:

  • O(1) Windowing: Sub-ranges of column data are created in constant time without memory allocation by advancing the pointer (data + offset) and adjusting len.
  • Storage Agnosticism: Slices expose a uniform interface regardless of whether the target memory resides in an in-memory allocation buffer (buffer_i32_t) or a memory-mapped file descriptor (mmap).
  • Read-Only Guarantees: The const int32_t* data qualifier prevents accidental modification of column data during query execution loops.

3. Polymorphism via C11 _Generic Macros

To support multiple column types (int32_t, float, int64_t) without type erasure (void*) or template instantiations, simpledb uses C11 _Generic selection expressions.

#define slice_of(PTR, LEN) _Generic((PTR), \
    int32_t*:       slice_i32_create((const int32_t*)(PTR), (LEN)), \
    const int32_t*: slice_i32_create((const int32_t*)(PTR), (LEN)), \
    float*:         slice_f32_create((const float*)(PTR), (LEN)), \
    const float*:   slice_f32_create((const float*)(PTR), (LEN)) \
)
FeatureC11 _Generic MacroC++ Templates
Compile-Time SafetyUnmatched types fail directly at macro expansionVerbose template instantiation stack traces
Binary Code SizeZero bloat (compiles only explicit functions)Monomorphization bloat across object files
Runtime OverheadZero overhead (resolved entirely at compile time)Zero overhead (unless virtual dispatch is used)
Language ComplexityTransparent C11 preprocessor expansionRequires SFINAE, concepts, and meta-templates

4. Architectural Comparison: Dynamic Buffer vs. Zero-Copy Slice

PropertyDynamic Buffer (buffer_i32_t)Zero-Copy Slice (slice_i32_t)
OwnershipOwner (Manages heap allocation lifecycle)View (Non-owning read-only reference)
MutabilityMutable (Supports push and capacity growth)Immutable (const int32_t* data)
Passing OverheadPassed by pointerPassed by value (16-24 bytes on stack)
Sub-WindowingRequires memory allocation and copyO(1) pointer arithmetic (data + offset)
Primary RoleData ingestion and intermediate result buffersPhysical query operators and SIMD kernels

5. Header Implementation: include/simpledb/slice.h

#pragma once
#include "simpledb/allocator.h"
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct {
    const int32_t* data;
    size_t len;
} slice_i32_t;

typedef struct {
    const float* data;
    size_t len;
} slice_f32_t;

static inline slice_i32_t slice_i32_create(const int32_t* buff, size_t len) {
    return (slice_i32_t){ .data = buff, .len = len };
}

static inline slice_f32_t slice_f32_create(const float* buff, size_t len) {
    return (slice_f32_t){ .data = buff, .len = len };
}

static inline slice_i32_t buffer_i32_as_slice(const buffer_i32_t* buff) {
    if (!buff || !buff->data) return (slice_i32_t){ .data = NULL, .len = 0 };
    return (slice_i32_t){
        .data = (const int32_t*)buff->data,
        .len = buff->size
    };
}

static inline slice_f32_t buffer_f32_as_slice(const buffer_i32_t* buff) {
    if (!buff || !buff->data) return (slice_f32_t){ .data = NULL, .len = 0 };
    return (slice_f32_t){
        .data = (const float*)buff->data,
        .len = buff->size
    };
}

static inline slice_i32_t slice_i32_sub(slice_i32_t s, size_t offset, size_t count) {
    return (slice_i32_t){ .data = (const int32_t*)s.data + offset, .len = count };
}

static inline slice_f32_t slice_f32_sub(slice_f32_t s, size_t offset, size_t count) {
    return (slice_f32_t){ .data = (const float*)s.data + offset, .len = count };
}

static inline int32_t slice_i32_at(slice_i32_t s, size_t idx) {
    return s.data[idx];
}

static inline float slice_f32_at(slice_f32_t s, size_t idx) {
    return s.data[idx];
}

#define slice_of(PTR_OR_BUF, LEN) _Generic((PTR_OR_BUF), \
    int32_t*:       slice_i32_create((const int32_t*)(PTR_OR_BUF), (LEN)), \
    const int32_t*: slice_i32_create((const int32_t*)(PTR_OR_BUF), (LEN)), \
    float*:         slice_f32_create((const float*)(PTR_OR_BUF), (LEN)), \
    const float*:   slice_f32_create((const float*)(PTR_OR_BUF), (LEN)), \
    buffer_i32_t*:  buffer_i32_as_slice((const buffer_i32_t*)(PTR_OR_BUF)) \
)

6. Unit Test Verification

// [tests/test_db.c]
static void test_slices(void) {
    // 1. Test NULL pointer slice creation via slice_of
    slice_i32_t null_slice = slice_of((int32_t*)NULL, 3);
    assert(null_slice.data == NULL);
    assert(null_slice.len == 3);
    (void)null_slice;

    // 2. Test buffer conversion & element lookup
    buffer_i32_t* buf = buffer_i32_create(16);
    for (int i = 0; i < 10; i++) {
        buffer_i32_push(buf, (i + 1) * 100);
    }

    slice_i32_t s_buf = slice_of(buf, 0);
    assert(s_buf.len == 10);
    assert(slice_i32_at(s_buf, 0) == 100);
    assert(slice_i32_at(s_buf, 4) == 500);
    (void)s_buf;

    // 3. Test O(1) sub-slicing
    slice_i32_t sub = slice_i32_sub(s_buf, 2, 5);
    assert(sub.len == 5);
    assert(slice_i32_at(sub, 0) == 300);
    assert(slice_i32_at(sub, 4) == 700);
    (void)sub;

    // 4. Test C11 _Generic macro dispatch for int32_t vs float arrays
    int32_t raw_i32[] = { 10, 20, 30 };
    float   raw_f32[] = { 1.5f, 2.5f, 3.5f };

    slice_i32_t gen_i32 = slice_of(raw_i32, 3);
    slice_f32_t gen_f32 = slice_of(raw_f32, 3);

    assert(gen_i32.len == 3 && slice_i32_at(gen_i32, 1) == 20);
    assert(gen_f32.len == 3 && slice_f32_at(gen_f32, 1) == 2.5f);
    (void)gen_i32;
    (void)gen_f32;

    // 5. Test buffer zero-copy re-interpretation as float slice
    slice_f32_t f32_from_buf = buffer_f32_as_slice(buf);
    assert(f32_from_buf.len == 10);
    assert(f32_from_buf.data != NULL);
    (void)f32_from_buf;

    buffer_i32_free(buf);
}

Day 2 Branch: View the exact code for this day at dmanchon/simpledb (day2) (diff from day1).