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: 6743
Venue: SIGMOD
Year: 2023
Pagerank: 5.6932481e-05
Overall Rank: 7,139 | 51.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 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,877	An Empirical Evaluation of Columnar Storage Formats	2024	VLDB	7.0532293e-05
9,038	The FastLanes File Format	2025	VLDB	5.3270943e-05
9,997	HyperBlocker: Accelerating Rule-based Blocking in Entity Resolution using GPUs	2025	VLDB	5.1814573e-05
10,771	Nested Parquet Is Flat, Why Not Use It? How To Scan Nested Data With On-the-Fly Key Generation and Joins	2025	SIGMOD	5.093636e-05
10,985	Scaling GPU-Accelerated Databases beyond GPU Memory Size	2025	VLDB	5.093636e-05
11,030	GraphAr: An Efficient Storage Scheme for Graph Data in Data Lakes	2025	VLDB	5.093636e-05
11,078	LiquidCache: Efficient Pushdown Caching for Cloud-Native Data Analytics	2025	VLDB	5.093636e-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.00069513174
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.0006312782
24	Spark SQL: Relational Data Processing in Spark	2015	SIGMOD	0.00054865648
49	Weaving Relations for Cache Performance	2001	VLDB	0.00043781096
51	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.0004291425
60	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.0003955489
66	The Snowflake Elastic Data Warehouse	2016	SIGMOD	0.00038561587
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
216	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024498128
520	Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores	2020	VLDB	0.00017136828
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
1,138	Lakehouse: A New Generation of Open Platforms that Unify Data Warehousing and Advanced Analytics	2021	CIDR	0.00012023643
1,450	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00010746714
1,761	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.8154969e-05
1,824	Photon: A Fast Query Engine for Lakehouse Systems	2022	SIGMOD	9.6734544e-05
2,391	Mison: A Fast JSON Parser for Data Analytics	2017	VLDB	8.6413407e-05
2,414	Filter Before You Parse: Faster Analytics on Raw Data with Sparser	2018	VLDB	8.6078841e-05
3,137	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.7204167e-05
3,632	FlexPushdownDB: Hybrid Pushdown and Caching in a Cloud DBMS	2021	VLDB	7.2368817e-05
5,348	Crystal: A Unified Cache Storage System for Analytical Databases	2021	VLDB	6.2562688e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD
2	7,242	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD
3	5,622	Good to the Last Bit: Data-Driven Encoding with CodecDB	2021	SIGMOD
4	10,056	Rethinking the Encoding of Integers for Scans on Skewed Data	2023	SIGMOD
5	9,806	BIPie: Fast Selection and Aggregation on Encoded Data using Operator Specialization	2018	SIGMOD
6	1,450	Row-wise Parallel Predicate Evaluation	2008	VLDB
7	3,877	An Empirical Evaluation of Columnar Storage Formats	2024	VLDB
8	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
9	9,754	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD
10	2,937	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD