Estimating Block Accesses When Attributes Are Correlated

Summary: Uses Schur-concavity/majorization to estimate query cost under correlation between the queried and clustering attributes. Also gives a correlated block-access distribution for accurate cost estimates and better plan choices. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7739
Venue: VLDB
Year: 1986
Pagerank: 6.971123e-05
Overall Rank: 3,561 | 75.23%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
508	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00021463742
12,836	Estimating Page Fetches for Index Scans with Finite LRU Buffers	1994	SIGMOD	4.1945683e-05
12,941	Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence	1989	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
228	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.00032269684
1,398	A Model of Data Distribution Based on Texture Analysis	1985	SIGMOD	0.00012197586

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,965	Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning	1991	PODS	5.2518232e-05
4,516	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD	6.1178799e-05
6,516	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS	5.0321577e-05
1,019	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00014625603
4,088	Towards Predicting Query Execution Time for Concurrent and Dynamic Database Workloads	2013	VLDB	6.4603918e-05
4,933	A Cost Model for Clustered Object-Oriented Databases	1995	VLDB	5.8205625e-05
228	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.00032269684
8,869	Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing	2010	VLDB	4.4320338e-05
3,064	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB	7.6279403e-05
2,837	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.0414149e-05