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: 7740
Venue: VLDB
Year: 1986
Pagerank: 6.9655849e-05
Overall Rank: 3,564 | 75.24%
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
509	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00021463676
12,845	Estimating Page Fetches for Index Scans with Finite LRU Buffers	1994	SIGMOD	4.1905499e-05
12,951	Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence	1989	SIGMOD	4.1905499e-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.00080571183
226	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.0003243274
1,399	A Model of Data Distribution Based on Texture Analysis	1985	SIGMOD	0.00012197728

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,971	Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning	1991	PODS	5.2466276e-05
4,517	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD	6.1143396e-05
1,017	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00014627121
6,512	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS	5.0273291e-05
4,075	Towards Predicting Query Execution Time for Concurrent and Dynamic Database Workloads	2013	VLDB	6.4699689e-05
4,944	A Cost Model for Clustered Object-Oriented Databases	1995	VLDB	5.8120276e-05
226	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.0003243274
8,869	Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing	2010	VLDB	4.4277859e-05
3,065	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB	7.6258862e-05
2,841	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.0396876e-05