Join Order Selection and Reordering Algorithms in Database Query Optimization

Problem Description
In multi-table join queries in databases, the join order of tables directly impacts query performance. When a query involves multiple tables, the database optimizer needs to select the join order with the minimum cost from all possible permutations. For example, for a three-table join of A, B, and C, possible join orders include (A⋈B)⋈C, A⋈(B⋈C), (A⋈C)⋈B, and so on. The join order selection problem is NP-hard, as the number of possible join orders grows factorially with the increase in the number of tables. The optimizer must employ efficient search strategies (such as dynamic programming, greedy algorithms) and pruning techniques to find an approximately optimal solution within a reasonable time.

Detailed Explanation

1. Analysis of Problem Importance

   • Join order directly affects the size of intermediate result sets: an incorrect order may generate massive temporary tables, increasing I/O and CPU overhead.
   • Example: If table A has 1,000 rows and table B has 100,000 rows (where B's join key can filter 99% of the data), joining A⋈B first can quickly reduce the result set, whereas B⋈A might initially produce a large number of invalid matches.
   • The optimizer needs to make comprehensive judgments based on cardinality estimation and predicate selectivity.

2. Dynamic Programming Algorithm Implementation Steps

   • Step 1: Initialize single-table access paths
     Calculate the optimal access method (full table scan or index scan) for each table, recording the cost and output row count.

     Example: Table A (cost=10, result rows=100), Table B (cost=20, result rows=500)  
     

   • Step 2: Build candidate set for binary joins
     Enumerate all two-table join combinations, calculate the cost for each join method (e.g., nested loop join, hash join), and retain the optimal path for each subset:

     Subset {A,B}:  
       - Path 1: A⋈B (cost=10+20+join cost 15=45)  
       - Path 2: B⋈A (cost=20+10+join cost 12=42) → Retain the better one  
     

   • Step 3: Recursively generate multi-table join plans
     Based on the optimal solutions for smaller subsets, gradually increase the number of tables. For a k-table join, combine the "optimal solution of an m-table subset" with the "optimal solution of the remaining (k-m)-table subset":

     Three-table join {A,B,C}:  
       - Combination 1: Optimal solution for {A,B} ⋈ C  
       - Combination 2: Optimal solution for {A,C} ⋈ B  
       - Combination 3: Optimal solution for {B,C} ⋈ A  
     

   • Step 4: Pruning optimization
     If multiple paths (e.g., different join methods) appear for the same subset, retain only the path with the lowest cost to avoid combinatorial explosion.

3. Systematic Optimization Strategies

   • Heuristic rule assistance:
     • Prioritize joining tables with high selectivity (e.g., tables with WHERE conditions).
     • Avoid joins that expand intermediate results (e.g., large table ⋈ large table).
   • Genetic algorithm application:
     When the number of tables exceeds 10, dynamic programming may become infeasible. Genetic algorithms can be used to randomly evolve a population of join orders and iteratively search for a better solution.
   • Rule-based fallback strategy:
     If statistical information is missing, use left-deep trees to avoid intermediate materialization overhead, or join tables in the order they appear in the SQL statement.

4. Practical Case Analysis

   • Scenario: Querying an order table (1 million rows), a user table (10,000 rows), and a product table (100,000 rows) to generate user purchase statistics.
   • Optimizer decision process:
     1. First join the user table (WHERE user age > 30) and the order table to quickly filter invalid data.
     2. Join the result set with the product table, leveraging product category indexes to reduce scan range.
   • Cost comparison of incorrect order: If the order table and product table are joined first, it may produce a million-row intermediate result, leading to a performance degradation of over 10 times.

Summary
Join order selection is a core aspect of query optimization, requiring a combination of systematic search via dynamic programming and flexible application of heuristic rules. In practice, the optimizer must also consider the characteristics of join algorithms (e.g., memory requirements for hash joins) and data distribution in distributed environments to generate high-performance execution plans.