US 10,884,704 B2Granted

Sorting a table in analytical databases

AssigneeInternational Business Machines Corporation

InventorsFelix Beier, Andreas Brodt, Oliver Schiller, Knut Stolze

Life of this patent

Estimating the term…

Loading patent…

Abstract

A computer-implemented method, a system, and a computer program product for sorting a data table by an attribute of the data table is provided. Each data block of the data table is provided with attribute value information being indicative of distinct values and/or ranges of values of the attribute in each of the data blocks of the data table. Distinct ranges and/or distinct values of the attribute of the data table are derived from the attribute value information. For each determined distinct range and/or distinct value, a bucket may be created. For each created bucket, it may be determined, using the attribute value information, which data block of the data table is to be scanned. Each scanned record is distributed to a corresponding bucket. The entries or records in each bucket having more than one record, may be sorted by the attribute.

Claims16

Dependent claims

A computer implemented method for sorting a data table by an attribute of the data table, attribute value information being provided for data blocks of the data table, the attribute value information being indicative of distinct values and/or ranges of values of the attribute in each of the data blocks of the data table;

the method comprising:
deriving from the attribute value information distinct ranges and/or distinct values of the attribute of the data table, and for each determined distinct range and/or distinct value creating a bucket;
for each created bucket determining using the attribute value information which data block of the data table is to be scanned;
scanning records of the determined data blocks and distributing each scanned record to a corresponding bucket of the buckets created for each of the determined distinct range and/or distinct values;
sorting by the attribute the entries in each of the buckets having more than one record;
and
providing the buckets in the sort order as the sorted data table;
wherein the attribute value information further comprising the extremum values, min, max of the attribute in each data block of the data table, the deriving of the distinct values comprising:
iterating over all 1-bits in the bloom filter, and for every 1-bit position h executing the following steps:
determining kmin and kmax as follows:
k
⁢
⁢
min
=
min
*
a
-
h
b
⁢
⁢
and
⁢
⁢
k
⁢
⁢
max
=
max
*
a
-
h
b
,
where b is the number of bits in the bloom filter and a is a predefined value;
and for every value k in the range [kmin;
kmax] compute a candidate distinct value xk
x
k
=
k
*
b
+
h
a
that can set the bit h.

48 more elements

A system for sorting a data table by an attribute of the data table, attribute value information being provided for data blocks of the data table, the attribute value information being indicative of distinct values and/or ranges of values of the attribute in each of the data blocks of the data table, the system comprising:

a computer system comprising:
a computer processor, a computer-readable storage medium, and program instructions stored on the computer-readable storage medium being executable by the processor, to cause the computer system to perform a method, comprising:
deriving from the attribute value information distinct ranges and/or distinct values of the attribute of the data table, and for each determined distinct range and/or distinct value creating a bucket;
for each created bucket determining using the attribute value information which data block of the data table is to be scanned;
scanning records of the determined data blocks and distributing each scanned record to a corresponding bucket of the buckets created for each of the determined distinct range and/or distinct values;
sorting by the attribute the entries in each of the buckets having more than one record;
and
providing the buckets in the sort order as the sorted data table;
wherein the attribute value information further comprising the extremum values, min, max of the attribute in each data block of the data table, the deriving of the distinct values comprising:
iterating over all 1-bits in the bloom filter, and for every 1-bit position h executing the following steps:
determining kmin and kmax as follows:
k
⁢
⁢
min
=
min
*
a
-
h
b
⁢
⁢
and
⁢
⁢
k
⁢
⁢
max
=
max
*
a
-
h
b
,
where b is the number of bits in the bloom filter and a is a predefined value;
and for every value k in the range [kmin;
kmax] compute a candidate distinct value xk
x
k
=
k
*
b
+
h
a
that can set the bit h.

49 more elements

A computer program product for sorting a data table by an attribute of the data table, attribute value information being provided for data blocks of the data table, the attribute value information being indicative of distinct values and/or ranges of values of the attribute in each of the data blocks of the data table, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, wherein the computer readable storage medium is not a transitory signal per se, the program instructions executable by a computer to cause the computer to perform a method, comprising:

deriving from the attribute value information distinct ranges and/or distinct values of the attribute of the data table, and for each determined distinct range and/or distinct value creating a bucket;
for each created bucket determining using the attribute value information which data block of the data table is to be scanned;
scanning records of the determined data blocks and distributing each scanned record to a corresponding bucket of the buckets created for each of the determined distinct range and/or distinct values;
sorting by the attribute the entries in each of the buckets having more than one record;
and
providing the buckets in the sort order as the sorted data table;
wherein the attribute value information further comprising the extremum values, min, max of the attribute in each data block of the data table, the deriving of the distinct values comprising:
iterating over all 1-bits in the bloom filter, and for every 1-bit position h executing the following steps:
determining kmin and kmax as follows:
k
⁢
⁢
min
=
min
*
a
-
h
b
⁢
⁢
and
⁢
⁢
k
⁢
⁢
max
=
max
*
a
-
h
b
,
where b is the number of bits in the bloom filter and a is a predefined value;
and for every value k in the range [kmin;
kmax] compute a candidate distinct value xk
x
k
=
k
*
b
+
h
a
that can set the bit h.

47 more elements

Dependencies are inferred from the claim text.