# US 7,613,682 B2 · Statistics collection using path-identifiers for relational databases

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,613,682 B2
- Document ID: US7613682B2
- Status: Granted
- Kind: B2
- Application number: 11/435,017
- Filed: 2006-05-16
- Published: 2007-11-22
- Granted: 2009-11-03
- Earliest claimed: 2006-05-16
- Assignees: International Business Machines Corporation
- Inventors: Lipyeow Lim; George Andrei Mihaila; Min Wang
- Web page: https://patentgrep.com/patent/US7613682B2

## CPC

- G06F 16/2462: {Approximate or statistical queries}
- G06F 16/2453: Query optimisation
- G06F 16/8365: {Query optimisation}
- Y10S 707/99931: Database or file accessing
- Y10S 707/99932: Access augmentation or optimizing
- Y10S 707/99933: Query processing, i.e. searching
- Y10S 707/99944: Object-oriented database structure
- Y10S 707/99953: Recoverability
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

Disclosed are a method for collecting statistics associated with data in a database. The method comprises determining an amount of memory needed to collect statistics for data associated with a defined data type in a relational database. The defined data type is based upon a mark-up language using a tree structure with one or more root-to-node paths therein. The amount of memory as determined is allocated for collecting the statistics for the data of the defined data type. A statistics collection is performed for the data of the defined data type in a single pass through the database and within the amount of memory which has been allocated.

## Claims

### Claim 1

A method, on an information processing system, for collecting statistics associated with data in a database, the method comprising:
determining an amount of memory needed to collect statistics for data associated with a defined data type in a relational database, wherein the amount of memory also includes an amount of memory needed for a set of reservoirs used to collect specific statistics for the data associated with the defined data type and a work area associated with each of the reservoirs, and an amount of memory needed for a set of filters to be used in collecting statistics for data associated with the defined data type, wherein the defined data type is based upon a mark-up language using a tree structure with one or more root-to-node paths therein;
allocating the amount of memory as determined for collecting the statistics for the data of the defined data type;
performing a collection of statistics for the data of the defined data type in a single pass through the database and within the amount of memory which has been allocated, wherein performing a collection of statistics includes:
counting a total number of instances of at least one path-identifier within a given set of documents;
determining at least one of a node count and a document count for the path-identifier based on counting the total number of instances of the at least one path-identifier, wherein the at least one path-identifier is one of a given number of most frequently occurring path-identifiers in the given set of documents;
counting, for each document within a set of given documents, a total number of path-identifiers that are each associated with a unique path, thereby resulting in a total number of path-identifiers in the set of given documents that are associated with the unique path;
counting a total number of nodes within the set of given documents; and
counting, for each path-identifier that is associated with a unique path, a total number of documents in the set of given documents that include the path-identifier, thereby resulting in a sum of document counts;
sampling at a document level, wherein the sampling comprises
a row level sampling and a page level sampling, and
sampling using at least one reservoir in the set of reservoirs, wherein the sampling using reservoirs comprises
traversing through at least one of
sampled documents in a given set of documents, and
all documents in the set of given set of documents for identifying at least path-identifiers;
passing data associated with each path-identifier that has been identified to a first reservoir in the set of reservoirs; and
passing data associated with each path-identifier that has been identified and is unique within a particular document in the given set of documents to a second reservoir in the set of reservoirs;
applying a first bloom filter in the set of filters to each path-identifier prior to passing the path-identifier to the second reservoir, thereby preventing a duplicate path-identifier within the particular document from being passed to the second reservoir;
summarizing the first reservoir for identifying a node count for determining a given number of most frequently occurring path-identifiers; and
summarizing the second reservoir for identifying a document count for determining the given number of most frequently occurring path-identifiers.