# US 6,732,110 B2 · Estimation of column cardinality in a partitioned relational database

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

- Number: US 6,732,110 B2
- Document ID: US6732110B2
- Status: Granted
- Kind: B2
- Application number: 09/894,222
- Filed: 2001-06-27
- Published: 2002-02-28
- Granted: 2004-05-04
- Earliest claimed: 2000-08-28
- Assignees: International Business Machines Corporation
- Inventors: Walid Rjaibi; Guy Maring Lohman; Peter Jay Haas
- Web page: https://patentgrep.com/patent/US6732110B2

## CPC

- G06F 16/24545: {Selectivity estimation or determination}
- Y10S 707/99932: Access augmentation or optimizing
- Y10S 707/99942: Manipulating data structure, e.g. compression, compaction, compilation
- Y10S 707/99943: Generating database or data structure, e.g. via user interface
- Y10S 707/99945: Object-oriented database structure processing
- 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

The present invention is directed to a system, method and computer readable medium for estimating a column cardinality value for a column in a partitioned table stored in a plurality of nodes in a relational database. According to one embodiment of the present invention, a plurality of column values for the partitioned table stored in each node are hashed, and a hash data set for each node is generated. Each of the hash data sets from each node is transferred to a coordinator node designated from the plurality of nodes. The hash data sets are merged into a merged data set, and an estimated column cardinality value for the table is calculated from the merged data set.

## Claims

### Claim 1

A method for estimating a column cardinality value for a column having a plurality of values in a partitioned table stored in a plurality of nodes in a relational database, the method comprising the steps of:
(a) generating a respective hash data set for each node in the plurality of nodes by hashing the column values for the partitioned table stored in each node wherein the hash data set comprises a list of unique hash values;
(b) transferring each of the hash data sets from each node in the plurality of nodes to a coordinator node;
(c) merging each of the respective hash data sets into a merged data set, and
(d) calculating an estimated column cardinality value for the table from the merged data set.

### Claim 2 (depends on 1)

The method of claim 1, wherein the coordinator node is designated from the plurality of nodes.

### Claim 3 (depends on 1)

The method of claim 1, wherein the calculating step (d) further comprising:
(d1) counting and adjusting the merged data set to derive the estimate for the column cardinality for the table.

### Claim 4 (depends on 1)

The method of claim 1, wherein the method utilizes a sample Counting technique.

### Claim 5 (depends on 4)

The method of claim 4, wherein the generating step (a) further comprising:
(a1) applying a defined hashing function to the plurality of column values for the partitioned table stored in the node, and generating a list of hash values and a sampling parameter for each node, a hash value being added to the list of hash values after filtering using a reference pattern defined by the sampling parameter, the sampling parameter being increased when the list of hash values reaches a predetermined maximum length.

### Claim 6 (depends on 5)

The method of claim 5, wherein the transferring step (b) further comprising:
(b1) transferring each list of hash values and the related sampling parameter from each node in the plurality of nodes to a coordinator node designated from the plurality of nodes.

### Claim 7 (depends on 5)

The method of claim 5, wherein the merging step (c) further comprising:
(c1) merging each list of hash values into a merged list of hash values by selecting a list of hash values having a largest associated sampling parameter and merging the each of the other lists into the selected list of hash values using filtering and sampling parameter incrementation as defined for sample counting.

### Claim 8 (depends on 7)

The method of claim 7, wherein the calculating step (8) further comprising:
(d1) multiplying a length of the merged list of hash values by 2 raised to a power of the sampling parameter for the merged list of hash values; and
(d2) correcting the estimate to account for hash function collisions.

### Claim 9

A computer readable medium containing programming instructions for estimating a column cardinality value for a column having a plurality of values in a partitioned table stored in a plurality of nodes in a relational database, the programming instructions for:
(a) generating a respective hash data set for each node in the plurality of nodes by hashing the column values for the partitioned table stored in each node wherein the hash data set comprises a list of unique hash values;
(b) transferring each of the hash data sets from each node in the plurality of nodes to a coordinator node;
(c) merging each of the respective hash data sets into a merged data set, and
(d) calculating an estimated column cardinality value for the table from the merged data set.

### Claim 10 (depends on 9)

The computer readable medium of claim 9, wherein the coordinator node is designated from the plurality of nodes.

### Claim 11 (depends on 9)

The computer readable medium of claim 9, wherein the calculating instruction (d) further comprising:
(d1) counting and adjusting the merged data set to derive the estimate for the column cardinality for the table.

### Claim 12 (depends on 9)

The computer readable medium of claim 9, wherein a sample counting technique is utilized.

### Claim 13 (depends on 12)

The computer readable medium of claim 12, wherein the hashing-generating instruction (a) further comprising:
(a1) applying a defined hashing function to the plurality of column values for the partitioned table stored in the node, and generating a list of hash values and a sampling parameter for each node, a hash value being added to the list of hash values after filtering using a reference pattern defined by the sampling parameter, the sampling parameter being increased when the list of hash values reaches a predetermined maximum length.

