Semi Join

Hook: Interviewers love semi join because it tests whether you know the difference between “find matching rows” and “bring back matching columns”.

Question: What is a semi join in SQL?

Answer: A semi join returns rows from the left table only when a matching row exists in the right table. It does not return columns from the right table, and it does not multiply left rows just because there are many matches on the right. In real SQL, you usually express it with EXISTS or sometimes IN, not with a literal SEMI JOIN keyword.

Interview-Ready Answer: I think of a semi join as an existence filter. I keep the left rows that have at least one match on the right, but I never bring back right-side columns. So if a customer has three orders, a semi join still returns that customer once. In SQL, I usually write it with EXISTS, and that is also a nice performance clue because many optimizers can turn it into a real semi-join plan.

What a Semi Join Really Means

Detailed Explanation: A semi join answers one question: Does at least one matching row exist? That is different from a normal join, which asks: What combined rows should I output? In a semi join, the right side is only used as a test. Think of it like a guest list at a venue: you check whether a person is on the list, but you do not print the whole guest list on their wristband.

How It Works Under the Hood

1. The database reads a row from the left table.
2. It checks the right table for a matching key or condition.
3. If at least one match exists, the left row is emitted once.
4. If no match exists, the left row is skipped.
5. The engine may stop early after the first match, which is a big reason semi joins can be efficient.

That early stop matters. With an inner join, the engine may need to produce every matching pair first, then you may need DISTINCT to clean up duplicates. A semi join avoids that extra work.

How SQL Usually Expresses It

Most SQL dialects do not require a literal SEMI JOIN keyword in user queries. Instead, you write:

• WHERE EXISTS (SELECT 1 FROM right_table ...)
• Sometimes WHERE left_key IN (SELECT right_key FROM ...)

Many optimizers rewrite these patterns into a semi join execution plan. In some engines, the plan output may even literally say Left Semi Join.

Semi Join vs Inner Join vs Join + DISTINCT

The key mental model: an inner join is a pair generator; a semi join is a yes/no filter.

Performance Notes and Complexity

• Nested-loop semi join: worst case is roughly O(L * R), but it can be fast when the right side has an index and the engine can stop on the first match.
• Hash semi join: often around O(L + R) time, with O(R) memory for the hash structure.
• Why it can beat join + distinct: join + distinct may generate millions of intermediate pairs, then sort or hash them again to remove duplicates.

Realistic numbers: if you have 1 million customers and 10 million orders, a hash semi join may build a hash set of order customer IDs once, then scan customers and emit only matching customers. That is often much cheaper than producing every customer-order pair. If the right side is tiny, an indexed nested-loop semi join may be even better.

Important Edge Cases

• Duplicates on the right: they do not create duplicate output rows in a semi join.
• Duplicates on the left: if the left table itself has duplicate rows, those duplicate left rows can still appear, because the semi join preserves left-row instances.
• NULL handling: EXISTS is usually safer than IN when the subquery can contain NULL values, because IN uses three-valued logic and can surprise you.
• SQL syntax: some databases expose semi join mainly in the optimizer plan, not as a direct query keyword.

Memory hook: Semi join is the bouncer, not the photographer. It checks the guest list and lets people in, but it does not hand you the whole list or duplicate the crowd.

Real-World Story

Real-World Example: Imagine a checkout service for a subscription app. Every night, it needs a list of users who have at least one paid invoice so it can renew premium access. The business question is not “show me every invoice next to every user”; it is “which users qualify?” That is exactly semi join territory.

Suppose finance has 5 invoices for one customer because of retries, refunds, and partial payments. If a developer uses a plain inner join and then forgets to dedupe, that customer may appear 5 times. Downstream code might send 5 renewal emails, create 5 entitlement records, or overcount active subscribers in a dashboard.

What goes wrong: the job log starts showing duplicate customer IDs, the metrics spike above the true active-user count, and support tickets appear saying “I got the same renewal email three times.” The fix is usually to switch from join logic to an existence check with EXISTS, which preserves one left row per qualifying entity.

Follow-up & Tricky Questions:

• How do you write a semi join in SQL? Use EXISTS for the clearest and most portable form. Many optimizers recognize it and turn it into a semi-join plan automatically.
• How is a semi join different from an inner join? An inner join returns matching pairs from both sides, which can duplicate left rows. A semi join only asks whether a match exists and returns the left row once.
• Why is EXISTS often preferred over IN? EXISTS handles NULL behavior more predictably, especially for correlated subqueries. It also communicates existence logic more directly to humans and optimizers.
• Can a semi join return columns from the right table? No. If you need right-side columns, it is no longer a semi join; you need a normal join or another query pattern.
• What is an anti-semi join? It is the opposite: return left rows that have no match on the right. In SQL, that is usually written with NOT EXISTS.
• Does a semi join remove duplicates from the left table? No, not by itself. It only prevents extra duplication caused by multiple right-side matches.
• Is JOIN ... DISTINCT the same as a semi join? Sometimes the final rows look similar, but the work done can be very different. The join may create a large intermediate result before DISTINCT removes duplicates, which is usually less efficient.
• Gotcha: What if the subquery contains NULL? With EXISTS, NULL values usually do not cause trouble unless they affect the join predicate. With IN and especially NOT IN, NULL can change the truth value in surprising ways.
• Gotcha: Is semi join a SQL keyword everywhere? No. Some engines show it in execution plans, but in day-to-day SQL you usually express it with EXISTS or IN.

Common Mistakes:

• Using an inner join when you only need existence. Fix: use EXISTS so you do not create extra row pairs.
• Adding DISTINCT after a join to patch duplicates. Fix: ask whether a semi join is the real intent and filter earlier.
• Forgetting about NULL with NOT IN. Fix: prefer NOT EXISTS for anti-semi join logic.
• Assuming the right side is returned. Fix: remember that a semi join returns only left rows.

Memory Hook: Semi join is a bouncer: it checks the list and lets a left row in, but never hands you the guest list.

Cheat Sheet:

• Semijoin = keep left rows that have at least one right-side match.
• Usually written as WHERE EXISTS (...).
• Right-side duplicates do not duplicate the output.
• Great for existence checks, permissions, active subscriptions, and parent-with-child queries.
• Inner join = pairs; semi join = yes/no filter.
• NOT EXISTS is the anti-semi join pattern.

Practice Tasks:

• Rewrite a customer-orders inner join into an EXISTS query.
• Add duplicate child rows and observe why the semi join output stays stable.
• Replace NOT IN with NOT EXISTS and test a subquery containing NULL.