Adaptive selectivity estimation using query feedback
ACM SIGMOD RecordPublished 24 May 1994Open access
Chungmin Melvin Chen, Nick Roussopoulos
Citations36
SJR quartileQ2
SJR score0.69
SNIP0.92
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
In this paper, we propose a novel approach for estimating the record selectivities of database queries. The real attribute value distribution is adaptively approximated by a curve-fitting function using a query feedback mechanism. This approach has the advantage of requiring no extra database access overhead for gathering statistics and of being able to continuously adapt the value distribution through queries and updates. Experimental results show that the estimation accuracy of this approach is comparable to traditional methods based on statistics gathering.
Keywords
Computer Science
Applied mathematical sciencesA Practical Guide to Splines
11,999 Citations1978Carl de Boor
This book presents those parts of the theory which are especially useful in calculations and stresses the representation of splines as linear combinations of B-splines as well as specific approximation methods, interpolation, smoothing and least-squares approximation, the solution of an ordinary differential equation by collocation, curve fitting, and surface fitting.
Access path selection in a relational database management system
2,153 Citations1979Patricia G. Selinger, M. M. Astrahan +3 more
This paper describes how System R chooses access paths for both simple (single relation) and complex queries (such as joins) given a user specification of desired data as a boolean expression of predicates.
Accurate estimation of the number of tuples satisfying a condition
342 Citations1984Gregory Piatetsky-Shapiro, Charles W. Connell
A new method for estimating the number of tuples satisfying a condition of the type attribute rel constant, where rel is one of "=", ">", "<, "≥", "≤" , which gives highly accurate, yet easy to compute, estimates.
Practical selectivity estimation through adaptive sampling
276 Citations1990Richard J. Lipton, Jeffrey F. Naughton +1 more
This paper extends the previous analysis to provide significantly improved bounds on the amount of sampling necessary for a given level of accuracy and provides “sanity bounds” to deal with queries for which the underlying data is extremely skewed or the query result is very small.
On the propagation of errors in the size of join results
266 Citations1991Yannis Ioannidis, Stavros Christodoulakis
This work presents a formal framework based on which the principles of this error propagation can be studied and obtains several analytic results on how the error propagates in general, as well as in the extreme and average cases.
ACM Computing SurveysStatistical profile estimation in database systems
226 Citations1988Michael V. Mannino, Pai-Cheng Chu +1 more
This paper describes a model of a database of profile, relates this model to estimating the cost of database operations, and surveys methods of estimating profiles.
Sequential sampling procedures for query size estimation
174 Citations1992Peter J. Haas, Arun Swami
Techniques for reducing undercoverage at small sample sizes and showing that the sampling cost of the procedure can be reduced through stratified sampling techniques are provided.
Statistical estimators for relational algebra expressions
144 Citations1988Wen‐Chi Hou, Gültekin Özsoyoğlu +1 more
This paper designs a sampling plan based on the cluster sampling method to improve the utilization of sampled data and to reduce the cost of sampling, and proposes consistent and unbiased estimators for arbitrary COUNT(E) type queries.
Information SystemsEstimating record selectivities
111 Citations1983Stavros Christodoulakis
It is shown that certain assumptions-used for modelling data base contents, data placement on devices and user requests often are not satisfied in actual data base environments.
The MIT Press eBooksStochastic Approximation and NonLinear Regression
98 Citations2003Arthur E. Albert, Leland A. Gardner
Equi-depth multidimensional histograms
93 Citations1988M. Muralikrishna, David J. DeWitt
This paper presents an algorithm for generating equi-depth, multi-dimensional histograms, and shows that the sorting cost of building a D-dimensional histogram is significantly less than the cost of sorting the relation D times.
Estimating block transfers and join sizes
85 Citations1983Stavros Christodoulakis
Estimates of the number of sequential and random block accesses required for retrieving a number of records of a file when the distribution of records in blocks of secondary storage is not uniform are provided.
An instant and accurate size estimation method for joins and selections in a retrieval-intensive environment
54 Citations1993Wei Sun, Yibei Ling +2 more
This paper proposes a novel strategy for estimating the size of the resulting relation after an equi-join and selection using a regression model, with no run-time overheads in page faults and space, and with negligible CPU overhead.
Distribution Models Of Relations
44 Citations1979T. H. Merrett, Ekow Otoo
It is shown how relations can be modelled in fast memory by a distribution of tuples in a multidimensional space using the result for the natural join to optimize the evaluation of an expression involving two joins.
A model of data distribution based on texture analysis
23 Citations1985Nabil Kamel, Roger King
Test results performrd for thla function are presented to show the Inverse correlation between Its value and the resulting estimation errors.
Database evaluation using multiple regression techniques
19 Citations1984Jane Fedorowicz
This paper introduces the Zipfian models, their regression formulation, and their results and interpretation for application to database evaluation.
Journal of the ACMOptimal sample cost residues for differential database batch query problems
10 Citations1991Dan E. Willard
The very general notion of a differentiable query problem is defined and it is shown that the ideal sample size for guessing the optimal choice of algorithm is O(N)(supscrpt) for all differential problems involving approximately N executing steps.