Granted Patent B2

US 12,639,322 · App. 18/946,348 · Granted May 26, 2026

Inventors: Young Goo Cho (Seoul, KR); Jaehyok Chong (Seoul, KR)

Assignee: SAP SE

G06F16/2462G06F16/2453

Abstract

Claims (113)

1 . A computer-implemented method for improving query optimization, comprising:

receiving a query for a database table, wherein the query has a filter comprising a first predicate and a second predicate, wherein the first predicate specifies a first condition evaluating data values in a first column of the database table and the second predicate specifies a second condition evaluating data values in a second column of the database table;

obtaining a projection histogram comprising base statistics of the first column and projected statistics of the second column;

determining an output size of the filter based on the projection histogram,

wherein determining the output size of the filter comprises:

determining a group size based on evaluating the base statistics of the projection histogram using the first condition; and

evaluating the projected statistics of the projection histogram using the second condition,

wherein the output size is determined based on the group size and results of evaluating the projected statistics; and

generating a query plan based on the determined output size of the filter,

wherein the base statistics of the first column comprise a plurality of intervals and respective counts of cells in the first column whose data values are within corresponding intervals, wherein a selected interval defines a set of rows containing a first set of cells in the first column whose data values are within the selected interval,

wherein the projected statistics of the second column comprise a plurality of ranges corresponding to the plurality of intervals, respectively, wherein the set of rows defined by the selected interval contains a second set of cells in the second column, wherein a range corresponding to the selected interval is defined by a minimum and a maximum of data values in the second set of cells.

2 . The computer-implemented method of claim 1 , wherein the first predicate and the second predicate have a conjunctive relationship, wherein determining the output size of the filter further comprises:

adjusting the group size based on the results of evaluating the projected statistics.

3 . The computer-implemented method of claim 2 , wherein determining the group size comprises:

identifying a matching interval in the projection histogram which contains at least some data values in the first column that meet the first condition and a count corresponding to the matching interval;

determining a fraction of the matching interval in which the data values in the first column meet the first condition; and

multiplying the count by the fraction of the matching interval.

4 . The computer-implemented method of claim 3 , wherein adjusting the group size comprises:

identifying a range corresponding to the matching interval;

determining a fraction of the range in which the data values in the second column meet the second condition; and

multiplying the group size by the fraction of the range.

5 . The computer-implemented method of claim 3 , wherein the matching interval is one of a plurality of matching intervals, wherein the plurality of matching intervals has corresponding adjusted group sizes, wherein determining the output size of the filter further comprises summing the adjusted group sizes corresponding to the plurality of matching intervals.

6 . The computer-implemented method of claim 2 , wherein the filter further comprises a third predicate which specifies a third condition evaluating data values in a third column of the database table, wherein the second predicate and the third predicate also have a conjunctive relationship,

wherein the projection histogram is a first projection histogram, wherein the group size is a first group size, wherein determining the output size of the filter further comprises:

obtaining a second projection histogram comprising base statistics of the second column and projected statistics of the third column;

determining a second group size based on evaluating the base statistics of the second projection histogram using the second condition;

adjusting the second group size based on evaluating the projected statistics of the second projection histogram using the third condition;

determining a first selectivity as a ratio of the first group size to a total number of rows in the database table;

determining a second selectivity as a ratio of the second group size to the total number of rows in the database table; and

determining a product of the first selectivity and the second selectivity.

7 . The computer-implemented method of claim 1 , wherein the first predicate and the second predicate have a disjunctive relationship, wherein the group size is a first group size, wherein determining the output size of the filter further comprises:

determining a second group size based on evaluating the base statistics of the projection histogram using the first condition and the results of evaluating the projected statistics; and

calculating a sum of the first group size and the second group size.

8 . The computer-implemented method of claim 7 , wherein determining the first group size comprises:

identifying one or more matching intervals in the projection histogram which contain at least some data values in the first column that meet the first condition and respective counts corresponding to the one or more matching intervals;

determining respective fractions of the one or more matching intervals in which the data values in the first column meet the first condition; and

calculating a sum of products of the counts and their respective fractions of the one or more matching intervals.

9 . The computer-implemented method of claim 8 , wherein determining the second group size comprises:

identifying one or more non-matching intervals in the projection histogram which contain at least some data values in the first column that do not meet the first condition and respective counts corresponding to the one or more non-matching intervals;

determining respective fractions of the one or more non-matching intervals in which the data values in the first column do not meet the first condition;

calculating non-matching counts as products of the counts and their respective fractions of the one or more non-matching intervals;

identifying one or more ranges corresponding to the one or more non-matching intervals, respectively;

determining respective fractions of the one or more ranges in which the data values in the second column meet the second condition; and

calculating a sum of products of the non-matching counts and their respective fractions of the one or more ranges.

10 . The computer-implemented method of claim 9 , wherein the filter further comprises a third predicate which specifies a third condition evaluating the data values in a third column of the database table, wherein the second predicate and the third predicate also have a disjunctive relationship,

wherein the projection histogram is a first projection histogram, wherein the one or more non-matching intervals are first non-matching intervals, the one or more ranges are first ranges, and the non-matching counts are first non-matching counts, wherein determining the output size of the filter further comprises:

obtaining a second projection histogram comprising base statistics of the second column and projected statistics of the third column;

determining a third group size based on evaluating both the base statistics of the second projection histogram using the second condition and the projected statistics of the second projection histogram using the third condition; and

adding the third group size to the sum of the first group size and the second group size, wherein determining the third group size comprises:

identifying one or more second non-matching intervals in the second projection histogram which contain at least some data values in the second column that do not meet the second condition and respective counts corresponding to the one or more second non-matching intervals;

determining respective fractions of the one or more second non-matching intervals in which the data values in the second column do not meet the second condition;

calculating second non-matching counts as products of the counts and their respective fractions of the one or more second non-matching intervals;

identifying one or more second ranges corresponding to the one or more second non-matching intervals, respectively;

determining respective fractions of the one or more second ranges in which the data values in the third column meet the third condition; and

calculating a sum of products of the second non-matching counts and their respective fractions of the one or more second ranges.

11 . A computing system for improving query optimization, comprising:

memory;

one or more hardware processors coupled to the memory; and

one or more non-transitory computer-readable media storing instructions that, when loaded into the memory, cause the one or more hardware processors to perform operations comprising:

receiving a query for a database table, wherein the query has a filter comprising a first predicate and a second predicate, wherein the first predicate specifies a first condition evaluating data values in a first column of the database table and the second predicate specifies a second condition evaluating data values in a second column of the database table;

obtaining a projection histogram comprising base statistics of the first column and projected statistics of the second column;

determining an output size of the filter based on the projection histogram,

wherein determining the output size of the filter comprises:

determining a group size based on evaluating the base statistics of the projection histogram using the first condition; and

evaluating the projected statistics of the projection histogram using the second condition,

wherein the output size is determined based on the group size and results of evaluating the projected statistics; and

generating a query plan based on the determined output size of the filter,

wherein the base statistics of the first column comprise a plurality of intervals and respective counts of cells in the first column whose data values are within corresponding intervals, wherein a selected interval defines a set of rows containing a first set of cells in the first column whose data values are within the selected interval,

wherein the projected statistics of the second column comprise a plurality of ranges corresponding to the plurality of intervals, respectively, wherein the set of rows defined by the selected interval contains a second set of cells in the second column, wherein a range corresponding to the selected interval is defined by a minimum and a maximum of data values in the second set of cells.

12 . The computing system of claim 11 , wherein the first predicate and the second predicate have a conjunctive relationship, wherein determining the output size of the filter further comprises:

adjusting the group size based on the results of evaluating the projected statistics.

13 . The computing system of claim 12 , wherein determining the group size comprises:

identifying a matching interval in the projection histogram which contains at least some data values in the first column that meet the first condition and a count corresponding to the matching interval;

determining a fraction of the matching interval in which the data values in the first column meet the first condition; and

multiplying the count by the fraction of the matching interval.

14 . The computing system of claim 13 , wherein adjusting the group size comprises:

identifying a range corresponding to the matching interval;

determining a fraction of the range in which the data values in the second column meet the second condition; and

multiplying the group size by the fraction of the range.

15 . The computing system of claim 13 , wherein the matching interval is one of a plurality of matching intervals, wherein the plurality of matching intervals has corresponding adjusted group sizes, wherein determining the output size of the filter further comprises summing the adjusted group sizes corresponding to the plurality of matching intervals.

16 . The computing system of claim 12 , wherein the filter further comprises a third predicate which specifies a third condition evaluating data values in a third column of the database table, wherein the second predicate and the third predicate also have a conjunctive relationship,

wherein the projection histogram is a first projection histogram, wherein the group size is a first group size, wherein determining the output size of the filter further comprises:

obtaining a second projection histogram comprising base statistics of the second column and projected statistics of the third column;

determining a second group size based on evaluating the base statistics of the second projection histogram using the second condition;

adjusting the second group size based on evaluating the projected statistics of the second projection histogram using the third condition;

determining a first selectivity as a ratio of the first group size to a total number of rows in the database table;

determining a second selectivity as a ratio of the second group size to the total number of rows in the database table; and

determining a product of the first selectivity and the second selectivity.

17 . The computing system of claim 11 , wherein the first predicate and the second predicate have a disjunctive relationship, wherein the group size is a first group size, wherein determining the output size of the filter further comprises:

determining a second group size based on evaluating the base statistics of the projection histogram using the first condition and the results of evaluating the projected statistics; and

calculating a sum of the first group size and the second group size.

18 . The computing system of claim 17 , wherein determining the first group size comprises:

identifying one or more matching intervals in the projection histogram which contain at least some data values in the first column that meet the first condition and respective counts corresponding to the one or more matching intervals;

determining respective fractions of the one or more matching intervals in which the data values in the first column meet the first condition; and

calculating a sum of products of the counts and their respective fractions of the one or more matching intervals.

19 . The computing system of claim 18 , wherein determining the second group size comprises:

identifying one or more non-matching intervals in the projection histogram which contain at least some data values in the first column that do not meet the first condition and respective counts corresponding to the one or more non-matching intervals;

determining respective fractions of the one or more non-matching intervals in which the data values in the first column do not meet the first condition;

calculating non-matching counts as products of the counts and their respective fractions of the one or more non-matching intervals;

identifying one or more ranges corresponding to the one or more non-matching intervals, respectively;

determining respective fractions of the one or more ranges in which the data values in the second column meet the second condition; and

calculating a sum of products of the non-matching counts and their respective fractions of the one or more ranges.

20 . One or more non-transitory computer-readable media having encoded thereon computer-executable instructions causing one or more processors to perform a method for improving query optimization, the method comprising:

receiving a query for a database table, wherein the query has a filter comprising a first predicate and a second predicate, wherein the first predicate specifies a first condition evaluating data values in a first column of the database table and the second predicate specifies a second condition evaluating data values in a second column of the database table;

obtaining a projection histogram comprising base statistics of the first column and projected statistics of the second column;

determining an output size of the filter based on the projection histogram,

wherein determining the output size of the filter comprises:

determining a group size based on evaluating the base statistics of the projection histogram using the first condition; and

evaluating the projected statistics of the projection histogram using the second condition,

wherein the output size is determined based on the group size and results of evaluating the projected statistics; and

generating a query plan based on the determined output size of the filter,

wherein the base statistics of the first column comprise a plurality of intervals and respective counts of cells in the first column whose data values are within corresponding intervals, wherein a selected interval defines a set of rows containing a first set of cells in the first column whose data values are within the selected interval,

wherein the projected statistics of the second column comprise a plurality of ranges corresponding to the plurality of intervals, respectively, wherein the set of rows defined by the selected interval contains a second set of cells in the second column, wherein a range corresponding to the selected interval is defined by a minimum and a maximum of data values in the second set of cells.

Assignments (1)

Continuity (1)

References Cited (32)