More Web Proxy on the site http://driver.im/

Article

Free access

Sequential sampling procedures for query size estimation

Authors:

Arun N. SwamiAuthors Info & Claims

SIGMOD '92: Proceedings of the 1992 ACM SIGMOD international conference on Management of data

Pages 341 - 350

https://doi.org/10.1145/130283.130335

Published: 01 June 1992 Publication History

Abstract

We provide a procedure, based on random sampling, for estimation of the size of a query result. The procedure is sequential in that sampling terminates after a random number of steps according to a stopping rule that depends upon the observations obtained so far. Enough observations are obtained so that, with a pre-specified probability, the estimate differs from the true size of the query result by no more than a prespecified amount. Unlike previous sequential estimation procedures for queries, our procedure is asymptotically efficient and requires no ad hoc pilot sample or a a priori assumptions about data characteristics. In addition to establishing the asymptotic properties of the estimation procedure, we provide techniques for reducing undercoverage at small sample sizes and show that the sampling cost of the procedure can be reduced through stratified sampling techniques.

References

[1]

Chow, Y. S. and Robbins, H. (1965). On the asymptotic theory of fixed-width confidence intervals for the mean. Ann. Math. Statist. 37, 457-462.

[2]

Glynn, P. W. (1982). Asymptotic theory for nonparametric confidence intervals. Technical Report 63. Department of Operations Research. Stanford University. Stanford, California.

[3]

Gut, A. (1988) Stopped Random Walks: Limit Theorems and Applications. Springer-Verlag. New York.

[4]

Haas, P. 3. and Swami, A. N. (1992). Sequential procedures for query size estimation. Technical Report R,J 8558. IBM Almaden Research Center. San Jose, California. (The full version of this paper.)

Digital Library

[5]

Hou, W., Ozsoyoglu, G., and Taneja, B. (1988). Statistical estimators for relational algebra expressions. Proc. 7th A CM Symposium on Principles of Database Systems, 276-287. Association for Computing Machinery. New York.

Digital Library

[6]

Hou, W., Ozsoyoglu, G., and Waneja, B. (1989). Processing aggregate relational queries with hard time constraints. Proc. SIGMOD International Conference on Management of Data, 68-77. Association for Computing Machinery. New York.

Digital Library

[7]

ttou, W., Ozsoyoglu, G., and Dogdu, E. (1991). Error-constrained COUNT query evaluation in relational databases. Proc. SIGMOD /nternational Conference on Management of Data, 278-287. Association for Computing Machinery. New York.

Digital Library

[8]

IBM Corporation (1990). Capacity Planning for DB2 Applications. IBM Manual GG24-3512.

[9]

:Jarke, M. and Koch, J. (1984). Query optimization in database systems. ACM Computing Surveys 16, 111-152.

Digital Library

[10]

gnuth, D. E. (1973). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley. Reading, Massachusetts.

Digital Library

[11]

Lavenberg, S. S. and Sauer, C. H. (1977). Sequential stopping rules for the regenerative method of simulation. IBM J. Res. Develop. 21, 545-558

Digital Library

[12]

Lipton, R. 3. and Naughton, 3. F. (1989). Estimating the size of general transitive closures. Proc. 15th Conf. Very Large Data Bases, 165-171. Morgan Kaufmann. Palo Alto, California.

Digital Library

[13]

Lipton, R. 3. and Naughton, 3. F. (1990). Query size estimation by adaptive sampling. Proc. 9th A CM Symposium on Principles of Database Systems, 40-46. Association for Computing Machinery. New York.

Digital Library

[14]

Lipton, R. :I., Naughton, J. F., and Schneider, D. A. (1990). Practical selectivity estimation through adaptive sampling. Proc. SIGMOD International Conference on Management of Data, i-Ii. Association for Computing Machinery. New York.

Digital Library

[15]

Mannino, M. V., Chu, V., and Sager, T. (1988). Statistical profile estimation in database systems. ACM Computing Surveys 20, 191-221.

Digital Library

[16]

Ngdas, A. (1969). An extension of a theorem of Chow and Robbins on sequential confidence intervals for the mean. Ann. Math. Statist. 40, 667-671.

[17]

Olken, F. and Rotem, D. (1989). Random sampling from B+ trees. Proc. 15Lh Conf. Very Large Data Bases, 269-278. Morgan Kaufmann. Palo Alto, California.

Digital Library

[18]

Peiser, A. M. (1943). Asymptotic formulas for significance levels of certain distributions. Ann. Math. Statist. 14, 56-62.

[19]

Seppi, g. (1990). A Bayesian approach to selected database issues. Ph.D. Dissertation. Graduate Program in Operations Research. University of Texas. Austin, Texas.

Digital Library

[20]

Shedler, G. S. (1987). Regeneration and Networks of Queues. Springcr-Vcrlag. New York.

Digital Library

[21]

Siegmund, D. (1985). Sequential Analysis: Tests and Cont~dence Intervals. Springer-Verlag. New York.

[22]

