跪拜 Guibai
← Back to the summary

How a Database Optimizer Proves It Can Rewrite Your LEFT JOIN into an Inner Join

Why does the optimizer dare to "silently change" the LEFT JOIN you wrote? — Deconstructing the design philosophy of the Kingbase KES optimizer

I stared at one line in the EXPLAIN output for a long time:

Hash Join  (cost=...)

I wrote LEFT JOIN, but what appeared in the execution plan was Hash Join — without Left. The outer join had been eliminated.

I've encountered this more than once. At first, I thought it was a KES-specific behavior, but later I discovered that Oracle, MySQL, and PostgreSQL all do it. It's a common optimization action across all SQL-standard-compliant databases, called Outer Join Elimination.

But "doing it" and "daring to do it" are two different things. The confidence to do it comes from relational algebra — the optimizer can mathematically prove that the result sets of the two writing styles are completely identical, which gives it the right to rewrite your SQL. This article doesn't discuss application-level pitfalls (I wrote a separate piece on that); here, the lens is focused specifically on the optimizer's internals: how this elimination action is determined and executed, and what noteworthy design choices Kingbase KES has made in this area.

image.png

@[toc]

1. Starting from Relational Algebra: The Theoretical Foundation of Outer Join Elimination

To understand the optimizer's behavior, you must first accept a premise — SQL is a declarative language, and the optimizer has the right to freely rewrite it under the guarantee of equivalence. And the legitimacy of "equivalent rewriting" comes from relational algebra. Let's first look at this matter in the purest algebraic language.

1.1 Algebraic Expressions of Outer and Inner Joins

Expressed in symbolic language, for two relations R and S under a join condition θ:

Then, a left outer join with a WHERE filter:

σ_p ( R ⟕θ S )

means "perform the outer join first, then apply the p filter to the result."

The Outer Join Elimination Theorem can be described in one sentence: When p is a "null-rejecting predicate" and p only acts on S-side columns, the above expression is equivalent to an inner join. Written symbolically:

σ_p ( R ⟕θ S )  ≡  σ_p ( R ⋈θ S )

This "≡" sign has a rigorous mathematical proof; it is not a heuristic rule. It is a theorem-level conclusion of relational algebra. Once the optimizer recognizes this pattern, it can rewrite the left side to the right side without any hesitation. And the execution cost of the right side is usually much lower than the left side — because an inner join does not need to "pad NULLs for unmatched R rows," and thus does not need to execute the heavier pipeline of a "null-augmented tuple stream."

1.2 Key Concept: What is a "Null-Rejecting Predicate"?

The "null-rejecting predicate" mentioned above is the core of understanding outer join elimination. The definition is:

A predicate p is called a null-rejecting predicate if it returns False or Unknown (i.e., does not return True) for any input row containing a NULL value.

In other words, any filter condition that "NULL cannot pass through" is a null-rejecting predicate. Common null-rejecting predicates include:

Conversely, predicates that "NULL can pass through" are not null-rejecting, for example:

Determining whether a predicate is null-rejecting is a statically provable process. KES's optimizer internally has a "predicate strictness inference" mechanism that traverses the expression tree, deriving each sub-expression's attitude toward NULL from the leaf nodes upward, ultimately determining whether the overall predicate is null-rejecting.

1.3 Two Prerequisites of the Theorem

It is worth emphasizing that the equivalence of outer join elimination has two prerequisites that cannot be ignored:

Industrial-grade optimizers (including Kingbase KES) strictly adhere to these two prerequisites. If either one is not met, the elimination action will never trigger. This is also why "IS NULL scenarios are not eliminated" — because they violate Condition B.

2. The Optimizer's Processing Flow: From SQL to Elimination Decision

The theory has been covered, so let's now look at how the actual optimizer code handles this. In Kingbase KES, from the moment a SQL statement enters until it finally decides to eliminate an outer join, it roughly goes through five stages. Here, I'll use simplified pseudocode combined with a decision flowchart to walk you through it.

