← Back
Home › Systems › Databases and storage engines

columnar-warehouse

columnar analytics warehouse

ClickHouse, Snowflake

SystemTechniques · 11Primitives · 37 columnar-warehouse Data shuffledistributed · medium: Hash/range repartitioning of intermediate data between workers (exchange operator)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.›Cardinality estimationstorage · medium: Row-count estimates from histograms, MCVs, sketches and sampling for the optimizerColumnar storagestorage · medium: Store each column contiguously so analytic scans read only the columns they need, compress well and run as tight SIMD loops.›LSM compactionstorage · medium: Compaction policies (leveled, tiered, time-window, FIFO) decide which sorted files to merge and when, trading write, read and space amplification and purging tombstones.›Query compilationstorage · medium: Compile query pipelines into tight machine-code loops (data-centric produce/consume, LLVM or template JIT) instead of interpreting operatorsQuery optimizerstorage · medium: Cost-based plan search: join ordering (DP/greedy), rewrites, access path selectionHyperLogLogdata-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.›Bit packing and PFORcompression · low: Store blocks of integers with exactly b bits each and patch rare outliers separately (PFOR); the fastest integer codec family, billions of values per second.›Delta encodingcompression · low: Store differences between consecutive values instead of the values, turning sorted IDs, timestamps and counters into small numbers that pack into few bits.›Dictionary encodingcompression · low: Map values to small integer codes via a dictionary for compact, comparable columnsZone 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.›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.›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.›Zstandard (zstd)compression · low: LZ77 plus Huffman and FSE entropy coding, with levels from LZ4-like speed to xz-like ratio, all decoding at about 1-2 GB/s.›SIMD 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.›Top-k selectionsearch-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 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 diskLate materializationstorage · low: Carry row ids through operators and fetch other columns only for surviving rowsFast 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.›+ 4 more techniques+ 21 more primitives

Similar systems

Share the most building blocks with this one.

log-analytics 38 %query-engine 34 %batch-engine 34 %htap-db 30 %query-optimizer 28 %

In-house systems

Named systems of this kind at large companies, with their paper or write-up.

MesaAlphabet