Approximating a database statistic

Details Approximating a database statistic Approximating a database statistic

2007-04-25

2009-12-22

Lee, Wilson (Department: 2163)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

07636731

ABSTRACT:
A method and apparatus for approximating a database statistic, such as the number of distinct values (NDV) is provided. To approximate the NDV for a portion of a table, a synopsis of distinct values is constructed. Each value in the portion is mapped to a domain of values. The mapping function is implemented with a uniform hash function, in one embodiment. If the resultant domain value does not exist in the synopsis, the domain value is added to the synopsis. If the synopsis reaches its capacity, a portion of the domain values are discarded from the synopsis. The statistic is approximated based on the number (N) of domain values in the synopsis and the portion of the domain that is represented in the synopsis relative to the size of the domain.

REFERENCES:
patent: 6665684 (2003-12-01), Zait et al.
patent: 6757675 (2004-06-01), Aiken et al.
patent: 7092954 (2006-08-01), Ramesh
patent: 7480302 (2009-01-01), Choi
patent: 7512589 (2009-03-01), Stokkan et al.
patent: 2006/0083227 (2006-04-01), Eldar
patent: 2006/0085592 (2006-04-01), Ganguly et al.
patent: 2006/0242694 (2006-10-01), Gold et al.
patent: 2006/0288030 (2006-12-01), Lawrence
patent: 2007/0043757 (2007-02-01), Benton et al.
patent: 2007/0226237 (2007-09-01), Gong et al.
patent: 2008/0120275 (2008-05-01), Cruanes et al.
Poess, Meikel, et al., “New TPC Benchmarks for Decision Support and Web Commerce”, ACM Press, retrieved from website: < http://www.sigmod.org/record/issues/0012/standards.pdf >, published Dec. 2000, 8 pages.
Selinger, P. Griffiths, et al., “Access Path Selection in a Relational Database Management System”, ACM Inc., Proceedings of the 1979 ACM SIGMOD International Conference on the Management of Data, dated Oct. 2002, pp. 23-34.
Cyran, Michele, et al., “Oracle® Database Concepts”, Oracle, 10g Release 2 (10.2), dated Oct. 2005, 16 pages.
PUBLIB.BOULDER.IBM.COM, “Collecting statistics on a sample of the table data”, DB2 Version 9 for Linux, UNIX, and Windows, retrieved from website: http://publib.boulder.ibm.com/infocenter/db2luw/v9/index.jsp?topic=/com.ibm.db2. udb.admin.doc/doc/c0011393.htm >, last updated Oct. 27, 2006, 1 page.
PUBLIB.BOULDER.IBM.COM, “Runstats command”, DB2 Version 9 for Linux, UNIX, and Windows, Retrieved from website: http://publib.boulder.ibm.com/infocenter/db2luw/v8/index.jsp?topic=/com.ibm.db2.udb.doc/core/r0001980.htm, last updated Oct. 27, 2006, 8 pages.
Microsoft, “SQL Server Query Optimization and Tuning”, Microsoft TechNet, Retrieved from website: < http://www.microsoft.com/technet/community/chats/trans/sql/sql0909.mspx >, Published Sep. 9, 2003, 7 pages.
Hanson, Eric N., et al., “Statistics Used by the Query Optimizer in Microsoft SQL Server 2005”, Microsoft TechNet, retrieved from website: < http://www.microsoft.com/technet/prodtechnol/sql/2005/qrystats.mspx >, printed Mar. 27, 2007, 13 pages.
Gibbons, Phillip B., et al., “Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports”, Proceedings of the 27thVLDB Conference, 2001, 10 pages.
Othayoth, Raghunath, et al., “The Making of TPC-DS”, Copyright 2006 VLDB Endowment, ACM, retrieved from website: < http://www.vldb.org/conf/2006/p1049-othayoth.pdf >, 10 pages.

Affiliated with

Also associated with

Rating

Approximating a database statistic does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4122864