2.1 Stage 1: SQL Parsing and Initial Query Tree Construction

What the optimizer actually holds in its hands is not the raw SQL string you wrote. It receives the query tree produced by the parser. For example, if you write this:

SELECT * FROM t1 LEFT JOIN t2 ON t1.id = t2.id WHERE t2.status = 'A';

Then the structure produced by the parser looks roughly like this:

Query
 ├── jointree: LeftJoin(t1, t2, ON = "t1.id = t2.id")
 ├── qual   : "t2.status = 'A'"
 └── target : *

At this stage, the optimizer itself hasn't done anything. It just holds a structural tree, which merely presents the original form of how you wrote the SQL.

2.2 Stage 2: Query Normalization

Before the optimizer performs equivalence transformations, it has one thing to do first: perform a round of normalization on the query tree. What does this round of operations include? For example, constant folding, expression simplification, flattening CASE expressions, and conversions like IS TRUE / IS FALSE.

Why is this step necessary? Simply because everyone has different SQL writing habits. The purpose of this step is to standardize various messy writing styles into a few fixed forms. This makes pattern matching much easier later on.

Let's look at an example. Normalization will take this:

WHERE (t2.status = 'A') = TRUE

and directly simplify it to this:

WHERE t2.status = 'A'

And also this:

WHERE t2.amount IN (SELECT amount FROM ...)  -- but the subquery is single-valued and deterministic

will be converted to an EXISTS / semi-join form.

After this series of operations, the result is a query tree that looks simpler, with shorter expressions. All subsequent rewrite rules, including outer join elimination, run based on this cleaned-up tree.

2.3 Stage 3: Pattern Matching for Outer Join Elimination

Next comes the most critical step. The optimizer traverses this query tree and performs the following judgment on each outer join node:

# Optimizer Pseudocode: Outer Join Elimination Decision
def try_eliminate_outer_join(join_node, top_qual):
    if join_node.type not in ('LeftJoin', 'RightJoin', 'FullJoin'):
        return join_node

    nullable_side = get_nullable_side(join_node)

    for pred in split_and_predicates(top_qual):
        # Condition A: Does the predicate only reference Nullable-Side columns?
        if not refers_only(pred, nullable_side):
            continue

        # Condition B: Is the predicate null-rejecting?
        if is_null_rejecting(pred):
            # Both conditions met, rewrite!
            join_node.type = 'InnerJoin'
            return join_node

    return join_node

There are two situations here worth noting:

2.4 Stage 4: Predicate Pushdown and Execution Plan Generation

Immediately after the outer join elimination action is completed, the next step is predicate pushdown.

What is the situation after elimination? The filter conditions that originally resided in the WHERE clause can now be freely pushed down, directly to the scan nodes:

-- Before elimination
LeftJoin(t1, t2) ON t1.id = t2.id
 └── Filter: t2.status = 'A'

-- After elimination + pushdown
InnerJoin(t1, t2) ON t1.id = t2.id
 ├── SeqScan(t1)
 └── SeqScan(t2) Filter: t2.status = 'A'   -- Filter pushed down to scan layer

After this step, the performance improvement actually comes in two parts: first, the join algorithm no longer needs to run in the complex manner of an outer join; it falls back to the simpler inner join. Second, the filter condition is moved to the scan layer, so data that doesn't meet the condition can be directly eliminated during scanning. As a result, the amount of data participating in the join is significantly reduced.

Typically, when dealing with large tables, the combination of these two actions can often reduce query time significantly, sometimes by more than tenfold.

2.5 Stage 5: Physical Operator Selection

Moving further down, we reach the physical layer. At this point, the optimizer calculates costs, i.e., looks at the Cost Model. Based on the calculated cost, it selects the specific JOIN algorithm — choosing Hash Join, Nested Loop, or Sort-Merge Join.

Since the outer join has already been eliminated earlier, there's no need to worry about the NULL-padded data stream anymore. These algorithms just run according to the most ordinary, standard logic.

At this point, the entire process of a SQL statement from entry to final execution plan determination is complete. Outer join elimination is actually just a small link in this pipeline. However, its role is quite significant. It represents the practical implementation of relational algebra theory in an enterprise-level database.

3. Design Trade-offs of the Kingbase KES Optimizer

Having covered the theory and process, let's look at the specific design trade-offs Kingbase KES has made in this area. This is the core part of this article. I've summarized four design principles that I felt most deeply during source code reading and practical testing.

3.1 Strictness First: Never "Cover" for Incorrect SQL

Some databases, when designing, pursue so-called "user-friendliness" — for example, automatically "guessing the closest legal syntax" to execute illegal syntax. Kingbase KES's choice is to strictly adhere to SQL standard semantics: outer join elimination only triggers in scenarios that are equivalent in the relational algebra sense, never making speculative inferences beyond the standard.

For example:

SELECT * FROM t1 LEFT JOIN t2 ON t1.id = t2.id
WHERE  t2.status = 'A' OR t1.id > 100;

In this SQL, the WHERE clause is connected by OR, and the right side t1.id > 100 is not a null-rejecting predicate. KES's optimizer will strictly determine: the outer join cannot be eliminated. Because there is a possibility that t1.id > 100 returns True for some null-augmented rows, and these rows need to be preserved.

Some other database optimizers might use "heuristic reasoning" in such scenarios, potentially leading to erroneous elimination. KES's choice is "better conservative than overstepping" — this is a very important quality in domestic replacement scenarios, as it ensures that migrated SQL does not experience semantic drift due to an overly aggressive optimizer.

3.2 Judgment Completeness: Cascading Elimination of Multi-Layer JOINs

Some optimizers only handle simple scenarios of "a single top-level outer join." When encountering nested outer joins or multi-layer outer joins exposed after View Inline, they are powerless. KES's optimizer is quite solid in this regard.

Consider a slightly more complex example:

SELECT * FROM t1
LEFT JOIN t2 ON t1.id = t2.id
LEFT JOIN t3 ON t2.id = t3.id
WHERE  t3.status = 'A';

KES optimizer's judgment process is:

One judgment eliminates two layers of outer joins. This cascading capability is very common in actual business, especially for multi-layer JOINs exposed through view nesting. KES's optimizer can recognize and reasonably simplify them, which directly determines the performance after domestic migration.

3.3 View Transparency: Secondary Elimination After View Inline

In modern business code, views are an almost inevitable abstraction layer. A typical scenario is:

CREATE VIEW v_user_order AS
SELECT u.user_id, u.user_name, o.order_id, o.order_amount
FROM   t_user u LEFT JOIN t_order o ON u.user_id = o.user_id;

-- Business-side call
SELECT * FROM v_user_order WHERE order_amount > 500;

KES optimizer's processing path here is: first perform View Inline, "expanding" the view definition into the outer query, and then run another round of outer join elimination judgment. The expanded equivalent SQL becomes:

SELECT u.user_id, u.user_name, o.order_id, o.order_amount
FROM   t_user u LEFT JOIN t_order o ON u.user_id = o.user_id
WHERE  o.order_amount > 500;

This returns to the standard outer join elimination scenario — the outer join is eliminated, and the Filter is pushed down. KES's optimizer tightly connects the View Inline and rewrite stages, ensuring that the execution plan obtained by users encapsulating logic into views is completely identical to that of directly hand-written SQL. This is very valuable from a "performance predictability" perspective — the business side will not encounter inexplicable performance differences because of "using views vs. not using views."

3.4 Compatibility with Oracle (+) Syntax: Product Refinement in Details

Legacy business code migrated from Oracle extensively uses Oracle's unique (+) outer join syntax:

SELECT * FROM t1, t2 WHERE t1.id = t2.id(+) AND t2.status(+) = 'A';

KES fully supports this syntax and has achieved semantic equivalence alignment in the judgment of outer join elimination:

This detail is very important in domestic replacement scenarios. In a project I participated in that migrated from Oracle to KES, about 60% of the legacy SQL used the (+) syntax. The KES optimizer's ability to faithfully translate this syntax directly determines whether this code can run with "zero modification."

4. A Complete Example You Can Run Locally

So much theory has been discussed earlier. Let's finally use a complete example that can be run locally to illustrate. This example is one I often use when training my team on the KES optimizer. Running through this example basically allows you to see all the key points mentioned earlier.

4.1 Set Up the Environment First

-- Create test tables
CREATE TABLE t_user (
    user_id     INT PRIMARY KEY,
    user_name   VARCHAR(50)
);

CREATE TABLE t_order (
    order_id     INT PRIMARY KEY,
    user_id      INT,
    order_amount NUMERIC(10, 2),
    order_status VARCHAR(20)
);

-- Generate data: 100,000 users, only 30,000 have orders
INSERT INTO t_user
SELECT g, 'user_' || g FROM generate_series(1, 100000) g;

INSERT INTO t_order
SELECT g,
       (g % 100000) + 1,
       (random() * 1000)::NUMERIC(10, 2),
       (ARRAY['FINISHED','PENDING','CANCELED'])[floor(random()*3)+1]
FROM   generate_series(1, 300000) g;

CREATE INDEX idx_order_user ON t_order(user_id);
CREATE INDEX idx_order_status ON t_order(order_status);

ANALYZE;

4.2 Scenario A: The Join Will Be Eliminated

EXPLAIN ANALYZE
SELECT u.user_id, u.user_name, o.order_id, o.order_amount
FROM   t_user u LEFT JOIN t_order o ON u.user_id = o.user_id
WHERE  o.order_status = 'FINISHED';

What to look for: Look at the topmost node of the execution plan. It should display Hash Join here. Note that the word Left is not in parentheses. Then, the scan of t_order will have a Filter: (order_status = 'FINISHED'). The number of rows in the result set is much smaller than 100,000. Why is this? Because orders with FINISHED status are only a portion. This indicates that the outer join has indeed been eliminated.

4.3 Scenario B: The Join Is Preserved (IS NULL)

EXPLAIN ANALYZE
SELECT u.user_id, u.user_name
FROM   t_user u LEFT JOIN t_order o ON u.user_id = o.user_id
WHERE  o.order_id IS NULL;

What to look for: This time, look at the topmost node. It becomes Hash Left Join. It carries Left now. What's going on? Because KES's optimizer found that IS NULL is not a null-rejecting predicate. So it preserves the semantics of the outer join. Look at the result set produced; it's the users without orders. The row count is around 70,000. This indicates that the outer join was not eliminated and was preserved.

4.4 Scenario C: Condition Written in ON (If Business Logic Intends This)

EXPLAIN ANALYZE
SELECT u.user_id, u.user_name, o.order_id, o.order_amount
FROM   t_user u
LEFT   JOIN t_order o
       ON  u.user_id = o.user_id
       AND o.order_status = 'FINISHED';

What to look for: The top layer of the execution plan is still Hash Left Join. All 100,000 users are present at this time. For users with FINISHED orders, the order information will be displayed. What about users without? The order fields will be NULL. Generally speaking, if the business requirement is "show each user their completed orders," the SQL should be written this way.

4.5 Scenario D: Cascading Elimination of Two Layers

-- Add an additional table
CREATE TABLE t_review (
    review_id INT PRIMARY KEY,
    order_id  INT,
    review    VARCHAR(500)
);
INSERT INTO t_review
SELECT g, g, 'review_' || g FROM generate_series(1, 100000) g;

EXPLAIN ANALYZE
SELECT *
FROM   t_user u
LEFT   JOIN t_order o  ON u.user_id = o.user_id
LEFT   JOIN t_review r ON o.order_id = r.order_id
WHERE  r.review LIKE 'review_1%';

What to look for: Carefully examine the execution plan. Both layers of outer joins are eliminated. In the final execution plan, both JOIN nodes are Hash Join. In this case, they are eliminated together.

This test environment can be run on any KES instance. Combine it with the output from EXPLAIN ANALYZE. How the optimizer makes its judgment is very clearly visible. During my internal training, I usually have everyone type it out themselves. Once you've seen this execution plan with your own eyes, when writing SQL in the future, you'll often subconsciously avoid falling into the pitfalls of outer join elimination.

5. A Deeper Look at the Optimizer: Is It Trustworthy?

So many technical details have been discussed earlier. Now, let's stop staring at the code and talk a bit about the design philosophy behind the Kingbase KES optimizer.

Everyone is currently undertaking domestic replacements. In database development, optimizer design often faces just one question: Do you want to run fast, or do you want semantic safety?

Some optimizers are more aggressive. Their benchmark scores look great, and their benchmark data is beautiful. However, they might rewrite your SQL into a mess. The final result might be completely different from what you expected. This kind is harder to control. The other kind is more stable. It runs exactly as you wrote it, with strong predictability. The cost is that, in certain specific situations, it won't reach the absolute fastest speed.

Kingbase KES's stance on this matter is actually very clear. It prioritizes ensuring strict semantics and predictable results first. Then it considers performance. Looking back at the details of outer join elimination discussed earlier, you can see:

This approach, which seems rigid but is actually very thoughtfully designed, has a very practical benefit during domestic replacements: it reduces migration risk. Think about it: if performance suddenly improves after migration, but business data occasionally shows strange problems, who can tolerate that? Engineering teams actually prefer a situation where performance after migration is consistent with before, and business operations continue as usual. Over the past six months, running several KES projects, I've noticed one thing: the greatest benefit of this database's optimizer is not how fast it can run, but that you find it trustworthy.

6. Summary

Outer join elimination seems simple at first glance. But truly implementing it deeply in code is actually very troublesome. From the theorems of relational algebra, to how the optimizer judges it internally, to how Kingbase KES specifically writes this logic — every step requires attention to detail.

So, returning to the question raised at the beginning of this article: How exactly is outer join elimination recognized? How is it judged? And how is it ultimately executed? Let me summarize:

  1. Where does the theory come from: It's essentially a theorem in relational algebra. The prerequisites are having a "null-rejecting predicate" and a "Nullable-Side reference." Only when these two conditions are met can the equivalence transformation be performed.
  2. How is it specifically judged: After the optimizer receives the SQL, it first parses, then performs query normalization, then matches patterns, then does predicate pushdown, and finally selects physical operators. It goes through these five stages to turn the theorem just mentioned into the execution plan you see.
  3. What choices did Kingbase KES make: In this area, it emphasizes strictness, completeness, transparency, and compatibility. That means the judgment of null-rejecting predicates must be strict. Multi-layer nesting and view scenarios must all be covered. Results inside and outside views must be consistent. And Oracle's (+) syntax must be compatible.

All these fragmented details added together actually piece together the most fundamental part of a database. When we make technical selections, just remember one thing: as long as an optimizer achieves "strict, complete, and predictable," its compatibility with your existing legacy code will definitely be high. The effort you spend on migration and modification will also be smaller. This is also one reason why I will spend a lot of time researching Kingbase KES going forward.

The optimizer is simply too vast a topic. One article can never cover it all. In the future, I will continue writing, breaking down principles like predicate pushdown, subquery unnesting, Join Reorder, and the cost model. I hope to provide some practical help to colleagues currently working on domestic replacements, or to friends interested in database kernels.