3.6. Creating the Plan Tree of Multiple-Table Query

In this section, the process of creating a plan tree for a multiple-table query is explained.

3.6.1. Preprocessing

The subquery_planner() function, defined in planner.c, invokes the preprocessing stage.

While the preprocessing for single-table queries was described in Section 3.3.1, this subsection focuses on the preprocessing specific to multiple-table queries.

Given the extensive number of tasks performed, only the primary operations are described here.

1. Processing and Converting CTEs:
   If WITH lists are present, the planner processes each common table expression (CTE) using the SS_process_ctes() function.

2. Pulling Up Subqueries:
   If a subquery in the FROM clause does not contain GROUP BY, HAVING, ORDER BY, LIMIT, or DISTINCT clauses, and does not use INTERSECT or EXCEPT, the planner converts it into a join form using the pull_up_subqueries() function.
   For example, a query containing a subquery in the FROM clause can be converted into a natural join:

   testdb=# SELECT * FROM tbl_a AS a, (SELECT * FROM tbl_b) as b WHERE a.id = b.id;

   $$ \Downarrow $$

   testdb=# SELECT * FROM tbl_a AS a, tbl_b as b WHERE a.id = b.id;

3. Transforming Outer Joins to Inner Joins:
   The planner transforms an outer join into an inner join whenever the join condition or WHERE clause constraints allow for a more efficient inner join execution without changing the result set.

3.6.2. Determining the Cheapest Path

To determine the optimal plan tree, the planner must consider all combinations of indexes and join methods. This is a very expensive process and becomes impossible if the number of tables increases due to a combinatorial explosion.

When the number of joining tables is relatively small (typically fewer than 12), the planner uses dynamic programming to determine the optimal plan.

Determining the optimal plan tree via dynamic programming involves the following processing levels (refer to Figure 3.34):

• Level 1:
  Determine the cheapest path for each individual table. Each table’s cheapest path is stored in its respective RelOptInfo structure.

• Level 2:
  In the following, the RelOptInfo of a set of tables is represented using curly braces, such as {A, B}.

  • If there are two tables, A and B, the planner identifies the cheapest join path for {A, B}. This result is the final answer for a two-table join.
  • If there are three tables, the planner identifies the cheapest path for each possible pair: {A, B}, {A, C}, and {B, C}.

• Level 3 and higher:
  Continue this process incrementally. The results of lower-level join combinations are used to determine the cheapest paths for larger sets (e.g., {A, B, C}) until a single set containing all tables is reached.

By reusing the cheapest paths of partial problems at each level, the planner can efficiently determine the optimal plan tree.

The following section describes how the planner identifies the cheapest plan for the following query:

testdb=# \d tbl_a
     Table "public.tbl_a"
 Column |  Type   | Modifiers
--------+---------+-----------
 id     | integer | not null
 data   | integer |
Indexes:
    "tbl_a_pkey" PRIMARY KEY, btree (id)

testdb=# \d tbl_b
     Table "public.tbl_b"
 Column |  Type   | Modifiers
--------+---------+-----------
 id     | integer |
 data   | integer |

testdb=# SELECT * FROM tbl_a AS a, tbl_b AS b WHERE a.id = b.id AND b.data < 400;

3.6.2.1. Processing in Level 1

In Level 1, the planner creates a RelOptInfo structure and estimates the cheapest costs for each relation in the query. These RelOptInfo structures are added to the simple_rel_array within the PlannerInfo structure of the query (refer to Figure 3.35).

The RelOptInfo for tbl_a contains three access paths, which are added to its pathlist. Each RelOptInfo is linked to its cheapest cost paths:

• the cheapest start-up cost path
• the cheapest total cost path
• the cheapest parameterized cost path (refer to Section 3.5.1.3 for details on parameterized paths)

In contrast, the RelOptInfo for tbl_b contains only a sequential scan access path because tbl_b has no associated index.

3.6.2.2. Processing in Level 2

In Level 2, a RelOptInfo structure for the join relation is created and added to the join_rel_list of the PlannerInfo (refer to Figure 3.36 [1]).

The planner then estimates the costs of all possible join paths and identifies the best access path — the one with the cheapest total cost. The RelOptInfo stores this result as its cheapest total cost path.

Table 3.3 shows all combinations of join access paths considered in this example. Since the query is an equi-join, the planner estimates costs for all three join methods (Nested Loop, Merge, and Hash Join). For clarity, the following notations are used:

• SeqScanPath(table): Sequential scan path of the table.
• Materialized->SeqScanPath(table): Materialized sequential scan path of the table.
• IndexScanPath(table, attribute): Index scan path using the specified attribute.
• ParameterizedIndexScanPath(table, attr1, attr2): Index path of the table using attr1, parameterized by attr2 of the outer table.

In the nested loop join category, for instance, seven join paths are estimated. The first path uses sequential scans for both tbl_a (outer) and tbl_b (inner). The second path uses a sequential scan for tbl_a and a materialized sequential scan for tbl_b, and so on.

The planner finally identifies the cheapest path among all estimated join paths and adds it to the pathlist of the RelOptInfo representing the set {tbl_a, tbl_b} (refer to Figure 3.36 [2]).

In this example, as shown in the EXPLAIN output below, the planner selects a hash join where tbl_b is the inner table and tbl_a is the outer table.

testdb=# EXPLAIN  SELECT * FROM tbl_b AS b, tbl_c AS c WHERE c.id = b.id AND b.data < 400;
                              QUERY PLAN
----------------------------------------------------------------------
 Hash Join  (cost=90.50..277.00 rows=400 width=16)
   Hash Cond: (c.id = b.id)
   ->  Seq Scan on tbl_c c  (cost=0.00..145.00 rows=10000 width=8)
   ->  Hash  (cost=85.50..85.50 rows=400 width=8)
         ->  Seq Scan on tbl_b b  (cost=0.00..85.50 rows=400 width=8)
               Filter: (data < 400)
(6 rows)

3.6.3. Determining the Cheapest Path of a Triple-Table Query

The process for determining the cheapest path of a query involving three tables is as follows:

testdb=# \d tbl_a
     Table "public.tbl_a"
 Column |  Type   | Modifiers
--------+---------+-----------
 id     | integer |
 data   | integer |

testdb=# \d tbl_b
     Table "public.tbl_b"
 Column |  Type   | Modifiers
--------+---------+-----------
 id     | integer |
 data   | integer |

testdb=# \d tbl_c
     Table "public.tbl_c"
 Column |  Type   | Modifiers
--------+---------+-----------
 id     | integer | not null
 data   | integer |
Indexes:
    "tbl_c_pkey" PRIMARY KEY, btree (id)

testdb=# SELECT * FROM tbl_a AS a, tbl_b AS b, tbl_c AS c
testdb-#                WHERE a.id = b.id AND b.id = c.id AND a.data < 40;

• Level 1: The planner estimates the cheapest paths for all individual tables and stores this information in the corresponding RelOptInfo objects: {tbl_a}, {tbl_b}, and {tbl_c}.
• Level 2: The planner identifies all possible pairs of the three tables and estimates the cheapest path for each combination. The results are stored in the corresponding RelOptInfo objects: {tbl_a, tbl_b}, {tbl_b, tbl_c}, and {tbl_a, tbl_c}.
• Level 3: The planner finally identifies the cheapest path for the entire query using the previously obtained RelOptInfo objects.

A more detailed description of the Level 3 processing follows (refer to Figure 3.34):

The planner considers three combinations of RelOptInfo objects: {tbl_a, {tbl_b, tbl_c}}, {tbl_b, {tbl_a, tbl_c}}, and {tbl_c, {tbl_a, tbl_b}}. This is expressed as:

The planner then estimates the costs of all possible join paths within these combinations.

For the RelOptInfo object {tbl_c, {tbl_a, tbl_b}}, the planner estimates all combinations of tbl_c and the cheapest path of {tbl_a, tbl_b}. In this example, the cheapest path for {tbl_a, tbl_b} is a hash join where tbl_a and tbl_b are the outer and inner tables, respectively.

As with Level 2, the estimated join paths include nested loop joins, merge joins, hash joins, and their variations. The planner processes the combinations {tbl_a, {tbl_b, tbl_c}} and {tbl_b, {tbl_a, tbl_c}} in the same manner, finally selecting the cheapest overall access path.

The EXPLAIN output for this query is shown below:

The outermost join is an indexed nested loop join (Line 5). The inner relation is a parameterized index scan (Line 13), while the outer relation is the result of the hash join between tbl_b and tbl_a (Lines 7–12).

Consequently, the executor first performs the hash join of tbl_a and tbl_b and then performs the indexed nested loop join with tbl_c.