### Claim 14 (depends on 13)

The computer readable medium of claim 13, wherein the transferring instruction (b) further comprising:
(b1) transferring each list of hash values and the related sampling parameter from each node in the plurality of nodes to a coordinator node designated from the plurality of nodes.

### Claim 15 (depends on 13)

The computer readable medium of claim 13, wherein the merging instruction (c) further comprising:
(c1) merging each list of hash values into a merged list of hash values by selecting a list of hash values having a largest associated sampling parameter and merging the each of the other lists into the selected list of hash values using filtering and sampling parameter incrementation as defined for sample counting.

### Claim 16 (depends on 15)

The computer readable medium of claim 15, wherein the calculating instruction (d) further comprising:
(d1) multiplying a length of the merged list of hash values by 2 raised to a power of the sampling parameter for the merged list of hash values; and
(d1b) correcting the estimate to account for hash function collisions.

### Claim 17

A method for estimating a column cardinality value for a column having a plurality of values in a partitioned table stored in a plurality of nodes in a relational database, the method comprising the steps of:
(a) utilizing a logarithmic counting technique to generate a respective bit map for each node in the plurality of nodes by hashing the column values for the partitioned table stored in each node, wherein the utilizing step further includes:
(a1) calculating a binary hash value for each of the plurality of column values.
(b) transferring each bit map generated in each node in the plurality of nodes to a coordinator node designated from the plurality of nodes;
(c) merging each bit map in the coordinator node into a merged bit map by executing a logical, bit-wise OR operation on the bit maps; and
(d) calculating an estimated column cardinality value for the table from the merged bit map.

### Claim 18 (depends on 17)

The method of claim 17, wherein the utilizing step (a) further comprises:
(a2) transforming each binary hash value by retaining a leftmost 1 bit in the binary hash value and replacing all other 1 bits in the binary hash value with 0 values; and
(a3) performing a logical OR operation on the transformed binary hash value with a bit map value for the column in the node.

### Claim 19 (depends on 17)

The method of claim 17, wherein the calculating step (d) further comprising:
(d1) dividing 2 raised to a power of the leftmost position of a 0 bit in the merged bit map by a defined parameter related to a size of the bit map, and
(d2) correcting the estimate to account for hash function collisions.

### Claim 20

A computer readable medium containing programming instructions for estimating a column cardinality value for a column having a plurality of values in a partitioned table stored in a plurality of nodes in a relational database, the programming instructions for:
(a) utilizing a logarithmic counting technique to generate a respective bit map for each node in the plurality of nodes by hashing the column values for the partitioned table stored in each node, wherein the utilizing instruction further includes:
(a1) calculating a binary hash value for each of the plurality of column values.
(b) transferring each bit map generated in each node in the plurality of nodes to a coordinator node designated from the plurality of nodes;
(c) merging each bit map in the coordinator node into a merged bit map by executing a logical, bit-wise OR operation on the bit maps; and
(d) calculating an estimated column cardinality value for the table from the merged bit map.

### Claim 21 (depends on 20)

The computer readable medium of claim 20, wherein the utilizing instruction (a) further comprises:
(a2) transforming each binary hash value by retaining a leftmost 1 bit in the binary hash value and replacing all other 1 bits in the binary hash value with 0 values; and
(a3) performing a logical OR operation on the transformed binary hash value with a bit map value for the column in the node.

### Claim 22 (depends on 20)

The computer readable medium of claim 20, wherein the calculating instruction (d) further comprising:
(d1) dividing 2 raised to a power of the leftmost position of a 0 bit in the merged bit map by a defined parameter related to a size of the bit map, and
(d2) correcting the estimate to account for hash function collisions.

### Claim 23

A method for estimating a column cardinality value for a column having a plurality of values in a partitioned table stored in a plurality of nodes in a relational database, the method comprising the steps of:
(a) utilizing a sample counting technique to generate a respective list of hash values for each node in the plurality of nodes by hashing the column values for the partitioned table stored in each node, wherein hash values in the list are filtered when the list exceeds a predetermined length;
(b) transferring each of the list of hash values from each node in the plurality of nodes to a coordinator node;
(c) merging each of the respective lists of hash data values into a merged list, and
(d) calculating an estimated column cardinality value for the table from the merged list.

### Claim 24

A computer readable medium containing programming instructions for estimating a column cardinality value for a column having a plurality of values in a partitioned table stored in a plurality of nodes in a relational database, the programming instructions for:
(a) utilizing a sample counting technique to generate a respective list of hash values for each node in the plurality of nodes by hashing the column values for the partitioned table stored in each node, wherein hash values in the list are filtered when the list exceeds a predetermined length;
(b) transferring each of the list of hash values from each node in the plurality of nodes to a coordinator node;
(c) merging each of the respective lists of hash data values into a merged list, and
(d) calculating an estimated column cardinality value for the table from the merged list.