Wolf, :I., Dias, D., and Yu, P. (1990). An effective algorithm for paralleliv.ing sort merge joins in the presence of data skew. Proc. 2nd International Symposium on Databases in Parallel and Distributed Systems, 103-115.

Digital Library

Cited By

Hu PMotik B(2024)Accurate Sampling-Based Cardinality Estimation for Complex Graph QueriesACM Transactions on Database Systems10.1145/368920949:3(1-46)Online publication date: 17-Sep-2024
https://dl.acm.org/doi/10.1145/3689209
Paun IMoshfeghi YNtarmos N(2023)White Box: On the Prediction of Collaborative Filtering Recommendation Systems’ PerformanceACM Transactions on Internet Technology10.1145/355497923:1(1-29)Online publication date: 23-Feb-2023
https://dl.acm.org/doi/10.1145/3554979
He XTan JWu BLi FZhang XLiang GXu J(2023)Active Sampling for Sparse Table by Bayesian Optimization with Adaptive Resolution2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00068(816-828)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00068
Show More Cited By

Index Terms

Sequential sampling procedures for query size estimation

Recommendations

Sequential sampling procedures for query size estimation

We provide a procedure, based on random sampling, for estimation of the size of a query result. The procedure is sequential in that sampling terminates after a random number of steps according to a stopping rule that depends upon the observations ...
Query Size Estimation for Joins Using Systematic Sampling

We propose a new approach to the estimation of query result sizes for join queries. The technique, which we have called “systematic sampling—SYSSMP”, is a novel variant of the sampling-based approach. A key novelty of the systematic sampling is that it ...
Bifocal sampling for skew-resistant join size estimation
SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data

This paper introduces bifocal sampling, a new technique for estimating the size of an equi-join of two relations. Bifocal sampling classifies tuples in each relation into two groups, sparse and dense, based on the number of tuples with the same join ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '92: Proceedings of the 1992 ACM SIGMOD international conference on Management of data

June 1992

416 pages

ISBN:0897915216

DOI:10.1145/130283

Editor:
Michael Stonebraker
Univ. of California at Berkeley

ACM SIGMOD Record Volume 21, Issue 2
June 1, 1992
415 pages
ISSN:0163-5808
DOI:10.1145/141484
Editor:
Michael Stonebraker
Issue’s Table of Contents

Copyright © 1992 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1992

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS92

Sponsor:

SIGMOD/PODS92: SIGMOD/PODS '92

June 2 - 5, 1992

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

157
Total Citations
View Citations
338
Total Downloads

Downloads (Last 12 months)133
Downloads (Last 6 weeks)11

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hu PMotik B(2024)Accurate Sampling-Based Cardinality Estimation for Complex Graph QueriesACM Transactions on Database Systems10.1145/368920949:3(1-46)Online publication date: 17-Sep-2024
https://dl.acm.org/doi/10.1145/3689209
Paun IMoshfeghi YNtarmos N(2023)White Box: On the Prediction of Collaborative Filtering Recommendation Systems’ PerformanceACM Transactions on Internet Technology10.1145/355497923:1(1-29)Online publication date: 23-Feb-2023
https://dl.acm.org/doi/10.1145/3554979
He XTan JWu BLi FZhang XLiang GXu J(2023)Active Sampling for Sparse Table by Bayesian Optimization with Adaptive Resolution2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00068(816-828)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00068
Patrignani MMartin EDevriese D(2021)On the semantic expressiveness of recursive typesProceedings of the ACM on Programming Languages10.1145/34343025:POPL(1-29)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434302
Zhang DShao JShen H(2020)Kernel Attention Network for Single Image Super-ResolutionACM Transactions on Multimedia Computing, Communications, and Applications10.1145/339868516:3(1-15)Online publication date: 5-Jul-2020
https://dl.acm.org/doi/10.1145/3398685
Hu XXi JTang D(2020)Optimization for Multi-Join Queries on the GPUIEEE Access10.1109/ACCESS.2020.30026108(118380-118395)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3002610
Walenz BSintos SRoy SYang J(2019)Learning to sampleProceedings of the VLDB Endowment10.14778/3368289.336830213:3(390-402)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.14778/3368289.3368302
Liu CXiong JCai LFeng LChen XFang D(2019)Beyond RespirationProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/33512543:3(1-22)Online publication date: 9-Sep-2019
https://dl.acm.org/doi/10.1145/3351254
Lee LLam KLi TBraud TSu XHui P(2019)Quadmetric Optimized Thumb-to-Finger Interaction for Force Assisted One-Handed Text Entry on Mobile HeadsetsProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/33512523:3(1-27)Online publication date: 9-Sep-2019
https://dl.acm.org/doi/10.1145/3351252
King ZMoskowitz JEgilmez BZhang SZhang LBass MRogers JGhaffari RWakschlag LAlshurafa N(2019)micro-Stress EMAProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/33512493:3(1-22)Online publication date: 9-Sep-2019
https://dl.acm.org/doi/10.1145/3351249
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents