← Back
Home › Systems › Data processing and pipelines

batch-engine

distributed batch processing engine

Spark, MapReduce

SystemTechniques · 9Primitives · 25 batch-engine Data shuffledistributed · medium: Hash/range repartitioning of intermediate data between workers (exchange operator)Lineage based recoverydistributed · medium: Recompute lost partitions from their recorded transformation lineage instead of replicatingMapreducedistributed · medium: Map, partition, sort/shuffle, reduce with combiners and re-execution of failed tasksExternal 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.›Cardinality estimationstorage · medium: Row-count estimates from histograms, MCVs, sketches and sampling for the optimizerQuery 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.›Speculative executiondistributed · low: Launch backup copies of straggler tasks and keep the first resultTopological sortgraphs · low: Order the vertices of a DAG so every edge points forward; the core of build systems, schedulers and dependency resolution, with cycle detection for free.›Object storagecloud · low: S3-compatible blob storage at cents per GB-month with 11 nines durability; pick by egress price, request price and latency, not by storage price alone.›K way mergesearch-sort · low: Merge k sorted streams with a heap or loser tree (merging iterators)Hash 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.›LZ4compression · low: Byte-aligned LZ77 with no entropy stage; compresses at hundreds of MB/s and decompresses at several GB/s per core, for when speed beats ratio.›Bin packingoptimization · low: Pack items of given sizes into the fewest fixed-capacity bins; sort descending, then first-fit, gives at most 11/9 of optimal and runs in O(n log n).›Columnar file formatstorage · low: Row groups, column chunks, pages, encodings and footer stats (Parquet/ORC style) (listed in Moved to the wiki)Hash aggregationstorage · low: GROUP BY via hash tables with partitioning and spill to diskSort-merge joinstorage · 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.›Fast hash functionsdata-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 partitioningdistributed · 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.›Columnar memory formatstorage · low: In-memory column buffers with validity bitmaps and offsets (Arrow style) for zero-copy exchangeBuffer 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.›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.›HyperLogLogdata-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.›+ 2 more techniques+ 9 more primitives

Similar systems

Share the most building blocks with this one.

query-engine 36 %columnar-warehouse 34 %htap-db 21 %dataframe-engine 21 %query-optimizer 19 %