Semi Join and Anti Join Should Have Their Own Syntax in SQL
lukaseder
Relational algebra nicely describes the various operations that we know in SQL as well from a more abstract, formal perspective. One of the most common relational JOIN operations is the “equi-join” or SQL INNER JOIN.
The above example “equi-joins” the ACTOR, FILM_ACTOR, and FILM tables from the Sakila database, in order to produce a new relation consisting of all the actors and all their associated films.
Relational operators without equivalent SQL syntax
In most cases, SQL is much much more powerful than relational algebra. However, there are three operators in relational algebra, that have no exact representation in SQL, and can only be expressed through “workarounds”. These operators are:
We’ll be looking only at the first two in this article.
The Wikipedia article on relational algebra nicely explains semi join and anti join visually:
Semi join
As you can see, the semi join relation Employee ⋉ Dept only contains attributes from the Employee relation, not from the Dept relation. “Semi” means that we don’t really join the right hand side, we only check if a join would yield results for any given tuple.
In SQL, we would write the same relation using IN or EXISTS:
-- IN
SELECT *
FROM Employee
WHERE DeptName IN (
SELECT DeptName
FROM Dept
)
-- EXISTS
SELECT *
FROM Employee
WHERE EXISTS (
SELECT 1
FROM Dept
WHERE Employee.DeptName = Dept.DeptName
)
Anti join
As you can see, the anti join relaion Employee ▷ Dept only contains attributes from the Employee relation, not from the Dept relation. “Anti” means that we don’t really join the right hand side, we only check if a join would NOT yield results for any given tuple.
In SQL, we would write the same relation using NOT IN or NOT EXISTS (although, in the case of NOT IN, we need to be extra careful with NULLs):
-- NOT IN
SELECT *
FROM Employee
WHERE DeptName NOT IN (
SELECT DeptName
FROM Dept
)
-- NOT EXISTS
SELECT *
FROM Employee
WHERE NOT EXISTS (
SELECT 1
FROM Dept
WHERE Employee.DeptName = Dept.DeptName
)
A better SQL with native SEMI JOIN / ANTI JOIN
While the above IN / NOT IN and EXISTS / NOT EXISTS predicates are useful, they are not at all as expressive as native SEMI JOIN or ANTI JOIN support would be. Imagine, we could write the above statements like this, instead:
Semi join
-- Natural semi join
SELECT *
FROM Employee
NATURAL LEFT SEMI JOIN Dept
-- Semi join with USING clause
SELECT *
FROM Employee
LEFT SEMI JOIN Dept USING (DeptName)
-- Semi join with ON clause
SELECT *
FROM Employee e
LEFT SEMI JOIN Dept d ON e.DeptName = d.DeptName
Anti join
-- Natural anti join
SELECT *
FROM Employee
NATURAL LEFT ANTI JOIN Dept
-- Anti join with USING clause
SELECT *
FROM Employee
LEFT ANTI JOIN Dept USING (DeptName)
-- Anti join with ON clause
SELECT *
FROM Employee e
LEFT ANTI JOIN Dept d ON e.DeptName = d.DeptName
With all of the above options, SQL would be a much more concise language for those cases where we’d like to quickly semi/anti join two relations. In fact, many developers accidentally use INNER JOIN instead, because INNER JOINcan implement a SEMI JOIN when joining a 1:1 or a M:1 relationship. But when they get used to abusing INNER JOIN, they’ll do so as well for 1:N and M:N relationships, ending up with duplicates and removing those again with DISTINCT (see item #6 on this list of 10 common SQL mistakes)
Interestingly enough, Cloudera Impala’s SQL dialect supports these JOIN syntaxes:
SELECT select_list FROM
table_or_subquery1 [INNER] JOIN table_or_subquery2 |
table_or_subquery1
{LEFT [OUTER] | RIGHT [OUTER] | FULL [OUTER]}
JOIN table_or_subquery2 |
table_or_subquery1
{LEFT | RIGHT} SEMI JOIN table_or_subquery2 |table_or_subquery1
{LEFT | RIGHT} ANTI JOIN table_or_subquery2 |
[ ON col1 = col2 [AND col3 = col4 ...] |
USING (col1 [, col2 ...]) ]
[other_join_clause ...]
[ WHERE where_clauses ]
