Selection Pushdown in Column Stores using Bit Manipulation Instructions

Summary: Generic predicate pushdown over encoded columnar data enabling direct selection without decoding via Bit Manipulation Instructions (BMI). Evaluations on Parquet/TPC-H and Spark show up to 10x scan speedups and 5.5x end-to-end with complex joins. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h635723dedfe69101
Venue: SIGMOD
Year: 2023
Pagerank: 5.800848e-05
Overall Rank: 6,392 | 57.03%
DOI: 10.1145/3589323

Incoming Non-self Citations Over Time

Authors

1. Yinan Li (Microsoft)
2. Jianan Lu (Princeton University)
3. Badrish Chandramouli (Microsoft)

BibTeX Citation

@inproceedings{li_sigmod23,
        title = {{Selection Pushdown in Column Stores using Bit Manipulation Instructions}},
        author = {Li, Yinan and Lu, Jianan and Chandramouli, Badrish},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3589323},
        url = {https://dl.acm.org/doi/10.1145/3589323},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,808	An Empirical Evaluation of Columnar Storage Formats	2024	VLDB	7.0097354e-05
8,274	Scaling GPU-Accelerated Databases beyond GPU Memory Size	2025	VLDB	5.3642256e-05
8,569	The FastLanes File Format	2025	VLDB	5.3132501e-05
9,458	HyperBlocker: Accelerating Rule-based Blocking in Entity Resolution using GPUs	2025	VLDB	5.173446e-05
10,080	LiquidCache: Efficient Pushdown Caching for Cloud-Native Data Analytics	2025	VLDB	5.0830849e-05
10,807	dpKernels: Harvesting DPU Compute Resources for Data-path Efficiency in Cloud Data Processing	2026	VLDB	4.9793485e-05
10,901	Overlay Bitmap Encoding for Efficient Consumption of Apache Parquet Files	2026	VLDB	4.9793485e-05
11,191	Nested Parquet Is Flat, Why Not Use It? How To Scan Nested Data With On-the-Fly Key Generation and Joins	2025	SIGMOD	4.9793485e-05
11,394	GraphAr: An Efficient Storage Scheme for Graph Data in Data Lakes	2025	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00068998927
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00064031282
23	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00055406774
48	Weaving Relations for Cache Performance	2001	VLDB	0.00043805923
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.00043160717
52	The Snowflake Elastic Data Warehouse	2016	SIGMOD	0.00041219077
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.000392237
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
219	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024363532
459	Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores	2020	VLDB	0.00017856221
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
950	Lakehouse: A New Generation of Open Platforms that Unify Data Warehousing and Advanced Analytics	2021	CIDR	0.00012895553
1,459	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00010585108
1,487	Photon: A Fast Query Engine for Lakehouse Systems	2022	SIGMOD	0.00010521722
1,723	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7931223e-05
2,347	Filter Before You Parse: Faster Analytics on Raw Data with Sparser	2018	VLDB	8.6012176e-05
2,436	Mison: A Fast JSON Parser for Data Analytics	2017	VLDB	8.4708399e-05
3,073	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.6777283e-05
3,520	FlexPushdownDB: Hybrid Pushdown and Caching in a Cloud DBMS	2021	VLDB	7.2360022e-05
5,446	Crystal: A Unified Cache Storage System for Analytical Databases	2021	VLDB	6.1266228e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,495	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD
2	10,241	Rethinking the Encoding of Integers for Scans on Skewed Data	2023	SIGMOD
3	5,471	Good to the Last Bit: Data-Driven Encoding with CodecDB	2021	SIGMOD
4	9,981	BIPie: Fast Selection and Aggregation on Encoded Data using Operator Specialization	2018	SIGMOD
5	1,459	Row-wise Parallel Predicate Evaluation	2008	VLDB
6	3,808	An Empirical Evaluation of Columnar Storage Formats	2024	VLDB
7	6,106	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
8	9,932	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD
9	2,952	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD
10	10,901	Overlay Bitmap Encoding for Efficient Consumption of Apache Parquet Files	2026	VLDB