← Back
Home › Systems › Databases and storage engines

embedded-sql

embedded single-file SQL database

SQLite, DuckDB

SystemTechniques · 11Primitives · 33 embedded-sql External merge sortsearch-sort · medium: Sort data larger than RAM: write memory-sized sorted runs, then k-way merge them with large sequential buffers; terabytes in one merge pass.›Buffer poolstorage · medium: The database's own page cache (frames, page table, pin counts, dirty bits, replacement) so it, not the OS, controls eviction, write order and I/O.›Columnar storagestorage · medium: Store each column contiguously so analytic scans read only the columns they need, compress well and run as tight SIMD loops.›Morsel driven parallelismstorage · medium: Split pipelines into small morsels scheduled NUMA-aware across worker threadsMVCCstorage · medium: Keep timestamped versions of each row so readers see a consistent snapshot without blocking writers; the default concurrency control in modern databases.›Query optimizerstorage · medium: Cost-based plan search: join ordering (DP/greedy), rewrites, access path selectionVectorized executionstorage · medium: Query operators pass batches of about 1-2K values per column instead of single tuples, amortizing interpretation overhead and enabling tight SIMD loops.›fsync, O_DSYNC and O_DIRECThardware-os · low: What fsync, fdatasync, O_DSYNC, O_DIRECT and F_FULLFSYNC really guarantee on Linux and macOS, and the exact call sequences for crash-safe files.›Zone mapsstorage · low: Per-block min/max (and sparse primary) indexes to skip data during scansHash joinstorage · low: Build a hash table on the smaller input's join key and probe it with every row of the larger one; the linear-time workhorse for equi-joins.›Bytecode interpretercompilers · low: Register/stack VM dispatch loop for executing compiled plans or rules (SQLite VDBE, nftables)Recursive-descent parsingcompilers · low: Hand-written top-down parser with one function per grammar rule; simple, fast, with full control over error messages and recovery.›Varint (LEB128)compression · low: Variable-length integers in 7-bit groups with a continuation bit; small numbers take 1 byte, the wire format of Protobuf, WebAssembly and DWARF.›Advisory file lockinghardware-os · low: Fcntl/flock byte-range and whole-file locks for multi-process access to one filemmap and the page cachehardware-os · low: How read() and mmap reach file data through the kernel page cache, what readahead and madvise do, and why databases use their own buffer pool instead.›B+ treestorage · low: Balanced high-fanout search tree with all values in linked leaves; the default on-disk index for point lookups and range scans.›Hash aggregationstorage · low: GROUP BY via hash tables with partitioning and spill to diskSlotted pagesstorage · low: Fixed-size page layout for variable-length records, with a slot array growing from the front and data from the back; stable record IDs despite compaction.›Write-ahead logstorage · low: Append each change to a checksummed sequential log and fsync it before touching data pages; the basis of crash durability in nearly every database.›Buffer pools for zero-allocation I/Ohardware-os · low: Preallocate a fixed set of aligned I/O buffers and recycle them through a free list, so the hot path never mallocs, faults or unmaps. The bounded count doubles as back pressure.›K way mergesearch-sort · low: Merge k sorted streams with a heap or loser tree (merging iterators)Pattern-defeating quicksort (pdqsor…search-sort · low: Introsort successor: quicksort with adaptive pivots, linear on sorted and equal-heavy input, heapsort fallback; the unstable sort of Go and (until 1.81) Rust.›LRU and CLOCKsystems · low: LRU evicts the least recently used entry via hash map plus linked list; CLOCK approximates it with a reference bit, so hits take no lock.›+ 4 more techniques+ 17 more primitives

Similar systems

Share the most building blocks with this one.

relational-db 37 %btree-engine 30 %query-engine 29 %graph-db 26 %htap-db 24 %