Replacing NOT EXISTS with an outer join and when to leave out (+)

Replacing NOT EXISTS with an outer join and when to leave out (+)

We came across this trick in Oracle8 when a query using NOT EXISTS took an unreasonable amount of time. After

we replaced it with an outer join, it ran several times faster. We initially doubted whether the result was correct,

so I put together an example to show that it works.

Suppose TZW holds employees and where they live, and TZS holds each employee's

roles or skills.

create table TZW(name varchar2(25), home varchar2(25) );
create table TZS(name varchar2(25), skill varchar2(25));
insert into TZW values ('Tom','TomHouse' );
insert into TZW values ('Jiri','JiriHouse' );
insert into TZW values ('Ruda','RudaHouse' );
insert into TZS values ('Tom','NEW');
insert into TZS values ('Jiri','PROGRAMMER');

We want to list everyone who isn't new (skill isn't NEW). This query does it:

SQL> ed
Zapsáno file afiedt.buf
  1  select TZW.name, home from TZW -- DOTAZ 1
  2* where not exists (select 1 from TZS where TZW.name = TZS.name and TZS.skill = 'NEW')
SQL> /

NAME                      HOME
------------------------- -------------------------
Jiri                      JiriHouse
Ruda                      RudaHouse

This query does the same job, provided the TZS.name column cannot be NULL:

SQL> ed
Zapsáno file afiedt.buf
  1  select TZW.name, home from TZW, TZS -- DOTAZ 2
  2* where TZW.name = TZS.name(+) and TZS.skill(+) = 'NEW' and TZS.name is NULL
SQL> /

NAME                      HOME
------------------------- -------------------------
Jiri                      JiriHouse
Ruda                      RudaHouse

The construction looks unusual because you normally put the plus marker on every column from the outer-joined table. Why

is there no plus marker on TZS.name in the third condition? If we put it there…

SQL> ed
Zapsáno file afiedt.buf
  1  select TZW.name, home from TZW, TZS -- DOTAZ 3
  2* where TZW.name = TZS.name(+) and TZS.skill(+) = 'NEW' and TZS.name(+) is NULL
SQL> /

NAME                      HOME
------------------------- -------------------------
Jiri                      JiriHouse
Ruda                      RudaHouse
Tom                       TomHouse

