Workload-driven, Lazy Discovery of Data Dependencies for Query Optimization

Summary: Workload-driven, lazy discovery that extracts dependency candidates from executed plans, validates them dynamically, and maintains lightweight metadata to enable practical dependency-based query optimizations. Hyrise prototype shows feasibility and up to 27% JOB speedup, demonstrating practicality in columnar DBMSs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h51b7d55048c73948
Venue: CIDR
Year: 2022
Pagerank: 5.2644901e-05
Overall Rank: 8,851 | 40.50%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jan Kossmann (Hasso Plattner Institute)
2. Daniel Lindner (Hasso Plattner Institute)
3. Felix Naumann (Hasso Plattner Institute)
4. Thorsten Papenbrock (Philipps University Marburg)

BibTeX Citation

@inproceedings{kossmann_cidr22,
        address = {Amsterdam, Netherlands},
        series = {{CIDR} '22},
        title = {{Workload-driven, Lazy Discovery of Data Dependencies for Query Optimization}},
        booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
        author = {Kossmann, Jan and Lindner, Daniel and Naumann, Felix and Papenbrock, Thorsten},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,392	Themis: A GPU-accelerated Relational Query Execution Engine	2025	VLDB	5.1861628e-05
10,100	Adaptive data transformations for QaaS	2025	CIDR	5.0789354e-05
10,953	HaDA: Empower Database Experts with Data Dependencies	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
71	DuckDB: an Embeddable Analytical Database	2019	SIGMOD	0.00037720227
479	The Making of TPC-DS	2006	VLDB	0.00017622471
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015699254
906	Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation	2016	SIGMOD	0.00013160654
6,855	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.6642528e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,069	Dynamically Optimizing Queries over Large Scale Data Platforms	2014	SIGMOD
2	209	Dependency Inference	1987	VLDB
3	10,508	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
4	2,516	Optimization of Queries with User-defined Predicates	1996	VLDB
5	727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB
6	6,171	Fundamentals of Order Dependencies	2012	VLDB
7	143	Optimization of Nonrecursive Queries	1986	VLDB
8	603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD
9	12,046	Making DBMSes Dependency-Aware	2020	CIDR
10	6,049	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD