← Back
Home › Systems › Databases and storage engines

dataframe-engine

in-process columnar dataframe engine

Polars, Arrow

SystemTechniques · 8Primitives · 24 dataframe-engine Work-stealing dequeconcurrency · 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.›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.›Morsel driven parallelismstorage · medium: Split pipelines into small morsels scheduled NUMA-aware across worker threadsQuery 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.›Cardinality estimationstorage · medium: Row-count estimates from histograms, MCVs, sketches and sampling for the optimizerJoin order dynamic programmingstorage · medium: DPccp and DPhyp enumeration of join orders with cost models; greedy fallback for many joinsPattern-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.›Predicate pushdownstorage · low: Move filters and projections into scans and remote sourcesHash 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.›Dictionary encodingcompression · low: Map values to small integer codes via a dictionary for compact, comparable columnsSIMD programminghardware-os · low: Process 4-16 lanes per instruction with AVX2, AVX-512 or NEON via Rust std::arch, with runtime dispatch and a portable fallback.›Zero-copy serializationnetworking · low: Wire formats laid out like in-memory structs (FlatBuffers, Cap'n Proto, SBE, rkyv) so readers access fields in place with no decode pass or allocation.›Radix sortsearch-sort · low: Non-comparison sort that distributes keys by 8-bit digits; several times faster than comparison sorts on large arrays of integers, floats or fixed-size keys.›Columnar file formatstorage · low: Row groups, column chunks, pages, encodings and footer stats (Parquet/ORC style) (listed in Moved to the wiki)Columnar memory formatstorage · low: In-memory column buffers with validity bitmaps and offsets (Arrow style) for zero-copy exchangeHash aggregationstorage · low: GROUP BY via hash tables with partitioning and spill to diskWindow functionsstorage · low: ROW_NUMBER, rank, running and frame aggregates via sort and segment treesArena allocatorsystems · low: Allocate by bumping a pointer through big chunks and free everything at once: a few instructions per allocation for objects sharing a lifetime.›Epoch-based reclamationconcurrency · 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 orderingconcurrency · low: What Relaxed, Acquire, Release and SeqCst atomics actually guarantee, what they cost on x86 and ARM, and which one each pattern needs.›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)+ 1 more techniques+ 8 more primitives

Similar systems

Share the most building blocks with this one.

query-engine 36 %columnar-warehouse 26 %batch-engine 21 %embedded-sql 20 %htap-db 17 %