Adaptive selectivity estimation using query feedback

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AG67	A.E. Albert and L.A. Gardner. Stochastic Approximation and Nonlinear Regression. M.I.T. Press, Cambridge, Massachusetts, 1967.
	Chr83a	Stavros Christodoulakis, Estimating block transfers and join sizes, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
	Chr83b	S. Christodoulakis. Estimating record selectivities. Inf. Syst., 8(2):105-115, 1983.
	CR94	Chungmin Melvin Chen , Nick Roussopoulos, Adaptive selectivity estimation using query feedback, University of Maryland at College Park, College Park, MD, 1994
	dB78	C. de Boor. A practzcal guide to splines. Springer-Verlag, New York, 1978.
	Fed84	Jane Fedorowicz, Database evaluation using multiple regression techniques, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	HOT88	Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Statistical estimators for relational algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.276-287, March 1988, Austin, Texas, United States [doi>10.1145/308386.308455]
	HS92	Peter J. Haas , Arun N. Swami, Sequential sampling procedures for query size estimation, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.341-350, June 02-05, 1992, San Diego, California, United States
	IC91	Yannis E. Ioannidis , Stavros Christodoulakis, On the propagation of errors in the size of join results, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.268-277, May 29-31, 1991, Denver, Colorado, United States
	Ioa93	Yannis E. Ioannidis, Universality of Serial Histograms, Proceedings of the 19th International Conference on Very Large Data Bases, p.256-267, August 24-27, 1993
	KK85	Nabil Kamel , Roger King, A model of data distribution based on texture analysis, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.319-325, May 1985, Austin, Texas, United States
	LN90	Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States
	LST83	Ezio Lefons , Alberto Silvestri , Filippo Tangorra, An Analytic Approach to Statistical Databases, Proceedings of the 9th International Conference on Very Large Data Bases, p.260-274, October 31-November 02, 1983
	Lyn88	Clifford A. Lynch, Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distribution of Column Values, Proceedings of the 14th International Conference on Very Large Data Bases, p.240-251, August 29-September 01, 1988
	MCS88	Michael V. Mannino , Paicheng Chu , Thomas Sager, Statistical profile estimation in database systems, ACM Computing Surveys (CSUR), v.20 n.3, p.191-221, Sept. 1988 [doi>10.1145/62061.62063]
	MD88	M. Muralikrishna , David J. DeWitt, Equi-depth multidimensional histograms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.28-36, June 01-03, 1988, Chicago, Illinois, United States
	MO79	T.H. Merrett and E. Otoo. Distribution models of relations. In Proceedings of the 5th VLDB Conference, pages 418-425, Rio De Janero, Brazil, 1979.
	PSC84	Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	S+79	P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
	SB83	W. Samson and A. Bendell. Rank order distriburions and secondary key indexing. In Proceedings of the 2nd Intl. Conf. on Databases, Cambridge, England, 1983.
	SLRD93	Wei Sun , Yibei Ling , Naphtali Rishe , Yi Deng, An instant and accurate size estimation method for joins and selections in a retrieval-intensive environment, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.79-88, May 25-28, 1993, Washington, D.C., United States
	Wil91	Dan E. Willard, Optimal sample cost residues for differential database batch query problems, Journal of the ACM (JACM), v.38 n.1, p.104-119, Jan. 1991 [doi>10.1145/102782.102786]
	You84	Peter Young, Recursive estimation and time-series analysis: an introduction, Springer-Verlag New York, Inc., New York, NY, 1984