Generating an optimized join tree for execution of a plurality of join operations via a database system
A database system is operable to generating a query operator execution flow that includes an optimized join tree implementing a plurality of join operations applied to a plurality of input row sets based on: identifying a set of filter predicates indicated by the query expression and generating, based on the plurality of input row sets and the set of filter predicates, cardinality data for each of the plurality of input row sets. The optimized join tree is generated based on generating the optimized join tree based on selecting an ordering for applying the plurality of join operations to the plurality of input row sets based on the cardinality data for the each of the plurality of input row sets. The query operator execution flow is executed in conjunction with executing the query expression based on executing the plurality of join operators of the optimized join tree.
1 . A query and response sub-system of a database system comprises:
a plurality of computing device clusters, wherein a computing device cluster of the plurality of computing device clusters includes a plurality of computing devices, wherein a computing device of the plurality of computing devices includes a plurality of computing nodes, wherein a computing node of the plurality of computing nodes includes a plurality of processing core resources, wherein a set of processing core resources of the pluralities of processing core resources is operable to optimize memory usage during query execution by:
obtaining an initial query that includes a plurality of join operations involving a plurality of tables, wherein the plurality of join operations has an initial organizational structure of execution;
determining a plurality of cardinality values for the plurality of tables, wherein a first cardinality value of the plurality of cardinality values is regarding a first number of rows of a first table of the plurality of tables to be included in a join operation of the plurality of join operations;
determining an initial cumulative cardinality value for the initial organizational structure of execution of the plurality of join operations based on the plurality of cardinality values;
when the initial cumulative cardinality value compares favorably to an output cardinality threshold:
utilizing the initial organizational structure of execution in an optimized query plan; and
when the initial cumulative cardinality value compares unfavorably to the output cardinality threshold:
utilizing an optimized organizational structure of execution of the plurality of join operations in the optimized query plan.
2 . The query and response sub-system of claim 1 , wherein the set of processing core resources further determine the plurality of cardinality values based on:
metadata of the plurality of tables previously collected by the database system.
3 . The query and response sub-system of claim 1 , wherein the set of processing core resources is further operable to:
assign a plurality of join ID's to the plurality of tables, wherein a join ID of the plurality of join ID's is assigned to a table of the plurality of tables; and
store the plurality of table join ID's in distributed memory resources of the database system.
4 . The query and response sub-system of claim 1 , wherein the set of processing core resources is further operable to:
record the initial organizational structure of execution in metadata; and
access the recorded metadata to determine the optimized organizational structure of execution.
5 . The query and response sub-system of claim 1 , wherein the set of processing core resources is further operable to obtain the initial query by one of:
receiving the initial query;
generating the initial query; and
looking up the initial query from a plurality of stored queries in distributed memory resources of the database system.
6 . The query and response sub-system of claim 1 , wherein the set of processing core resources is further operable to determine the plurality of cardinality values by:
when the query indicates a filter to be applied to a table of the plurality of tables:
applying the filter to a number of rows of the table to produce filtered rows of the table; and
determining a cardinality value for the table based on the filtered rows.
7 . The query and response sub-system of claim 1 , wherein the set of processing core resources is further operable to determine the initial cumulative cardinality value based on:
a cumulative of cardinality values of the plurality of tables of the initial organizational structure of execution.
8 . The query and response sub-system of claim 1 , wherein the set of processing core resources is further operable to determine the initial cumulative cardinality value based on:
a cumulative of cardinality values of the plurality of tables of a layer of a plurality of layers of the initial organizational structure of execution.
9 . The query and response sub-system of claim 1 , wherein the set of processing core resources are further operable to:
create a plurality of alternative organizational structures of execution; and
selecting the most favorable alternative organizational structure of execution of the plurality of alternative organizational structures of execution based on the cardinality value of the plurality of tables.
10 . The query and response sub-system of claim 1 , wherein the set of processing core resources is further operable to:
create an alternative organizational structure of execution;
determine cardinality values of the plurality of tables of the alternative organizational structure of execution; and
when the cardinality values of the plurality of tables of the alternative organizational structure of execution compares favorably to the output cardinality threshold:
utilize the alternative organizational structure of execution of the plurality of join operations in the optimized query plan.
11 . A computer-readable memory comprises:
a first memory section that stores operational instructions that, when executed by a set of processing core resources of pluralities of processing core resources of a query and response sub-system of a database system to optimize memory usage during query execution, causes the set of processing core resources to:
obtain an initial query that includes a plurality of join operations involving a plurality of tables, wherein the plurality of join operations has an initial organizational structure of execution;
determine a plurality of cardinality values for the plurality of tables, wherein a first cardinality value of the plurality of cardinality values is regarding a first number of rows of a first table of the plurality of tables to be included in a join operation of the plurality of join operations;
determine an initial cumulative cardinality value for the initial organizational structure of execution of the plurality of join operations based on the plurality of cardinality values;
when the initial cumulative cardinality value compares favorably to an output cardinality threshold:
utilize the initial organizational structure of execution in an optimized query plan; and
when the initial cumulative cardinality value compares unfavorably to the output cardinality threshold:
utilize an optimized organizational structure of execution of the plurality of join operations in the optimized query plan.
12 . The computer-readable memory of claim 11 , wherein the first memory section further stores operational instructions that, when executed by the set of processing core resources, causes the set of processing core resources to:
determine the plurality of cardinality values based on metadata of the plurality of tables previously collected by the database system.
13 . The computer-readable memory of claim 11 , wherein the first memory section further stores operational instructions that, when executed by the set of processing core resources, causes the set of processing core resources to:
assign a plurality of table join ID's to the plurality of tables, wherein a join ID of the plurality of join ID's is assigned to a table of the plurality of tables; and
store the plurality of table join ID's in distributed memory resources of the database system.
14 . The computer-readable memory of claim 11 , wherein the first memory section further stores operational instructions that, when executed by the set of processing core resources, causes the set of processing core resources to:
record the initial organizational structure of execution in metadata; and
access the recorded metadata to determine the optimized organizational structure of execution.
15 . The computer-readable memory of claim 11 , wherein the first memory section further stores operational instructions that, when executed by the set of processing core resources, causes the set of processing core resources to obtain the initial query by one of:
receiving the initial query;
generating the initial query; and
looking up the initial query from a plurality of stored queries in distributed memory resources of the database system.
16 . The computer-readable memory of claim 11 , wherein the first memory section further stores operational instructions that, when executed by the set of processing core resources, causes the set of processing core resources to further determine the plurality of cardinality values by:
when the query indicates a filter to be applied to a table of the plurality of tables:
applying the filter to a number of rows of the table to produce filtered rows of the table; and
determine a cardinality value for the table based on the filtered rows.
17 . The computer-readable memory of claim 11 , wherein the first memory section further stores operational instructions that, when executed by the set of processing core resources, causes the set of processing core resources to further determine the initial cumulative cardinality value based on:
a cumulative of cardinality values of the plurality of tables of the initial organizational structure of execution.
18 . The computer-readable memory of claim 11 , wherein the first memory section further stores operational instructions that, when executed by the set of processing core resources, causes the set of processing core resources to further determine the initial cumulative cardinality value based on:
a cumulative of cardinality values of the plurality of tables of a layer of a plurality of layers of the initial organizational structure of execution.
19 . The computer-readable memory of claim 11 , wherein the first memory section further stores operational instructions that, when executed by the set of processing core resources, causes the set of processing core resources to:
create a plurality of alternative organizational structures of execution; and
select the most favorable alternative organizational structure of execution of the plurality of alternative organizational structures of execution based on the cardinality value of the plurality of tables.
20 . The computer-readable memory of claim 11 , wherein the first memory section further stores operational instructions that, when executed by the set of processing core resources, causes the set of processing core resources to:
create an alternative organizational structure of execution;
determine cardinality values of the plurality of tables of the alternative organizational structure of execution; and
when the cardinality values of the plurality of tables of the alternative organizational structure of execution compares favorably to the output cardinality threshold:
utilize the alternative organizational structure of execution of the plurality of join operations in the optimized query plan.