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: he0b634f838cb5d65
Venue: SIGMOD
Year: 2001
Pagerank: 0.00013152699
Overall Rank: 900 | 93.97%
DOI: 10.1145/375663.375692

Incoming Non-self Citations Over Time

Authors

1. Zhiyuan Chen (Cornell University)
2. Johannes Gehrke (Cornell University)
3. Flip Korn (AT&T)

BibTeX Citation

@inproceedings{chen_sigmod01,
        title = {{Query Optimization In Compressed Database Systems}},
        author = {Chen, Zhiyuan and Gehrke, Johannes and Korn, Flip},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375692},
        url = {https://dl.acm.org/doi/10.1145/375663.375692},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00039323387
852	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013447072
912	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013092547
1,990	How to Barter Bits for Chronons: Compression and Bandwidth Trade Offs for Database Scans	2007	SIGMOD	9.2272838e-05
2,634	WideTable: An Accelerator for Analytical Data Processing	2014	VLDB	8.1797149e-05
3,308	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	7.4195851e-05
3,495	In-Cache Query Co-Processing on Coupled CPU-GPU Architectures	2015	VLDB	7.237656e-05
4,872	GOLAP: A GPU-in-Data-Path Architecture for High-Speed OLAP	2024	SIGMOD	6.3582628e-05
4,891	Accelerating Generalized Linear Models with MLWeaving: A One-Size-Fits-All System for Any-Precision Learning	2019	VLDB	6.3508222e-05
5,236	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2037372e-05
5,398	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	6.1338952e-05
5,442	Joins on Encoded and Partitioned Data	2014	VLDB	6.1132896e-05
5,489	Good to the Last Bit: Data-Driven Encoding with CodecDB	2021	SIGMOD	6.0972774e-05
6,425	MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model	2020	VLDB	5.7716425e-05
6,688	Composable Data Management: An Execution Overview	2024	VLDB	5.6925768e-05
8,256	Online Reorganization in Read Optimized MMDBS	2011	SIGMOD	5.3520542e-05
8,996	XQueC: Pushing Queries to Compressed XML Data	2003	VLDB	5.2280172e-05
9,139	RadixZip: Linear Time Compression of Token Streams	2007	VLDB	5.2082006e-05
9,318	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	5.1831862e-05
9,740	Toward Quantity-of-Interest Preserving Lossy Compression for Scientific Data	2023	VLDB	5.1186755e-05
10,308	MorphStore — In-Memory Query Processing based on Morphing Compressed Intermediates LIVE	2019	SIGMOD	5.0294306e-05
10,341	Simple (yet Efficient) Function Authoring for Vectorized Engines	2024	VLDB	5.0210286e-05
10,919	Error-bounded Point Cloud Compression Using Truncated Octahedron Quantization	2026	VLDB	4.9605343e-05
11,338	QPET: A Versatile and Portable Quantity-of-Interest-Preservation Framework for Error-Bounded Lossy Compression	2025	VLDB	4.9605343e-05
11,633	Blitzcrank: Fast Semantic Compression for In-memory Online Transaction Processing	2024	VLDB	4.9605343e-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.0023948467
27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.0005146739
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030398363
1,001	Data Compression Support in Databases	1994	VLDB	0.00012586461
1,018	XMill: an Efficient Compressor for XML Data	2000	SIGMOD	0.00012451992
1,195	Daytona And The Fourth-Generation Language Cymbal	1999	SIGMOD	0.00011549748
1,386	Query Processing in Main Memory Database Management Systems	1986	SIGMOD	0.00010809129
1,939	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.3280163e-05
4,820	Aggregation Algorithms for Very Large Compressed Data Warehouses	1999	VLDB	6.3880163e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,777	How to Wring a Table Dry: Entropy Compression of Relations and Querying of Compressed Relations	2006	VLDB
2	9,824	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
3	1,246	Compressing SQL Workloads	2002	SIGMOD
4	5,442	Joins on Encoded and Partitioned Data	2014	VLDB
5	61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD
6	6,737	CompressDB: Enabling Efficient Compressed Data Direct Processing for Various Databases	2022	SIGMOD
7	912	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD
8	5,512	Compressed Representations of Conjunctive Query Results	2018	PODS
9	8,589	Robust and Budget-Constrained Encoding Configurations for In-Memory Database Systems	2022	VLDB
10	5,866	Compression Aware Physical Database Design	2011	VLDB