Systems and methods for accelerating and optimizing groupwise comparison in relational databases

A method of executing SQL statements using a database management system (DBMS), the method comprising:

• receiving an SQL statement that identifies a first trendset and a second trendset, each of the first and the second trendsets including one or more trends, each of the trends being designated by a constraint and a grouping-measure combination, and that instructs a database to compare the first trendset and the second trendset over a relation in the database using a scoring function, wherein comparing the first and the second trendsets includes identifying trend pairs for comparison, each of the trend pairs including a trend from the first trendset and a trend from the second trendset having a common grouping-measure combination;
• transforming the SQL statement into a basic plan of existing logical operators for performing the SQL statement using a query optimizer;
• determining a set of sub-plans based on the basic plan, the set of sub-plans having one sub-plan for each grouping-measure combination, each of the sub-plans including a sequence of group-by aggregate, join and partition operations over one of the respective grouping-measure combinations;
• merging pairs of sub-plans from the set of sub-plans by merging group by aggregates and using vertical and horizontal partitioning to generate a set of merged sub-plans;
• determining a respective cost for each of the merged sub-plans based on costs of physical operators used to perform each of the merged sub-plans using the query optimizer;
• and
• using the merged sub-plan having lowest cost to execute the SQL statement,
• wherein the constraint of each of the trends is an attribute value used to identify a subset of tuples from the relation, and
• wherein the grouping-measure combination of each of the trends includes a grouping and a measure, the grouping being an attribute value that designates tuples in the subset of tuples for aggregation, the measure indicating an aggregate function over one or more attributes for performing the aggregation.

A non-transitory computer readable medium on which are stored instructions that, when executed, cause a programmable device to perform functions of:

• receiving an SQL statement that identifies a first trendset and a second trendset, each of the first and the second trendsets including one or more trends, each of the trends being designated by a constraint and a grouping-measure combination, and that instructs a database to compare the first trendset and the second trendset over a relation in the database using a scoring function, wherein comparing the first and the second trendsets includes identifying trend pairs for comparison, each of the trend pairs including a trend from the first trendset and a trend from the second trendset having a common grouping-measure combination;
• transforming the SQL statement into a basic plan of existing logical operators for performing the SQL statement using a query optimizer;
• determining a set of sub-plans based on the basic plan, the set of sub-plans having one sub-plan for each grouping-measure combination, each of the sub-plans including a sequence of group-by aggregate, join and partition operations over one of the respective grouping-measure combinations;
• merging pairs of sub-plans from the set of sub-plans by merging group by aggregates and using vertical and horizontal partitioning to generate a set of merged sub-plans;
• determining a respective cost for each of the merged sub-plans based on costs of physical operators used to perform each of the merged sub-plans using the query optimizer;
• and
• using the merged sub-plan having lowest cost to execute the SQL statement,
• wherein the constraint of each of the trends is an attribute value used to identify a subset of tuples from the relation, and
• wherein the grouping-measure combination of each of the trends includes a grouping and a measure, the grouping being an attribute value that designates tuples in the subset of tuples for aggregation, the measure indicating an aggregate function over one or more attributes for performing the aggregation.