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.8119682e-05
Overall Rank: 2,954 | 80.15%
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,974	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	9.2806652e-05
2,237	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7738349e-05
3,075	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.6742518e-05
3,285	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	7.4525495e-05
3,810	An Empirical Evaluation of Columnar Storage Formats	2024	VLDB	7.0064171e-05
4,638	A Deep Dive into Common Open Formats for Analytical DBMSs	2023	VLDB	6.4901967e-05
4,755	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.4309508e-05
5,619	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.0602908e-05
5,895	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.9534254e-05
6,240	Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses	2024	SIGMOD	5.8373399e-05
6,447	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	5.7798274e-05
7,486	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.5102404e-05
8,207	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.3763264e-05
8,500	Tree-Encoded Bitmaps	2020	SIGMOD	5.3286931e-05
8,541	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	5.3190248e-05
8,559	F3: The Open-Source Data File Format for the Future	2026	SIGMOD	5.3141911e-05
8,587	Conditional Cuckoo Filters	2021	SIGMOD	5.3075325e-05
10,602	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.9769913e-05
10,666	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	4.9769913e-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.00041210636
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00039236924
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033459417
163	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00027480091
178	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.00026620521
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024485637
219	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024367137
287	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022001327
327	Impala: A Modern, Open-Source SQL Engine for Hadoop	2015	CIDR	0.00020942751
432	Shark: SQL and Rich Analytics at Scale	2013	SIGMOD	0.00018331051
627	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015454197
873	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00013334067
910	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013122392
1,036	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00012372946
1,458	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00010583148
1,531	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010344951
1,718	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7983307e-05
2,157	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	8.9425625e-05
2,187	Database Compression on Graphics Processors	2010	VLDB	8.891124e-05
3,597	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.1759026e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.222614e-05
6,788	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD	5.6808999e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,984	Fingerprints for Compressed Columnar Data Search	2019	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,447	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB
5	6,108	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,531	Column Imprints: A Secondary Index Structure	2013	SIGMOD
8	6,395	Selection Pushdown in Column Stores using Bit Manipulation Instructions	2023	SIGMOD
9	12,076	Workload-Aware Column Imprints	2020	SIGMOD
10	1,458	Row-wise Parallel Predicate Evaluation	2008	VLDB