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.7894987e-05
Overall Rank: 2,965 | 80.13%
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,981	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	9.2505963e-05
2,249	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7479608e-05
3,081	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.6515625e-05
3,297	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	7.4280812e-05
3,809	An Empirical Evaluation of Columnar Storage Formats	2024	VLDB	6.9890843e-05
4,373	A Deep Dive into Common Open Formats for Analytical DBMSs	2023	VLDB	6.6191786e-05
4,773	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.4102054e-05
5,632	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.0402517e-05
5,911	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.9338021e-05
6,250	Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses	2024	SIGMOD	5.818039e-05
6,459	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	5.7607157e-05
7,505	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.4920201e-05
8,222	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.3585489e-05
8,516	Tree-Encoded Bitmaps	2020	SIGMOD	5.3110731e-05
8,560	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	5.3014368e-05
8,578	F3: The Open-Source Data File Format for the Future	2026	SIGMOD	5.2966191e-05
8,604	Conditional Cuckoo Filters	2021	SIGMOD	5.2899825e-05
10,664	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.9605343e-05
10,727	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	4.9605343e-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.00041439488
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00039323387
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033376274
161	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00027629724
177	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.00026571747
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024446892
218	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024342426
289	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00021955394
327	Impala: A Modern, Open-Source SQL Engine for Hadoop	2015	CIDR	0.00020904249
436	Shark: SQL and Rich Analytics at Scale	2013	SIGMOD	0.00018274105
627	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015430074
871	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00013313281
912	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013092547
1,039	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00012349128
1,461	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00010557729
1,532	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010312002
1,720	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7828414e-05
2,104	Database Compression on Graphics Processors	2010	VLDB	9.0262021e-05
2,168	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	8.9159881e-05
3,606	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.1528863e-05
5,236	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2037372e-05
6,803	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD	5.6621153e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,019	Fingerprints for Compressed Columnar Data Search	2019	SIGMOD
2	61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD
3	635	Performance Tradeoffs in Read-Optimized Databases	2006	VLDB
4	6,459	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB
5	6,122	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
6	5,236	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD
7	1,532	Column Imprints: A Secondary Index Structure	2013	SIGMOD
8	6,400	Selection Pushdown in Column Stores using Bit Manipulation Instructions	2023	SIGMOD
9	12,120	Workload-Aware Column Imprints	2020	SIGMOD
10	1,461	Row-wise Parallel Predicate Evaluation	2008	VLDB