How to Barter Bits for Chronons: Compression and Bandwidth Trade Offs for Database Scans

Summary: Code-generated, schema-tuned compression scans to reduce CPU-bound table scans; evaluates formats and introduces two optimizations: tuple-length quantization and a field-length lookup table. Empirical results reveal compression–speed trade-offs and ILP-based techniques to increase parallelism on multi-issue processors. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3929
Venue: SIGMOD
Year: 2007
Pagerank: 9.4271737e-05
Overall Rank: 1,950 | 86.63%
DOI: 10.1145/1247480.1247525

Incoming Non-self Citations Over Time

Authors

1. Allison L. Holloway (University of Wisconsin)
2. Vijayshankar Raman (IBM)
3. Garret Swart (IBM)
4. David J. DeWitt (University of Wisconsin)

BibTeX Citation

@inproceedings{holloway_sigmod07,
        title = {{How to Barter Bits for Chronons: Compression and Bandwidth Trade Offs for Database Scans}},
        author = {Holloway, Allison L. and Raman, Vijayshankar and Swart, Garret and DeWitt, David J.},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247525},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247525},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
165	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00027693424
216	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024498128
1,854	Towards a One Size Fits All Database Architecture	2011	CIDR	9.6069414e-05
2,150	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	9.081101e-05
2,843	Rose: Compressed, log-structured replication	2008	VLDB	8.0617003e-05
3,292	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	7.5518441e-05
3,489	Read-Optimized Databases, In Depth	2008	VLDB	7.3670717e-05
4,798	Accelerating Generalized Linear Models with MLWeaving: A One-Size-Fits-All System for Any-Precision Learning	2019	VLDB	6.5024772e-05
6,428	Data Warehouse Technology by Infobright	2009	SIGMOD	5.8807378e-05
8,072	Operational Analytics Data Management Systems	2016	VLDB	5.4933919e-05
8,794	AWARE: Workload-aware, Redundancy-exploiting Linear Algebra	2023	SIGMOD	5.370464e-05
8,952	RadixZip: Linear Time Compression of Token Streams	2007	VLDB	5.3458888e-05
12,117	Purity: Building Fast, Highly-Available Enterprise Flash Storage from Commodity Components	2015	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00069513174
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.0006312782
60	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.0003955489
630	Performance Tradeoffs in Read-Optimized Databases	2006	VLDB	0.00015591796
921	Query Optimization In Compressed Database Systems	2001	SIGMOD	0.00013209503
970	Sybase IQ Multiplex – Designed For Analytics	2004	VLDB	0.00012882125
1,017	Data Compression Support in Databases	1994	VLDB	0.00012641552
1,222	Data Compression in Oracle	2003	VLDB	0.00011602327
1,355	Query Processing in Main Memory Database Management Systems	1986	SIGMOD	0.0001105702
1,748	How to Wring a Table Dry: Entropy Compression of Relations and Querying of Compressed Relations	2006	VLDB	9.8480684e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,266	Compressing SQL Workloads	2002	SIGMOD
2	870	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD
3	2,232	Database Compression on Graphics Processors	2010	VLDB
4	5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD
5	630	Performance Tradeoffs in Read-Optimized Databases	2006	VLDB
6	5,357	Joins on Encoded and Partitioned Data	2014	VLDB
7	5,755	Compression Aware Physical Database Design	2011	VLDB
8	216	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB
9	921	Query Optimization In Compressed Database Systems	2001	SIGMOD
10	60	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD