Implementing multidimensional two-sided interval joins using sampling-based input-domain demarcation

A data platform comprising:

• one or more hardware processors;
• and
• one or more non-transitory computer-readable storage media containing instructions that, when executed by the one or more hardware processors, cause the one or more hardware processors to perform operations comprising:
• receiving a query that includes a two-sided N-dimensional interval join of first and second input relations, the interval join having an interval-join predicate that, in each of N dimensions, compares an interval determined from the first input relation with an interval determined from the second input relation;
• sampling, with respect to each of one or more of the N dimensions, one or both of the first input relation and the second input relation with respect to an interval size of the interval determined from the corresponding input relation;
• demarcating an N-dimensional input domain into a plurality of non-overlapping N-dimensional input-domain cells based at least in part on the sampling;
• implementing the interval join using a query-execution plan that includes an equality join that is keyed on input-domain-cell identifiers of input-domain cells of the N-dimensional input domain that at least partially overlap bounding polygons of the intervals determined from the first and second input relations, the equality join being followed in the query-execution plan by a filter that applies the interval-join predicate;
• and
• obtaining results of the query by executing the query-execution plan.

One or more non-transitory computer-readable storage media storing instructions that, when executed by one or more hardware processors, cause the one or more hardware processors to perform operations comprising:

• receiving a query that includes a two-sided N-dimensional interval join of first and second input relations, the interval join having an interval-join predicate that, in each of N dimensions, compares an interval determined from the first input relation with an interval determined from the second input relation;
• sampling, with respect to each of one or more of the N dimensions, one or both of the first input relation and the second input relation with respect to an interval size of the interval determined from the corresponding input relation;
• demarcating an N-dimensional input domain into a plurality of non-overlapping N-dimensional input-domain cells based at least in part on the sampling;
• implementing the interval join using a query-execution plan that includes an equality join that is keyed on input-domain-cell identifiers of input-domain cells of the N-dimensional input domain that at least partially overlap bounding polygons of the intervals determined from the first and second input relations, the equality join being followed in the query-execution plan by a filter that applies the interval-join predicate;
• and
• obtaining results of the query by executing the query-execution plan.