Algorithm to apply a predicate to data sets

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.

What is claimed is: 
     
         1 . A method of analyzing 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 digital data set and second digital data set comprising at least one digital element sorted according to the predicate criterion, comprising:
 (a) receiving an evaluation request, wherein the evaluation request includes the predicate;   (b) partitioning each data set into a plurality of sub-groups, wherein each sub-group has an upper boundary element and a lower boundary element defining a range for each sub-group;   (c) evaluating a probability of the predicate being satisfied by at least one element of each sub-group 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, wherein pairs of sub-groups are evaluated in a sub-group pairing, wherein the probability is evaluated by determining whether a range of a first sub-group in the sub-group pairing overlaps a range of a second sub-group in the sub-group pairing to define an interaction between the first sub-group and the second sub-group of sub-group pairing;   (d) 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 sub-group pairing, wherein zero probability sub-group pairings are excluded from further processing to provide efficient use of processing resources;   (e) 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;   (f) for each non-zero probability sub-group pairing, recursively repeat steps (b) to (e) until the partitioning step results in base case sub-groups for both data sets; and   (g) performing a predicate evaluation of the elements within each base case subgroup pairing to determine a result for the evaluation request.   
     
     
         2 . The method as in  claim 1  further comprising generating an output digital data set, wherein the digital data set comprises base case sub-group pairings where the predicate evaluation is true. 
     
     
         3 . The method as in  claim 1  in which steps (a) to (d) are carried out by a single core in a first instance. 
     
     
         4 . The method as in  claim 3  in which steps (a) to (d) are carried out by a single core in each recursion. 
     
     
         5 . The method as in  claim 1  in which the base case sub-group is defined in relation to hardware on which the method will be carried out, a nature of the predicate, and a nature of the data. 
     
     
         6 . The method as in  claim 1  comprising storing the elements of at least one of the sorted digital data sets in consecutive memory address locations. 
     
     
         7 . The method as in  claim 1  in which the step of partitioning further comprises identifying a memory location of the upper boundary element and the memory location of the lower boundary element of a sub-group and retrieving the elements stored therein. 
     
     
         8 . The method as in  claim 1  in which a processing device is a Graphics Processing Unit (GPU). 
     
     
         9 . The method as in  claim 1  implemented across a cluster of computing devices, each computing device comprising a plurality of computing cores. 
     
     
         10 . A non-transitory machine readable storage medium including instructions embodied thereon, the instructions when executed by the plurality of computing cores perform the method as set out in  claim 1 . 
     
     
         11 . The method as in  claim 1 , further comprising performing a sort operation with the first digital data set and the second digital data set. 
     
     
         12 . The method as in  claim 1 , further comprising performing a merge join operation with the first digital data set and the second digital data set. 
     
     
         13 . The method as in  claim 1 , further comprising performing a filter operation using the first digital data set and the second digital data set. 
     
     
         14 . An apparatus for analyzing digital data sets included 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) receive a request for an evaluation operation, wherein the request for the evaluation includes the predicate;   (b) partition each data set into a plurality of sub-groups, each sub-group having an upper boundary element and a lower boundary element defining a range for each sub-group;   (c) for each sub-group of the first data set, evaluate a 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, wherein the probability is evaluated by determining whether a range of a first sub-group in the sub-group pairing overlaps a range of a second sub-group in the sub-group pairing to define an interaction between the first sub-group and the second sub-group of sub-group pairing;   (d) 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 sub-group pairing, wherein zero probability sub-group pairings are excluded from further processing to provide efficient use of processing resources;   (e) 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;   (f) for each non-zero probability sub-group pairing, recursively repeat steps (b) to (e) until the partitioning step results in base case sub-groups for both data sets;   (g) perform a predicate evaluation of the elements within each base case sub-group pairing; and   (h) combining digital elements in the base case sub-groups for both data sets where the predicate evaluation is true to identify results for the evaluation operation.   
     
     
         15 . The apparatus as in  claim 14  further adapted to generate an output digital data set comprising the base case sub-group pairings where the predicate evaluation is true. 
     
     
         16 . The apparatus as in  claim 14  wherein the elements of at least one of the sorted digital data sets are stored in the memory in consecutive memory address locations. 
     
     
         17 . The apparatus as in  claim 14  in which the processing device comprises a Single Program Multiple Data (SPMD) parallel computing architecture. 
     
     
         18 . The apparatus as in  claim 14 , further comprising performing a sort operation with the first digital data set and the second digital data set. 
     
     
         19 . The apparatus as in  claim 14 , further comprising performing a merge join operation with the first digital data set and the second digital data set. 
     
     
         20 . The apparatus as in  claim 14 , further comprising performing a filter operation using the first digital data set and the second digital data set.