Query Optimization In Compressed Database Systems

Summary: Proposes attribute-level compression via Hierarchical Dictionary Encoding for string-valued attributes and a compression-aware optimizer. Shows eager vs. lazy decompression is suboptimal; provides one provably optimal and two fast heuristic plan-selection algorithms, with TPC-H experiments achieving up to an order-of-magnitude speedup. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3276
Venue: SIGMOD
Year: 2001
Pagerank: 0.00014070252
Overall Rank: 1,098 | 92.38%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
132	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00043697853
903	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00015449454
1,134	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013751593
1,908	How to Barter Bits for Chronons: Compression and Bandwidth Trade Offs for Database Scans	2007	SIGMOD	0.00010130401
2,409	WideTable: An Accelerator for Analytical Data Processing	2014	VLDB	8.867144e-05
3,686	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	6.839208e-05
4,089	In-Cache Query Co-Processing on Coupled CPU-GPU Architectures	2015	VLDB	6.4559891e-05
5,124	Accelerating Generalized Linear Models with MLWeaving: A One-Size-Fits-All System for Any-Precision Learning	2019	VLDB	5.6747536e-05
5,541	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	5.4501856e-05
5,677	Joins on Encoded and Partitioned Data	2014	VLDB	5.376511e-05
5,847	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	5.3040014e-05
6,366	Good to the Last Bit: Data-Driven Encoding with CodecDB	2021	SIGMOD	5.0892171e-05
6,492	GOLAP: A GPU-in-Data-Path Architecture for High-Speed OLAP	2024	SIGMOD	5.0364695e-05
7,331	MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model	2020	VLDB	4.7558046e-05
7,813	Online Reorganization in Read Optimized MMDBS	2011	SIGMOD	4.6408773e-05
8,441	XQueC: Pushing Queries to Compressed XML Data	2003	VLDB	4.5054381e-05
8,658	RadixZip: Linear Time Compression of Token Streams	2007	VLDB	4.4682399e-05
8,856	Composable Data Management: An Execution Overview	2024	VLDB	4.4303659e-05
9,410	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	4.3399748e-05
9,452	Toward Quantity-of-Interest Preserving Lossy Compression for Scientific Data	2023	VLDB	4.3363262e-05
9,918	MorphStore — In-Memory Query Processing based on Morphing Compressed Intermediates LIVE	2019	SIGMOD	4.2520778e-05
10,622	QPET: A Versatile and Portable Quantity-of-Interest-Preservation Framework for Error-Bounded Lossy Compression	2025	VLDB	4.1905499e-05
11,039	Blitzcrank: Fast Semantic Compression for In-memory Online Transaction Processing	2024	VLDB	4.1905499e-05
11,093	Simple (yet Efficient) Function Authoring for Vectorized Engines	2024	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040465394
52	Database Architecture Optimized for the new Bottleneck: Memory Access	1999	VLDB	0.00066322421
140	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00042289025
894	Data Compression Support in Databases	1994	VLDB	0.00015516667
925	XMill: an Efficient Compressor for XML Data	2000	SIGMOD	0.00015243795
1,042	Daytona And The Fourth-Generation Language Cymbal	1999	SIGMOD	0.00014470108
1,337	Query Processing in Main Memory Database Management Systems	1986	SIGMOD	0.00012515176
2,065	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.6467359e-05
4,958	Aggregation Algorithms for Very Large Compressed Data Warehouses	1999	VLDB	5.8004036e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,469	Comprehensive and Efficient Workload Compression	2021	VLDB	6.1535623e-05
2,137	How to Wring a Table Dry: Entropy Compression of Relations and Querying of Compressed Relations	2006	VLDB	9.463768e-05
9,499	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD	4.3300131e-05
1,443	Compressing SQL Workloads	2002	SIGMOD	0.00011944621
5,677	Joins on Encoded and Partitioned Data	2014	VLDB	5.376511e-05
132	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00043697853
7,431	CompressDB: Enabling Efficient Compressed Data Direct Processing for Various Databases	2022	SIGMOD	4.7274757e-05
1,134	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013751593
8,575	Robust and Budget-Constrained Encoding Configurations for In-Memory Database Systems	2022	VLDB	4.4880409e-05
6,160	Compression Aware Physical Database Design	2011	VLDB	5.1750659e-05