Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation

Summary: Column Sketches use lossy, fixed-width codes to map values, enabling predicate evaluation with most results from compressed data. Works across column/row/hybrid layouts and delivers gains: 3x-6x numeric, 2.7x categorical, and 1.4-4.8x vs prior accelerators. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: he2c2344173f17afb
Venue: SIGMOD
Year: 2018
Pagerank: 7.8153507e-05
Overall Rank: 2,952 | 80.16%
DOI: 10.1145/3183713.3196911

Incoming Non-self Citations Over Time

Authors

1. Brian Hentschel (Harvard University)
2. Michael S. Kester (Harvard University)
3. Stratos Idreos (Harvard University)

BibTeX Citation

@inproceedings{hentschel_sigmod18,
        title = {{Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation}},
        author = {Hentschel, Brian and Kester, Michael S. and Idreos, Stratos},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3196911},
        url = {https://dl.acm.org/doi/10.1145/3183713.3196911},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,973	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	9.2834606e-05
2,238	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7751619e-05
3,073	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.6777283e-05
3,285	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	7.4559907e-05
3,808	An Empirical Evaluation of Columnar Storage Formats	2024	VLDB	7.0097354e-05
4,635	A Deep Dive into Common Open Formats for Analytical DBMSs	2023	VLDB	6.4932705e-05
4,756	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.43221e-05
5,618	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.0630987e-05
5,902	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.9536872e-05
6,240	Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses	2024	SIGMOD	5.8382355e-05
6,444	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	5.7825648e-05
7,481	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.5128501e-05
8,199	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.3788727e-05
8,500	Tree-Encoded Bitmaps	2020	SIGMOD	5.3296886e-05
8,533	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	5.3215439e-05
8,552	F3: The Open-Source Data File Format for the Future	2026	SIGMOD	5.316708e-05
8,580	Conditional Cuckoo Filters	2021	SIGMOD	5.3100462e-05
10,591	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.9793485e-05
10,655	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
52	The Snowflake Elastic Data Warehouse	2016	SIGMOD	0.00041219077
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.000392237
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033460288
163	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.0002749118
179	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.00026611886
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024485024
219	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024363532
287	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00021970198
327	Impala: A Modern, Open-Source SQL Engine for Hadoop	2015	CIDR	0.0002095191
432	Shark: SQL and Rich Analytics at Scale	2013	SIGMOD	0.00018339357
627	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015460957
873	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00013338838
910	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013123912
1,036	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00012377471
1,459	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00010585108
1,529	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010348765
1,723	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7931223e-05
2,155	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	8.9456729e-05
2,185	Database Compression on Graphics Processors	2010	VLDB	8.8948351e-05
3,599	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.1773938e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2250048e-05
6,782	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD	5.6835894e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,608	Adaptive Compression for Fast Scans on String Columns	2021	SIGMOD
2	61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD
3	634	Performance Tradeoffs in Read-Optimized Databases	2006	VLDB
4	6,444	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB
5	6,106	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
6	5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD
7	1,529	Column Imprints: A Secondary Index Structure	2013	SIGMOD
8	6,392	Selection Pushdown in Column Stores using Bit Manipulation Instructions	2023	SIGMOD
9	12,070	Workload-Aware Column Imprints	2020	SIGMOD
10	1,459	Row-wise Parallel Predicate Evaluation	2008	VLDB