…we get every value back! :-( Let's look at the problem more closely.

Theory

Although we write SQL statements as SELECT - FROM - WHERE, a simple trick for understanding how a query works is

to read the SQL select in the order FROM - WHERE - SELECT. I find this useful whenever

I need to understand a query. It comes from relational algebra, on which SQL is based. So first a few words

about relational algebra. Let's use the familiar examples from the Oracle manuals, which include the employee table

EMP and the department table DEPT.

In relational algebra we call columns attributes, and a table of n columns

is represented by a relation, a subset of the Cartesian product of the sets of all possible values of the individual attributes. The set

of possible values for an attribute is its domain, so the relation is a subset of the Cartesian product of the domains. A relation is therefore

a set of ordered n-tuples. A note on terminology. It is a mistake to think a database is relational

because there can be relationships between tables, such as 1:N. A relational database is relational even if it has only one table!

For example, the domain of the attribute represented in the database by the EMPNO column of type NUMBER(4) is the set

of all numbers with four digits or fewer. The EMP table corresponds to the relation EMP. The relation's individual n-tuples are the table rows.

Let's look at the three most important operations in relational algebra, inner join,

selection and projection.

An inner join
takes the Cartesian product of two relations and selects the n-tuples that satisfy

the join condition. The join condition brings together data in a meaningful way. This creates a new relation whose

number of attributes is the sum of the attribute counts of the relations being joined.

Selection
means choosing the members of a relation that meet a condition. In relational algebra it is written with parentheses.

For example, selecting all employees hired since January 1, 2000, is written EMP(hiredate>1.1.2000).



It may occur to you that an inner join is really a Cartesian product followed by a selection. That's right. What matters,

especially when we get to outer joins, is that selection based on the join condition and “ordinary” selection serve

different purposes. Selection based on a join condition expresses constraints we must respect to keep

the data model meaningful. Other selections express constraints arising from the logic of

the user application. For example, if we didn't select when joining the EMP and DEPT relations, we'd get a Cartesian product that paired

every employee with every department. In most cases the data within a resulting tuple would make no sense.

If we skip the selection EMP(hiredate>1.1.2000) on the EMP relation, we are left with the EMP relation. That may differ from what

a filter in the application requested, but the tuples still correspond to real objects, employees in this case.



This brings me to why I'm showing relational algebra notation even though it's a theoretical language. It captures

the distinction between the two kinds of selection above. In relational algebra the natural join of EMP and DEPT is written as

EMP*DEPT. The join condition is understood, so we leave it out. (You can probably also specify conditions other than the implicit one,

but I don't want to go that far into relational algebra syntax here.) Relational algebra therefore lets us express what

we want more clearly without making queries harder to read by spelling out the obvious.

Projection
creates a new relation from an existing one by choosing particular attributes from each n-tuple in

the relation. The new relation therefore has the same number of members, but they are m-tuples, where

0<m<=n.

These operations probably make the connection between relational algebra and SQL clear. Joining happens in

FROM, selection in WHERE and projection in SELECT (confusing at first, isn't it? You'll soon

get used to it :-) We can expect the system to return the same data as if it joined all tables first, then performed

selection and finally projection. Implementing it that way would be laughable, but it helps explain the behavior we see. SQL

can of course do somewhat more than relational algebra, but this model is enough to understand outer joins. Moving from relational

algebra to SQL, we lost the distinction between the two kinds of selection conditions above. In SQL, especially Oracle,

we cram everything into WHERE.

Outer joins

The difference becomes noticeable once we start using outer joins. Let's explain it with a left join. A left

outer join of two relations R1 and R2 is a join where, for each member of R1,

• we select the members of R2 that satisfy the join condition (an inner join)
• if no such member exists, the current R1 member still appears in the resulting relation, and the attributes from
• R2 are filled in with NULL values

The notation for an outer join in MS SQL, for instance, follows the theory much more closely than in Oracle. With LEFT OUTER JOIN

ON you specify the join condition in the FROM clause itself. This keeps the

WHERE clause readable and leaves it for application conditions. Unfortunately, in Oracle all the conditions go into

WHERE. A condition with (+) after the column name is a join condition for the outer join, while

conditions without (+) are application conditions (or join conditions for an inner join).

So how do the queries at the start work?

The join condition in query 2 is TZW.name = TZS.name(+) and TZS.skill(+) = 'NEW'.
Joining the tables therefore gives us

(Tom,TomHouse,Tom,NEW)
(Jiri,JiriHouse,NULL,NULL)
(Ruda,RudaHouse,NULL,NULL)

Then we apply selection using TZS.name is NULL and project the result, which gives us the correct answer

(Jiri,JiriHouse)
(Ruda,RudaHouse)

In words, to keep people who meet a condition out of the result, join another table using

that condition. Then keep only the rows where the outer join supplied NULL, since we know it supplied NULL if

and only if the condition wasn't met.

By contrast, the join condition in query 3 is TZW.name = TZS.name(+) and TZS.skill(+) = 'NEW' and TZS.name(+) is

NULL.
Joining the tables therefore gives us

(Tom,TomHouse,NULL,NULL)
(Jiri,JiriHouse,NULL,NULL)
(Ruda,RudaHouse,NULL,NULL)

For the member (Tom,TomHouse) in the TZW table, there is no matching record in TZS,

because no record in TZS meets the third condition.
There is no further condition besides the join condition, so projection gives us the unwanted result

(Tom,TomHouse)
(Jiri,JiriHouse)
(Ruda,RudaHouse)

Links

a question on http://www.google.com


some background on the theory [PDF]