mhtirogla
Home
Systems
API
Pricing
About
Log in
← Back
Home
›
Systems
›
Databases and storage engines
query-engine
federated SQL query engine
Trino, DataFusion
System
Techniques · 10
Primitives · 25
query-engine
Data shuffle
distributed · medium: Hash/range repartitioning of intermediate data between workers (exchange operator)
External merge sort
search-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.
›
Cardinality estimation
storage · medium: Row-count estimates from histograms, MCVs, sketches and sampling for the optimizer
Federated query planning
storage · medium: Split one query across heterogeneous sources, pushing down what each can execute
Morsel driven parallelism
storage · medium: Split pipelines into small morsels scheduled NUMA-aware across worker threads
Query optimizer
storage · medium: Cost-based plan search: join ordering (DP/greedy), rewrites, access path selection
Vectorized execution
storage · medium: Query operators pass batches of about 1-2K values per column instead of single tuples, amortizing interpretation overhead and enabling tight SIMD loops.
›
Columnar memory format
storage · low: In-memory column buffers with validity bitmaps and offsets (Arrow style) for zero-copy exchange
Predicate pushdown
storage · low: Move filters and projections into scans and remote sources
Hash join
storage · 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.
›
Recursive-descent parsing
compilers · low: Hand-written top-down parser with one function per grammar rule; simple, fast, with full control over error messages and recovery.
›
Bloom filter
data-structures · low: Bit array answering "definitely not present" or "probably present" in about 10 bits per key for 1 % false positives; inserts are cheap, deletes impossible.
›
Top-k selection
search-sort · low: Keep the k best of n items without sorting all n - bounded min-heap for streams, quickselect for arrays, threshold pruning to skip most items.
›
Columnar file format
storage · low: Row groups, column chunks, pages, encodings and footer stats (Parquet/ORC style) (listed in Moved to the wiki)
Hash aggregation
storage · low: GROUP BY via hash tables with partitioning and spill to disk
Sort-merge join
storage · low: Sort both inputs on the key, then advance two cursors in lockstep and emit matching runs; cheap on sorted inputs and good for range joins.
›
Zone maps
storage · low: Per-block min/max (and sparse primary) indexes to skip data during scans
Fast hash functions
data-structures · low: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.
›
Range partitioning
distributed · low: Cut the sorted key space into contiguous half-open ranges kept in a boundary map; split hot or big ranges, merge small ones, move ranges between nodes.
›
Buffer pools for zero-allocation I/O
hardware-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 merge
search-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.
›
HyperLogLog
data-structures · low: Counts distinct elements in kilobytes with about 1 % error by tracking the longest run of leading zero bits in hashed values per bucket.
›
+ 3 more techniques
+ 9 more primitives
System
Techniques · 10
Primitives · 25
query-engine
Data shuffle
distributed · medium: Hash/range repartitioning of intermediate data between workers (exchange operator)
External merge sort
search-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.
›
Cardinality estimation
storage · medium: Row-count estimates from histograms, MCVs, sketches and sampling for the optimizer
Federated query planning
storage · medium: Split one query across heterogeneous sources, pushing down what each can execute
Morsel driven parallelism
storage · medium: Split pipelines into small morsels scheduled NUMA-aware across worker threads
Query optimizer
storage · medium: Cost-based plan search: join ordering (DP/greedy), rewrites, access path selection
Vectorized execution
storage · medium: Query operators pass batches of about 1-2K values per column instead of single tuples, amortizing interpretation overhead and enabling tight SIMD loops.
›
Work-stealing deque
concurrency · medium: Per-worker deque: the owner pushes and pops at the bottom without contention, idle workers steal from the top; the core of Rayon, Tokio and Go.
›
Join order dynamic programming
storage · medium: DPccp and DPhyp enumeration of join orders with cost models; greedy fallback for many joins
Subquery decorrelation
storage · medium: Unnest correlated subqueries into joins via dependent join and magic sets
Columnar memory format
storage · low: In-memory column buffers with validity bitmaps and offsets (Arrow style) for zero-copy exchange
Predicate pushdown
storage · low: Move filters and projections into scans and remote sources
Hash join
storage · 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.
›
Recursive-descent parsing
compilers · low: Hand-written top-down parser with one function per grammar rule; simple, fast, with full control over error messages and recovery.
›
Bloom filter
data-structures · low: Bit array answering "definitely not present" or "probably present" in about 10 bits per key for 1 % false positives; inserts are cheap, deletes impossible.
›
Top-k selection
search-sort · low: Keep the k best of n items without sorting all n - bounded min-heap for streams, quickselect for arrays, threshold pruning to skip most items.
›
Columnar file format
storage · low: Row groups, column chunks, pages, encodings and footer stats (Parquet/ORC style) (listed in Moved to the wiki)
Hash aggregation
storage · low: GROUP BY via hash tables with partitioning and spill to disk
Sort-merge join
storage · low: Sort both inputs on the key, then advance two cursors in lockstep and emit matching runs; cheap on sorted inputs and good for range joins.
›
Zone maps
storage · low: Per-block min/max (and sparse primary) indexes to skip data during scans
Fast hash functions
data-structures · low: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.
›
Range partitioning
distributed · low: Cut the sorted key space into contiguous half-open ranges kept in a boundary map; split hot or big ranges, merge small ones, move ranges between nodes.
›
Buffer pools for zero-allocation I/O
hardware-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 merge
search-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.
›
HyperLogLog
data-structures · low: Counts distinct elements in kilobytes with about 1 % error by tracking the longest run of leading zero bits in hashed values per bucket.
›
Quantile sketches
data-structures · low: Mergeable quantile sketches: t-digest, DDSketch, HDR histograms
Reservoir sampling
data-structures · low: Uniform k-sample from a stream of unknown length (Algorithm R/L)
Numa aware allocation
hardware-os · low: Allocate memory and pin threads on the local NUMA node; first-touch and interleave policies
Partition pruning
storage · low: Skip whole partitions using partition transforms and predicate analysis
Relational algebra
storage · low: Relational operators and equivalence rules: selection pushdown, join reordering, projections
Epoch-based reclamation
concurrency · low: Threads announce a global epoch while touching shared lock-free data; garbage retired in epoch e is freed once the epoch reaches e + 2.
›
Memory ordering
concurrency · low: What Relaxed, Acquire, Release and SeqCst atomics actually guarantee, what they cost on x86 and ARM, and which one each pattern needs.
›
d-ary heap
data-structures · low: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.
›
fsync, O_DSYNC and O_DIRECT
hardware-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.
›
Copy for AI
Similar systems
Share the most building blocks with this one.
dataframe-engine
36 %
batch-engine
36 %
columnar-warehouse
34 %
embedded-sql
29 %
query-optimizer
28 %