US 9,852,185 B2Granted

Approximate distinct counting in a bounded memory

AssigneeOracle International Corporation

InventorsHong Su, Mohamed Zait, Sunil Chakkappen

Life of this patent

Estimating the term…

Loading patent…

Abstract

A table is processed to determine an approximate NDV for a plurality of groups. For each row, a group based is identified based on one or more group-by columns. A hashed valued is generated by applying a uniform hash function to a value in an NDV column. The hashed value is assigned to a particular bucket based on the values at a first set of bit positions in a binary representation of the hashed value. A bit position value is determined based on for a remaining portion of the binary representation of the hashed value. The bit position value is based on a number of ordered bits in the hashed value that match a particular bit pattern. For each group identified, a maximum bit position (MBP) table is generated. The MBP table stores, for one or more buckets, the maximum bit position value determined for hashed values assigned to a particular bucket.

Claims22

Dependent claims

A method comprising:

processing rows in a portion of a table to determine an approximate number of distinct values (NDV) in an NDV column for a plurality of groups specified in a set of one or more group-by columns;
wherein each group of said plurality of groups is associated with a respective maximum bit position (MBP) table of a plurality of MBP tables, said respective MBP table including a respective plurality of buckets;
wherein processing said rows in said portion of said table includes, for each row of said rows;
identifying a respective group of said plurality of groups for said each row based on one or more row values in the set of one or more group-by columns;
generating a hashed value by applying a uniform hash function to a row value in the NDV column of said each row;
assigning the hashed value to a particular bucket of the respective MBP table of said respective group based on values at a first set of bit positions in a binary representation of the hashed value;
determining a bit position value based on a remaining portion of the binary representation of the hashed value, wherein the first set of bit positions are excluded from the remaining portion;
and
wherein the bit position value is based on a number of ordered bits in the hashed value that match a particular bit pattern;
for each group of said plurality of groups, generating a particular maximum bit position for each particular bucket of one or more buckets of the respective MBP table associated with said each group, comprising, for said each particular of said one or more buckets, a maximum bit position value determined for one or more hashed values assigned to said each particular bucket;
determining one or more approximate NDVs for one or more particular groups of the plurality of groups based on one or more MBP tables of said plurality of MBP tables;
and
wherein the method is performed by one or more computing devices.

10 more elements

One or more non-transitory storage media storing one or more sequences of instructions, which when executed by one or more computing devices, cause:

processing rows in a portion of a table to determine an approximate number of distinct values (NDV) in an NDV column for a plurality of groups specified in a set of one or more group-by columns;
wherein each group of said plurality of groups is associated with a respective maximum bit position (MBP) table of a plurality of MBP tables, said respective MBP table including a respective plurality of buckets;
wherein processing said rows in said portion of said table includes, for each row of said rows;
identifying a respective group of said plurality of groups for said each row based on one or more row values in the set of one or more group-by columns;
generating a hashed value by applying a uniform hash function to a row value in the NDV column of said each row;
assigning the hashed value to a particular bucket of the respective MBP table of said respective group based on values at a first set of bit positions in a binary representation of the hashed value;
determining a bit position value based on a remaining portion of the binary representation of the hashed value, wherein the first set of bit positions are excluded from the remaining portion;
and
wherein the bit position value is based on a number of ordered bits in the hashed value that match a particular bit pattern;
for each group of said plurality of groups, generating a particular maximum bit position for each particular bucket of one or more buckets of the respective MBP table associated with said each group, comprising, for said each particular bucket of said one or more buckets, a maximum bit position value determined for one or more hashed values assigned to said each particular bucket;
and
determining one or more approximate NDVs for one or more particular groups of the plurality of groups based on one or more MBP tables of said plurality of MBP tables.

9 more elements

Dependencies are inferred from the claim text.