Push down top-k information for query plan optimization
Various example embodiments described herein provide for systems, methods, devices, instructions, and the like for optimizing a query plan to execute a query by pushing down top-k information in the query plan, which can be used within a data platform (e.g., database) environment. In particular, various example embodiments enable information from a top-k operator of a query plan to be pushed down the query plan and enable pushing the information through one or more outer join operators (e.g., through multiple levels of outer join operators) of the query plan to a select operator, such as an aggregation operator, positioned below the one or more outer join operators.
1 . A system comprising:
at least one processor; and
at least one memory storing instructions that cause the at least one processor to perform operations comprising:
accessing a query plan for execution on a plurality of tables of a database, the query plan comprising a plurality of operators, the plurality of operators comprising a top-k operator and an outer join operator positioned below the top-k operator in the query plan, the top-k operator being configured to order rows by a set of order-by keys and to limit a number of rows provided by the top-k operator to a specific number of rows, the outer join operator being configured to join rows received from at least two nodes of the query plan based on a set of join keys;
determining, below the top-k operator in the query plan, a series of aggregation operators that each have an individual set of group-by keys that includes the set of order-by keys;
modifying the query plan by changing a last aggregation operator in the series of aggregation operators to a top-k aggregation operator that applies a top-k operation based on information from the top-k operator, the last aggregation operator being positioned below an outer join operator in the query plan; and
executing the modified query plan on the plurality of tables of the database, the executing of the modified query plan comprising the top-k aggregation operator actively filtering rows during runtime to reduce the number of rows processed by the outer join operator.
2 . The system of claim 1 , wherein the changing of the last aggregation operator in the series of aggregation operators to the top-k aggregation operator comprises:
comparing a select set of group-by keys of the top-k aggregation operator and a parent set of group-by keys of a parent aggregation operator positioned above the outer join operator in the query plan; and
based on a result of the comparing of the select set of group-by keys and the parent set of group-by keys, configuring how the top-k aggregation operator tracks unique groupings for the top-k operation.
3 . The system of claim 2 , wherein the configuring of how the top-k aggregation operator tracks unique groupings for the top-k operation comprises:
in response to determining that the select set of group-by keys and the parent set of group-by keys are the same, configuring the top-k aggregation operator to check whether a received row is already in a hash table of the top-k aggregation operator prior to the top-k aggregation operator inserting a received row into a data structure of the top-k aggregation operator as a new row, the data structure being used by the top-k aggregation operator to track unique groupings for the top-k operation.
4 . The system of claim 3 , wherein the data structure comprises a heap.
5 . The system of claim 2 , wherein the configuring of how the top-k aggregation operator tracks unique groupings for the top-k operation comprises:
in response to determining that the select set of group-by keys is a subset of the parent set of group-by keys, configuring the top-k aggregation operator to check whether a received row is already in a hash table of the top-k aggregation operator prior to the top-k aggregation operator inserting a received row into a data structure of the top-k aggregation operator as a new row, the data structure being used by the top-k aggregation operator to track unique groupings for the top-k operation.
6 . The system of claim 5 , wherein the data structure comprises a heap.
7 . The system of claim 2 , wherein the configuring of how the top-k aggregation operator tracks unique groupings for the top-k operation comprises:
in response to determining that the select set of group-by keys is a superset in comparison to the parent set of group-by keys, configuring the top-k aggregation operator to check a number of unique groups in a data structure of the top-k aggregation operator based on the parent set of group-by keys prior to the top-k aggregation operator inserting a received row into the data structure as a new row, the data structure being used by the top-k aggregation operator to track unique groupings for the top-k operation.
8 . The system of claim 7 , wherein the data structure comprises an ordered data structure.
9 . The system of claim 1 , wherein any aggregation operators in the series of aggregation operators that is under at least one outer join is on a preserve side of the at least one outer join.
10 . The system of claim 1 , wherein the information comprises a parent set of group-by keys of a parent aggregation operator positioned above the outer join operator.
11 . The system of claim 1 , wherein the information comprises a limit of the top-k operator.
12 . The system of claim 1 , wherein the information comprises the set of order-by keys of the top-k operator.
13 . The system of claim 1 , wherein the operations comprise:
receiving a query that comprises a GROUP BY clause specifying one or more group-by keys, an ORDER BY clause specifying one or more order-by keys, a LIMIT clause specifying the specific number of rows, and one or more OUTER JOIN clauses each specifying an outer join of multiple tables and one or more join keys for the outer join; and
based on the query, generating the query plan to execute the query.
14 . A method comprising:
accessing, by at least one processor, a query plan for execution on a plurality of tables of a database, the query plan comprising a plurality of operators, the plurality of operators comprising a top-k operator and an outer join operator positioned below the top-k operator in the query plan, the top-k operator being configured to order rows by a set of order-by keys and to limit a number of rows provided by the top-k operator to a specific number of rows, the outer join operator being configured to join rows received from at least two nodes of the query plan based on a join key;
determining, by the at least one processor and below the top-k operator in the query plan, a series of aggregation operators that each have an individual set of group-by keys that includes the set of order-by keys;
modifying, by the at least one processor, the query plan by changing a last aggregation operator in the series of aggregation operators to a top-k aggregation operator that applies a top-k operation based on information from the top-k operator, the last aggregation operator being positioned below an outer join operator in the query plan; and
executing, by the at least one processor, the modified query plan on the plurality of tables of the database, the executing of the modified query plan comprising the top-k aggregation operator actively filtering rows during runtime to reduce the number of rows processed by the outer join operator.
15 . The method of claim 14 , wherein the changing of the last aggregation operator in the series of aggregation operators to the top-k aggregation operator comprises:
comparing a select set of group-by keys of the top-k aggregation operator and a parent set of group-by keys of a parent aggregation operator positioned above the outer join operator in the query plan; and
based on a result of the comparing of the select set of group-by keys and the parent set of group-by keys, configuring how the top-k aggregation operator tracks unique groupings for the top-k operation.
16 . The method of claim 15 , wherein the configuring of how the top-k aggregation operator tracks unique groupings for the top-k operation comprises:
in response to determining that the select set of group-by keys and the parent set of group-by keys are the same, configuring the top-k aggregation operator to check whether a received row is already in a hash table of the top-k aggregation operator prior to the top-k aggregation operator inserting a received row into a data structure of the top-k aggregation operator as a new row, the data structure being used by the top-k aggregation operator to track unique groupings for the top-k operation.
17 . The method of claim 15 , wherein the configuring of how the top-k aggregation operator tracks unique groupings for the top-k operation comprises:
in response to determining that the select set of group-by keys is a subset of the parent set of group-by keys, configuring the top-k aggregation operator to check whether a received row is already in a hash table of the top-k aggregation operator prior to the top-k aggregation operator inserting a received row into a data structure of the top-k aggregation operator as a new row, the data structure being used by the top-k aggregation operator to track unique groupings for the top-k operation.
18 . The method of claim 15 , wherein the configuring of how the top-k aggregation operator tracks unique groupings for the top-k operation comprises:
in response to determining that the select set of group-by keys is a superset in comparison to the parent set of group-by keys, configuring the top-k aggregation operator to check a number of unique groups in a data structure of the top-k aggregation operator based on the parent set of group-by keys prior to the top-k aggregation operator inserting a received row into the data structure as a new row, the data structure being used by the top-k aggregation operator to track unique groupings for the top-k operation.
19 . The method of claim 14 , wherein any aggregation operators in the series of aggregation operators that is under at least one outer join is on a preserve side of the at least one outer join.
20 . A non-transitory machine-storage medium storing instructions that when executed by a machine, cause the machine to perform operations comprising:
accessing a query plan for execution on a plurality of tables of a database, the query plan comprising a plurality of operators, the plurality of operators comprising a top-k operator and an outer join operator positioned below the top-k operator in the query plan, the top-k operator being configured to order rows by a set of order-by keys and to limit a number of rows provided by the top-k operator to a specific number of rows, the outer join operator being configured to join rows received from at least two nodes of the query plan based on a join key;
determining, below the top-k operator in the query plan, a series of aggregation operators that each have an individual set of group-by keys that includes the set of order-by keys;
modifying the query plan by changing a last aggregation operator in the series of aggregation operators to a top-k aggregation operator that applies a top-k operation based on information from the top-k operator, the last aggregation operator being positioned below an outer join operator in the query plan; and
executing the modified query plan on the plurality of tables of the database, the executing of the modified query plan comprising the top-k aggregation operator actively filtering rows during runtime to reduce the number of rows processed by the outer join operator.