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: 5619
Venue: SIGMOD
Year: 2018
Pagerank: 7.9435581e-05
Overall Rank: 2,937 | 79.86%
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
2,023	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	9.2950046e-05
2,213	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.9410226e-05
3,137	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.7204167e-05
3,510	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	7.3561488e-05
3,877	An Empirical Evaluation of Columnar Storage Formats	2024	VLDB	7.0532293e-05
4,782	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.5115802e-05
5,037	A Deep Dive into Common Open Formats for Analytical DBMSs	2023	VLDB	6.3914026e-05
5,512	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.1913331e-05
6,434	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.8799421e-05
6,602	Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses	2024	SIGMOD	5.8246665e-05
7,412	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	5.624223e-05
7,960	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.5181056e-05
8,056	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.4983582e-05
8,349	Tree-Encoded Bitmaps	2020	SIGMOD	5.4460774e-05
8,370	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	5.4409293e-05
8,413	Conditional Cuckoo Filters	2021	SIGMOD	5.4306049e-05
9,277	F3: The Open-Source Data File Format for the Future	2026	SIGMOD	5.2937431e-05
10,395	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	5.093636e-05
10,468	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	5.093636e-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
60	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.0003955489
66	The Snowflake Elastic Data Warehouse	2016	SIGMOD	0.00038561587
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
165	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00027693424
186	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.00026182534
216	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024498128
227	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00023958508
293	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022259273
330	Impala: A Modern, Open-Source SQL Engine for Hadoop	2015	CIDR	0.0002104801
425	Shark: SQL and Rich Analytics at Scale	2013	SIGMOD	0.00018704491
634	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015533814
870	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.0001350293
925	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013182044
1,044	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.0001244236
1,450	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00010746714
1,507	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.0001054177
1,761	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.8154969e-05
2,150	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	9.081101e-05
2,232	Database Compression on Graphics Processors	2010	VLDB	8.8970926e-05
3,598	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.2718988e-05
5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.3573169e-05
6,653	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD	5.8138531e-05

Semantically Similar Papers

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