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.7981019e-05
Overall Rank: 6,395 | 57.02%
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,810	An Empirical Evaluation of Columnar Storage Formats	2024	VLDB	7.0064171e-05
8,280	Scaling GPU-Accelerated Databases beyond GPU Memory Size	2025	VLDB	5.3616863e-05
8,577	The FastLanes File Format	2025	VLDB	5.3107348e-05
9,467	HyperBlocker: Accelerating Rule-based Blocking in Entity Resolution using GPUs	2025	VLDB	5.1709969e-05
10,085	LiquidCache: Efficient Pushdown Caching for Cloud-Native Data Analytics	2025	VLDB	5.0806786e-05
10,817	dpKernels: Harvesting DPU Compute Resources for Data-path Efficiency in Cloud Data Processing	2026	VLDB	4.9769913e-05
10,910	Overlay Bitmap Encoding for Efficient Consumption of Apache Parquet Files	2026	VLDB	4.9769913e-05
11,200	Nested Parquet Is Flat, Why Not Use It? How To Scan Nested Data With On-the-Fly Key Generation and Joins	2025	SIGMOD	4.9769913e-05
11,400	GraphAr: An Efficient Storage Scheme for Graph Data in Data Lakes	2025	VLDB	4.9769913e-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.0006897844
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00064013679
23	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00055384955
48	Weaving Relations for Cache Performance	2001	VLDB	0.00043795812
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.0004314366
52	The Snowflake Elastic Data Warehouse	2016	SIGMOD	0.00041210636
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00039236924
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033884854
219	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024367137
460	Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores	2020	VLDB	0.00017850215
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
950	Lakehouse: A New Generation of Open Platforms that Unify Data Warehousing and Advanced Analytics	2021	CIDR	0.00012889569
1,458	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00010583148
1,487	Photon: A Fast Query Engine for Lakehouse Systems	2022	SIGMOD	0.00010516813
1,718	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7983307e-05
2,348	Filter Before You Parse: Faster Analytics on Raw Data with Sparser	2018	VLDB	8.5972138e-05
2,437	Mison: A Fast JSON Parser for Data Analytics	2017	VLDB	8.4668658e-05
3,075	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.6742518e-05
3,520	FlexPushdownDB: Hybrid Pushdown and Caching in a Cloud DBMS	2021	VLDB	7.2326541e-05
5,451	Crystal: A Unified Cache Storage System for Analytical Databases	2021	VLDB	6.1238308e-05

Semantically Similar Papers

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