Principle Analysis of Adaptive Join in Database Query Optimization

Today, we will discuss an important runtime optimization technique in database query optimization—Adaptive Join. In traditional query optimization, the optimizer selects an optimal join algorithm (such as Hash Join, Nested Loop Join, etc.) during the query compilation phase based on statistical information. However, statistical information may be biased or data distribution may be uneven, leading to suboptimal performance of the pre-selected join algorithm during execution. Adaptive Join is a dynamic optimization technology proposed to address this issue.

1. The Core Problem Addressed by Adaptive Join

Traditional join algorithm selection faces a fundamental dilemma: during the query compilation phase, the optimizer must make a "one-time," irreversible decision based on incomplete and potentially outdated statistical information. This leads to two main risks:

• Cardinality Estimation Errors: Inaccurate predictions of intermediate result set sizes can lead to the selection of unsuitable algorithms. For example, if the optimizer estimates that the join of two tables will produce few results and chooses Nested Loop Join, which is suitable for small datasets, but the actual join generates millions of rows, it can result in a performance disaster.
• Data Distribution Skew: Statistical information (such as histograms) may fail to capture local data characteristics. For instance, a highly concentrated join key value may cause severe hash table collisions, drastically degrading Hash Join performance.

The core idea of Adaptive Join is: Postpone some decisions until the query is actually executed, and dynamically select or switch to the optimal join strategy based on real-time data characteristics collected during runtime.

2. Basic Working Principle of Adaptive Join

Adaptive Join is not an entirely new join algorithm but a decision framework. Its typical workflow is as follows:

Step 1: Compilation Phase—Constructing Backup Plans
During query compilation, the query optimizer no longer generates a single fixed join plan. Instead, it creates an "adaptive decision point" for certain join operations (particularly critical joins with uncertain cardinality) and prepares multiple candidate execution strategies (e.g., a Hash Join plan and a Nested Loop Join plan). The optimizer estimates a "switch threshold," such as: if the number of rows in the build input is less than X, Nested Loop Join is more optimal; otherwise, Hash Join is better.

Step 2: Initial Execution Phase—Probing and Sampling
When query execution reaches this adaptive decision point, it does not immediately begin the full join operation. Instead, it first executes the build input of the join (e.g., the input used to build the hash table in Hash Join or the outer table input in Nested Loop Join).

• Key Action: During the execution of the build input, the system dynamically collects accurate runtime information, primarily the actual number of rows processed. In some cases, it may also sample data to analyze the distribution of join keys (e.g., number of unique values, presence of skew).
• Execution Method: This process is typically performed in a "blocking" manner, meaning the entire build input data (or a sufficiently representative sample) must be fully read before a decision can be made. This introduces some initial overhead but avoids larger performance penalties later.

Step 3: Runtime Decision—Algorithm Switching
Based on the precise cardinality (row count) collected in Step 2, the system compares it with the pre-calculated "switch threshold."

• If the actual row count <= threshold: The input is small enough, making Nested Loop Join (or in-memory hash join in Grace Hash Join) suitable. The system selects and executes the corresponding plan branch better suited for small datasets.
• If the actual row count > threshold: The input is large, making Hash Join (or a hybrid hash join that may spill to disk) more suitable. The system switches to the other plan branch.

Step 4: Final Execution
After the decision is made, the system discards the unselected plan branch and proceeds to execute the chosen join algorithm to complete the join operation. For Hash Join, if Grace Hash Join is selected, the number of partitions and whether to spill to disk can be dynamically determined based on the actual data volume.

3. Main Implementation Strategies of Adaptive Join

In industrial-grade database systems, Adaptive Join primarily manifests in two forms:

Strategy A: Adaptive Join Selection
This is the most typical mode, as described above, dynamically selecting between Hash Join and Nested Loop Join. Microsoft SQL Server's "Adaptive Join" feature is a well-known example, allowing the execution engine to choose between Hash Join and Nested Loop Join after scanning the build input.

Strategy B: Adaptive Join Type Switching
In some complex join scenarios, the optimization goal may involve switching between different types of joins. A more advanced application is the adaptive selection between Broadcast Join and Shuffle Join, which is particularly important in big data systems like Spark.

• Problem: In distributed environments, joining a small table with a large table is highly efficient when the small table is broadcast to all nodes (Broadcast Join). However, if the small table is not actually "small," broadcasting it can incur significant network overhead.
• Adaptive Solution: Precisely calculate the size of the small table at runtime. If it is smaller than the broadcast threshold, use Broadcast Join; otherwise, switch to Shuffle Join, which involves repartitioning both tables by the join key before performing local joins.

4. Technical Advantages and Trade-offs

Advantages:

• Robustness: Significantly reduces the risk of performance degradation due to inaccurate statistical information, improving query performance stability.
• Adaptability: Automatically adapts to changes in data distribution without manual intervention or updating statistical information.
• Simplified Tuning: Reduces the burden on DBAs to manually tune complex queries using hints.

Costs and Challenges:

1. Compilation Overhead: The optimizer needs to generate multiple plan branches and compare their costs, increasing compilation time.
2. Runtime Overhead: Probing, sampling, and switching at decision points consume CPU and memory resources and may introduce temporary blocking.
3. Memory Management Complexity: Memory may need to be reserved or temporarily allocated during the decision-making process, increasing the complexity of memory management.
4. Decision Point Selection: Not all joins are suitable for adaptive decision-making. The optimizer must intelligently identify critical join points with high cardinality uncertainty and significant performance impact to avoid unnecessary decision overhead.

5. Summary

Adaptive Join represents a significant step in the evolution of query optimization from "static optimization" to "dynamic optimization." By postponing critical decisions from compile time to runtime and making choices based on real data characteristics, it effectively addresses the Achilles' heel of traditional optimizers—inaccurate statistical information. Although it introduces some runtime overhead, the benefits in improving the stability of complex query performance are often decisive. Understanding Adaptive Join helps us better appreciate how modern database systems are becoming more intelligent and robust.