Rethinking the Encoding of Integers for Scans on Skewed Data

Summary: Forward encodings address skew in bit-parallel scans by moving pruning-relevant bits toward the MSB. Data Forward Encoding and Extended Data Forward Encoding reduce fetch penalties, delivering up to 1.4x faster scans and 1.3x faster fetches on data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6820
Venue: SIGMOD
Year: 2023
Pagerank: 5.1676234e-05
Overall Rank: 10,056 | 31.01%
DOI: 10.1145/3626751

Incoming Non-self Citations Over Time

Authors

1. Martin Prammer (University of Wisconsin)
2. Jignesh M. Patel (Carnegie Mellon University)

BibTeX Citation

@inproceedings{prammer_sigmod23,
        title = {{Rethinking the Encoding of Integers for Scans on Skewed Data}},
        author = {Prammer, Martin and Patel, Jignesh M.},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3626751},
        url = {https://dl.acm.org/doi/10.1145/3626751},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,038	The FastLanes File Format	2025	VLDB	5.3270943e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
216	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024498128
293	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022259273
870	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.0001350293
1,315	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.00011181796
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
2,156	Quickstep: A Data Platform Based on the Scaling-Up Approach	2018	VLDB	9.0635624e-05
2,599	WideTable: An Accelerator for Analytical Data Processing	2014	VLDB	8.3583572e-05
3,597	Bit-Sliced Index Arithmetic	2001	SIGMOD	7.2721197e-05
5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.3573169e-05
5,622	Good to the Last Bit: Data-Driven Encoding with CodecDB	2021	SIGMOD	6.1461066e-05
5,715	Design and Evaluation of Storage Organizations for Read-Optimized Main Memory Databases	2013	VLDB	6.1105343e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	481	Practical Skew Handling in Parallel Joins	1992	VLDB
2	1,450	Row-wise Parallel Predicate Evaluation	2008	VLDB
3	1,950	How to Barter Bits for Chronons: Compression and Bandwidth Trade Offs for Database Scans	2007	SIGMOD
4	1,448	Skew in Parallel Query Processing	2014	PODS
5	5,472	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB
6	5,622	Good to the Last Bit: Data-Driven Encoding with CodecDB	2021	SIGMOD
7	1,464	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD
8	870	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD
9	7,139	Selection Pushdown in Column Stores using Bit Manipulation Instructions	2023	SIGMOD
10	5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD