Analysis of Join Order Selection Principles in Database Query Optimization

Problem Description
In database query optimization, when an SQL statement involves joins across multiple tables, the query optimizer needs to decide the join order of these tables. Different join orders produce equivalent query results, but their execution efficiency can differ by several orders of magnitude. Join order selection is one of the most core and complex tasks of a query optimizer. It requires comprehensive consideration of various factors such as table size, join conditions, and index availability to select the lowest-cost plan from all possible join orders.

Solution Process

1. Importance and Complexity of the Problem

• Why is it important? For a query joining N tables, there are theoretically N! (N factorial) possible join orders. For example, 5 tables have 120 orders, and 10 tables have 3,628,800 orders. The optimizer cannot exhaustively enumerate all orders and must use efficient algorithms to find a near-optimal solution within a reasonable timeframe.
• Core Challenge: The choice of join order directly affects the size of intermediate result sets, which in turn determines the cost of subsequent join operations. The goal is to minimize the total execution cost of the entire query.

2. How the Optimizer Estimates Join Cost?
Before selecting an order, the optimizer needs the ability to estimate the cost of any given order. This relies on:

• Cardinality Estimation: Estimating the number of rows returned from each table after applying filter conditions, and the number of rows produced by joining two tables. This depends on table statistics (e.g., total row count, column data distribution histograms). Inaccurate cardinality estimation is the primary reason for the optimizer choosing a suboptimal join order.
• Cost Model: Assigning a cost value to each operation (e.g., full table scan, index scan, join operation). Cost is typically related to I/O (disk read/write) and CPU consumption. For instance, reading a data page from disk is much more expensive than a comparison operation in memory.

3. Core Algorithms for Join Order Selection
Optimizers typically employ search algorithms based on dynamic programming to efficiently explore the vast search space.

• Step 1: Build Initial Subsets

  • The optimizer first treats each single table in the query as a "subplan." It calculates the optimal access path for each single table (e.g., full table scan vs. a specific index scan) and records the cost and result set size (cardinality) for that path.
  • For example, for the query SELECT ... FROM A, B, C WHERE ..., the optimizer initially obtains the optimal plans for the three subsets {A}, {B}, and {C}.

• Step 2: Iteratively Build Larger Subsets (Core of Dynamic Programming)

  • The algorithm starts with subsets of size 1 (single tables) and progressively builds subsets of size 2, 3, ... up to size N (all tables).
  • For each subset S of size k:
    1. Enumerate Candidate Joins: Consider all possible ways to partition subset S into two smaller, disjoint subsets (e.g., S1 and S2), where a join condition must exist between S1 and S2 (otherwise, a Cartesian product would result, which is typically very costly and generally avoided).
    2. Evaluate Join Cost: For each partition (S1, S2), the optimizer has already calculated the optimal subplans and costs for S1 and S2 in previous steps. Now, it needs to calculate the cost of joining S1 and S2. Total Cost = Cost(S1) + Cost(S2) + Cost(Join(S1, S2)).
    3. Compare and Retain the Optimal Solution: Perform the above calculation for all possible partition methods. Then, select the partition method (and its corresponding join order—whether it's S1 JOIN S2 or S2 JOIN S1? This depends on the join algorithm, e.g., Nested Loop Join typically requires the smaller table as the driving table) with the lowest total cost as the optimal execution plan for subset S.
    4. Record: Store the optimal plan and its cost for subset S for use when constructing larger subsets.

• Step 3: Illustrative Example (Using a three-table join A, B, C)

  • Subsets of size 1: Find the best access paths for {A}, {B}, {C} individually.
  • Subsets of size 2: Consider all subsets containing 2 tables.
    • Subset {A, B}: Possible partition is (A, B). Calculate Cost(A) + Cost(B) + Cost(JOIN(A,B)).
    • Subset {A, C}: Similarly.
    • Subset {B, C}: Similarly.
    • For each subset, retain the join order and plan with the lowest cost.
  • Subsets of size 3 (Final Result): Consider subset {A, B, C}. Possible partitions are:
    • (A, B) join C: Cost = Cost(optimal plan for {A,B}) + Cost(C) + Cost(JOIN(result, C))
    • (A, C) join B: Cost = Cost(optimal plan for {A,C}) + Cost(B) + Cost(JOIN(result, B))
    • (B, C) join A: Cost = Cost(optimal plan for {B,C}) + Cost(A) + Cost(JOIN(result, A))
    • Compare the costs of these three options and select the lowest as the optimal execution plan for the entire query.

4. Optimization Strategies for Handling More Tables
When there are a very large number of tables (e.g., over 10-15), the computational load of dynamic programming also becomes prohibitive. In such cases, the optimizer employs heuristic algorithms to reduce the search space:

• Greedy Algorithm: At each step, select only the join that appears best at the moment. For example, always join the two tables that produce the smallest intermediate result set first.
• Random Search Algorithms (e.g., Genetic Algorithms): Used to find a good, though not necessarily optimal, solution within a very large search space.
• Rule-Based Heuristics:
  • Prioritize joining tables with indexes.
  • Prioritize joining tables with small filtered result sets (using smaller tables as driving tables).
  • Avoid or postpone joins that produce huge intermediate result sets (e.g., Cartesian products).

Summary
Join order selection is a classic dynamic programming problem that trades space for time. The optimizer systematically constructs and evaluates all promising subplans in a bottom-up, small-to-large manner, avoiding exhaustive search, and ultimately finds the lowest-cost join order. Understanding this principle helps DBAs and developers assist the optimizer in making better decisions by analyzing execution plans, maintaining accurate statistics, and creating appropriate indexes.