Database Paper Browser

Back to papers

A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew

Summary: Padded encoding assigns shorter codes to frequent values, preserves code order, and pads to fixed-length blocks so predicates run on compressed codes in vertical bit-parallel scans. By exploiting data and predicate skew, it enables early pruning and reduces memory access, with an O(n^3) algorithm to compute the optimal encoding for n distinct values. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5002
Venue
SIGMOD
Year
2015
Pagerank
5.4501856e-05
Overall Rank
5,541 | 61.50%
DOI
10.1145/2723372.2737787

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank Citing Paper Year Venue Pagerank
1,260 Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation 2016 SIGMOD 0.00012990853
3,419 LeCo: Lightweight Compression via Learning Serial Correlations 2024 SIGMOD 7.1127752e-05
3,611 Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation 2018 SIGMOD 6.9178844e-05
4,160 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 2017 SIGMOD 6.3886736e-05
4,603 Accelerating Raw Data Analysis with the ACCORDA Software and Hardware Architecture 2019 VLDB 6.0515823e-05
5,847 Order-Preserving Key Compression for In-Memory Search Trees 2020 SIGMOD 5.3040014e-05
7,095 Fast Multi-Column Sorting in Main-Memory Column-Stores 2016 SIGMOD 4.8289712e-05
8,424 Tree-Encoded Bitmaps 2020 SIGMOD 4.5111681e-05
9,905 Rethinking the Encoding of Integers for Scans on Skewed Data 2023 SIGMOD 4.2537799e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 32 of 32 cited papers.

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

Rank Cited Paper Year Venue Pagerank
109 Dremel: Interactive Analysis of Web-Scale Datasets 2010 VLDB 0.00048217028
121 Improved Query Performance with Variant Indexes 1997 SIGMOD 0.00045429472
132 Integrating Compression and Execution in Column-Oriented Database Systems 2006 SIGMOD 0.00043697853
241 DB2 with BLU Acceleration: So Much More than Just a Column Store 2013 VLDB 0.00031314629
307 SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units 2009 VLDB 0.00028226342
310 The Vertica Analytic Database: C-Store 7 Years Later 2012 VLDB 0.0002815547
343 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00026756534
548 Practical Skew Handling in Parallel Joins 1992 VLDB 0.00020369531
639 On B-tree Indices for Skewed Distributions 1992 VLDB 0.00018782897
679 Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems 2012 SIGMOD 0.00018211621
852 A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins 1991 VLDB 0.00015896035
896 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00015486851
962 A Comparison of Join Algorithms for Log Processing in MapReduce 2010 SIGMOD 0.00015003834
1,098 Query Optimization In Compressed Database Systems 2001 SIGMOD 0.00014070252
1,134 Dictionary-based Order-preserving String Compression for Main Memory Column Stores 2009 SIGMOD 0.00013751593
1,267 BitWeaving: Fast Scans for Main Memory Data Processing 2013 SIGMOD 0.00012917585
1,339 SkewTune: Mitigating Skew in MapReduce Applications 2012 SIGMOD 0.00012492978
1,468 Adaptive Range Filters for Cold Data: Avoiding Trips to Siberia 2013 VLDB 0.00011831457
1,473 Fine-grained Partitioning for Aggressive Data Skipping 2014 SIGMOD 0.00011786148
1,488 Scuba: Diving into Data at Facebook 2013 VLDB 0.00011690191
1,622 Row-wise Parallel Predicate Evaluation 2008 VLDB 0.00011104582
1,726 Fast Updates on Read-Optimized Databases Using Multi-Core CPUs 2012 VLDB 0.00010734339
1,919 Handling Data Skew in Parallel Joins in Shared-Nothing Systems 2008 SIGMOD 0.00010097452
2,372 Predictable Performance for Unpredictable Workloads 2009 VLDB 8.940791e-05
2,409 WideTable: An Accelerator for Analytical Data Processing 2014 VLDB 8.867144e-05
2,890 Database Compression on Graphics Processors 2010 VLDB 7.9586083e-05
3,858 Bit-Sliced Index Arithmetic 2001 SIGMOD 6.6893766e-05
5,576 Efficient outer join data skew handling in parallel DBMS 2009 VLDB 5.4251727e-05
5,605 Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps 2006 VLDB 5.413565e-05
5,677 Joins on Encoded and Partitioned Data 2014 VLDB 5.376511e-05
6,107 Crescando 2010 SIGMOD 5.2037634e-05
6,212 Skew Handling Techniques in Sort-Merge Join 2002 SIGMOD 5.1499439e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
5,605 Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps 2006 VLDB 5.413565e-05
8,575 Robust and Budget-Constrained Encoding Configurations for In-Memory Database Systems 2022 VLDB 4.4880409e-05
1,622 Row-wise Parallel Predicate Evaluation 2008 VLDB 0.00011104582
6,366 Good to the Last Bit: Data-Driven Encoding with CodecDB 2021 SIGMOD 5.0892171e-05
8,444 Adaptive Compression for Fast Scans on String Columns 2021 SIGMOD 4.5043421e-05
7,427 Selection Pushdown in Column Stores using Bit Manipulation Instructions 2023 SIGMOD 4.7282014e-05
5,879 Column Partition and Permutation for Run Length Encoding in Columnar Databases 2020 SIGMOD 5.2875479e-05
1,908 How to Barter Bits for Chronons: Compression and Bandwidth Trade Offs for Database Scans 2007 SIGMOD 0.00010130401
3,611 Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation 2018 SIGMOD 6.9178844e-05
9,905 Rethinking the Encoding of Integers for Scans on Skewed Data 2023 SIGMOD 4.2537799e-05