Algorithm to apply a predicate to data sets
AssigneeBrytlyt Limited
InventorRICHARD HEYNS
Life of this patent
Estimating the term…
Abstract
The present invention relates to a method and apparatus for analysing a pair of data sets with respect to a predicate, the predicate having a predicate criterion, each data set comprising one or more elements sorted according to the predicate criterion. The invention comprises recursive partitioning of the data sets in a parallel manner across multiple computing cores until a base case is reached. The invention is particularly suited for carrying out join, filter and sort operations on large data sets within database management systems.
Claims16
1-30. (canceled)
A method of analysing a first digital data set and a second digital data set with respect to a predicate, the predicate including a predicate criterion, each of the first and second data sets comprising at least one digital element sorted according to the predicate criterion, wherein the method is adapted to operate on a processing device, the processing device comprising a plurality of computing cores, and the steps of the method comprise:
- (a) partitioning each data set into a plurality of sub-groups, wherein each sub-group has an upper boundary element and a lower boundary element;
- (b) evaluating the probability of the predicate being satisfied by at least one element of each subgroup of the first data set and at least one element of each sub-group of the second data set, via analysis of the boundary elements of the sub-groups, where each pair of sub-groups evaluated is referred to as a “sub-group pairing”;
- (c) classifying a sub-group pairing as a “zero probability sub-group pairing” if there is a zero probability of the predicate being satisfied by the elements of the subgroup pairing;
- (d) classifying a sub-group pairing as “non-zero probability sub-group pairing” if there is a non-zero probability of the predicate being satisfied by the elements of the sub-group pairing;
- (e) for each non-zero probability sub-group pairing, recursively repeat steps (a) to
- (d) until the partitioning step results in base case sub-groups for both data sets, wherein the recursions are distributed among the plurality of cores;
- (f) performing a predicate evaluation of the elements within each base case subgroup pairing.
An apparatus for analysing digital data sets with respect to a predicate, the predicate including a predicate criterion, the apparatus comprising memory adapted to store a first digital data set and a second digital data set, each data set comprising one or more digital elements sorted according to the predicate criterion;
- and at least one processing device having a plurality of computing cores;
- the apparatus being adapted to:
- (a) partition each data set into a plurality of sub-groups, each sub-group having an upper boundary element and a lower boundary element;
- (b) for each sub-group of the first data set, evaluate the probability of the predicate being satisfied by at least one element of that sub-group and at least one element of each sub-group of the second data set by analysis of the boundary elements of the sub-groups, where each pair of sub-groups evaluated is referred to as a sub-group pairing;
- (c) classify a sub-group pairing as a zero probability sub-group pairing if there is a zero probability of the predicate being satisfied by the elements of the subgroup pairing;
- (d) classify a sub-group pairing as non-zero probability sub-group paring if there is a non-zero probability of the predicate being satisfied by the elements of the sub-group pairing;
- (e) for each non-zero probability sub-group pairing, recursively repeat steps (a) to
- (d) until the partitioning step results in base case sub-groups for both data sets, wherein the recursions are distributed among the plurality of cores;
- (f) perform a predicate evaluation of the elements within each base case sub- group pairing.
Dependencies are inferred from the claim text.