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
5001
Venue
SIGMOD
Year
2015
Pagerank
5.4548897e-05
Overall Rank
5,532 | 61.52%
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,263 Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation 2016 SIGMOD 0.00012982857
3,416 LeCo: Lightweight Compression via Learning Serial Correlations 2024 SIGMOD 7.1196234e-05
3,608 Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation 2018 SIGMOD 6.924272e-05
4,161 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 2017 SIGMOD 6.3938006e-05
4,602 Accelerating Raw Data Analysis with the ACCORDA Software and Hardware Architecture 2019 VLDB 6.0567387e-05
5,835 Order-Preserving Key Compression for In-Memory Search Trees 2020 SIGMOD 5.30905e-05
7,097 Fast Multi-Column Sorting in Main-Memory Column-Stores 2016 SIGMOD 4.8336115e-05
8,430 Tree-Encoded Bitmaps 2020 SIGMOD 4.5154973e-05
9,906 Rethinking the Encoding of Integers for Scans on Skewed Data 2023 SIGMOD 4.2578595e-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.00048186983
121 Improved Query Performance with Variant Indexes 1997 SIGMOD 0.00045447517
131 Integrating Compression and Execution in Column-Oriented Database Systems 2006 SIGMOD 0.0004370331
241 DB2 with BLU Acceleration: So Much More than Just a Column Store 2013 VLDB 0.00031420034
305 SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units 2009 VLDB 0.00028248614
310 The Vertica Analytic Database: C-Store 7 Years Later 2012 VLDB 0.00028132402
343 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00026768139
588 Practical Skew Handling in Parallel Joins 1992 VLDB 0.00019604754
638 On B-tree Indices for Skewed Distributions 1992 VLDB 0.00018798677
679 Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems 2012 SIGMOD 0.00018215154
861 A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins 1991 VLDB 0.00015848554
897 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00015528028
960 A Comparison of Join Algorithms for Log Processing in MapReduce 2010 SIGMOD 0.00015012242
1,100 Query Optimization In Compressed Database Systems 2001 SIGMOD 0.00014072277
1,134 Dictionary-based Order-preserving String Compression for Main Memory Column Stores 2009 SIGMOD 0.00013761456
1,270 BitWeaving: Fast Scans for Main Memory Data Processing 2013 SIGMOD 0.00012926086
1,334 SkewTune: Mitigating Skew in MapReduce Applications 2012 SIGMOD 0.0001250413
1,471 Adaptive Range Filters for Cold Data: Avoiding Trips to Siberia 2013 VLDB 0.00011830111
1,477 Fine-grained Partitioning for Aggressive Data Skipping 2014 SIGMOD 0.00011770865
1,487 Scuba: Diving into Data at Facebook 2013 VLDB 0.00011701099
1,618 Row-wise Parallel Predicate Evaluation 2008 VLDB 0.00011114015
1,731 Fast Updates on Read-Optimized Databases Using Multi-Core CPUs 2012 VLDB 0.0001073454
1,915 Handling Data Skew in Parallel Joins in Shared-Nothing Systems 2008 SIGMOD 0.00010104123
2,372 Predictable Performance for Unpredictable Workloads 2009 VLDB 8.947963e-05
2,412 WideTable: An Accelerator for Analytical Data Processing 2014 VLDB 8.8726508e-05
2,882 Database Compression on Graphics Processors 2010 VLDB 7.9661218e-05
3,856 Bit-Sliced Index Arithmetic 2001 SIGMOD 6.6942616e-05
5,568 Efficient outer join data skew handling in parallel DBMS 2009 VLDB 5.4301489e-05
5,596 Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps 2006 VLDB 5.4181535e-05
5,670 Joins on Encoded and Partitioned Data 2014 VLDB 5.3804618e-05
6,103 Crescando 2010 SIGMOD 5.2086701e-05
6,214 Skew Handling Techniques in Sort-Merge Join 2002 SIGMOD 5.1546943e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
5,596 Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps 2006 VLDB 5.4181535e-05
8,578 Robust and Budget-Constrained Encoding Configurations for In-Memory Database Systems 2022 VLDB 4.4923477e-05
1,618 Row-wise Parallel Predicate Evaluation 2008 VLDB 0.00011114015
6,367 Good to the Last Bit: Data-Driven Encoding with CodecDB 2021 SIGMOD 5.0941072e-05
8,487 Adaptive Compression for Fast Scans on String Columns 2021 SIGMOD 4.4999394e-05
7,427 Selection Pushdown in Column Stores using Bit Manipulation Instructions 2023 SIGMOD 4.7327406e-05
5,898 Column Partition and Permutation for Run Length Encoding in Columnar Databases 2020 SIGMOD 5.2839046e-05
1,905 How to Barter Bits for Chronons: Compression and Bandwidth Trade Offs for Database Scans 2007 SIGMOD 0.00010138448
3,608 Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation 2018 SIGMOD 6.924272e-05
9,906 Rethinking the Encoding of Integers for Scans on Skewed Data 2023 SIGMOD 4.2578595e-05