Sampling for queries

Details Sampling for queries Sampling for queries

2007-10-23

2007-10-23

Wong, Don (Department: 2163)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

09759804

ABSTRACT:
This disclosure describes leveraging workload information associated with executed database queries for estimating the result of a current database query. The workload information is analyzed to determine the usage of tuples in a database during query execution, such as how often a tuple is accessed and the number of different queries that accessed the tuple. A tuple is assigned a weight value that is based on the analyzed workload information. The particular tuples sampled for estimating a result for the current query is based on each tuple's weight value. The workload information may also be leveraged to generate an outlier index that identifies outlier tuples associated with the executed queries or that identifies outlier tuples associated with particular queries that are executed more frequently than other queries. The result for the current query can also be estimated using the sampled values along with the outlier tuples from the outlier index.

REFERENCES:
patent: 5504887 (1996-04-01), Malhotra et al.
patent: 5950189 (1999-09-01), Cohen et al.
patent: 6026391 (2000-02-01), Osborn et al.
patent: 6029163 (2000-02-01), Ziauddin
patent: 6321218 (2001-11-01), Guay et al.
patent: 6356889 (2002-03-01), Lohman et al.
patent: 6360214 (2002-03-01), Ellis et al.
patent: 6466931 (2002-10-01), Attaluri et al.
patent: 6519604 (2003-02-01), Acharya et al.
patent: 2002/0124001 (2002-09-01), Chaudhuri et al.
patent: 2002/0127529 (2002-09-01), Cassuto et al.
U.S. Appl. No. 09/759,799 with pending claims, filed Jun. 22, 2004 by Chaudhuri et al.
Barnett et al., Table of Contents, “Outliers in Statistical Data,” John Wiley, 3rd Edition (1994).
Chatfield, Table of Contents, “The Analysis of Time Series,” Chapman and Hall (1984).
Hawkins, Table of Contents, “Identification of Outliers,” Chapman and Hall (1980).
Etzio et al., Table of Contents, “Temporal Databases: Research and Practice LNCS 1399,” Springer Verlag (1988).
Gray et al., Table of Contents, “Transaction Processor: Concepts and Techniques,” Morgan Kaufmann (1993).
H. Jagdish, N. Koudas and S. Muthukrishnan , “Mining Deviants in Times Series Database”, In Proceedings of 25thInternational Conference Very Large Data Bases, pp. 102-113, 1999.
E. Knorr and R. Ng, “Algorithms for Mining Distance-Based Outliers in Large Datasets”, In Proceedings of 24thInternational Conference Very Large Data Bases, pp. 392-403, 1998.
J.F. Naughton and S. Seshadri, “On Estimating the Size of Projections”, In Proceedings Third International Conference on Database Theory, pp. 499-513, 1990.
W.G. Cochran, “Sampling Techniques”, John Wiley & Sons, New York, third edition, 1977, Chapter 3, pp. 50-71.
Y. Ioannidis and V. Poosala, “Histogram Based Approximations of Set-Valued Query Answers”, In Proceedings of 25thInternational Conference Very Large Data Bases, pp. 174-185, 1999.
V. Ganti, M.L. Lee and R. Ramakrishnan, “ICICLES: Self-Tuning Samples for Approximate Query Answering”, In Proc. 26thVLDB, 2000.
S. Acharya, P.B. Gibbons, V. Poosala, “Congressional Samples for Approximate Answering of Group-By Queries”, ACM SIGMOD 2000, May 2000, Dallas, Texas.
S. Acharya, P.B. Gibbons, V. Poosala and S. Ramaswamy, “Join Synopses for Approximate Query Answering”, SIGMOD 1999, Philadelphia, PA.
P.B. Gibbons and Y. Matias, “New Samping-Based Summary Statistics for Improving Approximate Query Answers”, SIGMOD 1998, Seattle, WA.
P..J. Haas and J.M. Hellerstein, “Ripple Joins for Online Aggregation”, SIGMOD 1999, Philadelphia, PA.
S. Chaudhuri, R.Motwani and V. Narasayya, “On Random Sampling Over Joins”, SIGMOD 1999, Philadelphia, PA.
G.S. Manku, S. Rajagopalan, B.G. Lindsay, “Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets”, SIGMOD 1999, Philadelphia, PA.
S. Ganguly, P.B. Gibbons, Y. Matias and A. Silberschatz, “Bifocal Sampling for Skew-Resistant Join Size Estimation”, pp. 271-281, SIGMOD '96, Jun. 1996, Montreal Canada.
P.J. Hass, J.F. Naughton and A.N. Swami, “On the Relative Cost of Sampling for Join Selectivity Estimation”, pp. 14-24, SIGMOD/PODS 94—May 1994, Minneapolis, Minnesota USA.
J.M. Hellerstein, P.J. Haas and H.J. Wang, “Online Aggregation”, pp. 171-182, SIGMOD '97 AZ, USA.
R.J. Lipton, Jeffrey F. Naughton, D.A. Schneider and S. Seshadri, “Efficient Sampling Strategies for Relational Database Operations”, Theoretical Computer Science 116 (1993) 195-226.
Wen-Chi Hou, G. Ozaoyoglu and E. Dogdu, “Error-Constrained COUNT Query Evaluation in Relational Databases”, pp. 278-287, May 29-31, 1991, Denver, Colorado, Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data.
F. Olken and D. Rotem, “Random Sampling from Databases—A Survey”, Abstract and pp. 1-55, Mar. 22, 1994.
R. Motwani and P. Raghavan, “Randomized Algorithms”, 1995.
F. Olken, “Simple Random Sampling from Relational Databases”, Proceedings from Twelfth International Conference on Very Large Databases, Kyoto, Aug. 1986, p. 160-169.
G. Piatetsky-Shapiro and C. Connell, “Accurate Estimation of the Number of Tuples Satisfying a Condition”, pp. 256-276, 1984 ACM.
G.S. Manku, S. Rajagopalan and B.G. Lindsay, “Approximate Medians and other Quantiles in One Pass and with Limited Memory”, pp. 426-435, SIGMOD '98, Seattle Washington.
F.Olken, “Random Sampling from Databases”, 1993, pp. 1-158.

Affiliated with

Also associated with

Rating

Sampling for queries does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Sampling for queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sampling for queries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3853328