10 Cool SQL Optimisations That do not Depend on the Cost Model

Cost Based Optimisation is the de-facto standard way to optimise SQL queries in most modern databases. It is the reason why it is really really hard to implement a complex, hand-written algorithm in a 3GL (third generation programming language) such as Java that outperforms a dynamically calculated database execution plan, that has been generated from a modern optimiser. I’ve recently delivered a talk about that topic:

Today, we don’t want to talk about cost based optimisation, i.e. optimisations that depend on a database’s cost model. We’ll look into much simpler optimisations that can be implemented purely based on meta data (e.g. constraints) and the query itself. They’re usually no-brainers for a database to optimise, because the optimisation will always lead to a better execution plan, independently of whether there are any indexes, or how much data you have, or how skewed your data distribution is.

So, they’re not no-brainers in the sense whether they’re easy for the optimiser teams to implement, but they’re no-brainers in the sense whether they should be done.

These optimisations remove needless, optional work (as opposed to needless, mandatory work, which I’ve blogged about before)

Where do these optimisations apply?

Most of these optimisations are applied to:

  • Fix mistakes in queries
  • Allow for reusing complex views without actually executing the entire logic from the view

In the first case, you could claim: “Well, then fix the stupid SQL already”, but then again, who never makes any mistakes, right?

Specifically, the second case is really cool, as these optimisations allow us to build complex libraries of views and table valued functions, which we can reuse in several layers.

Databases being used

This post will evaluate 10 SQL optimisations on the 5 most popular RDBMS (according to the db-engines ranking):

  • Oracle 12.2
  • MySQL 8.0.2
  • SQL Server 2014
  • PostgreSQL 9.6
  • DB2 LUW 10.5

In all of this article, I will be using queries against the Sakila database – as always.

Sakila database

These will be the 10 optimisation types:

  1. Transitive Closure
  2. Impossible Predicates and Unneeded Table Accesses
  3. JOIN Elimination
  4. Removing “Silly” Predicates
  5. Projections in EXISTS Subqueries
  6. Predicate Merging
  7. Provably Empty Sets
  8. CHECK Constraints
  9. Unneeded Self JOIN
  10. Predicate Pushdown

One final note before you move on: Many of the following examples might be too simple. Some databases (e.g. SQL Server) might not apply a specific optimisation on a query that is “too trivial”. See also the comments for details.

1. Transitive Closure

Let’s start with something simple: transitive closure. It’s a really trivial concept that applies to a variety of maths operations, e.g. to the equality operator. It can be said that if:

  • A = B and…
  • B = C

then:

  • A = C

Duh, right? But this has some nice implications on SQL optimisers.

Let’s look at an example. Let’s get all films for ACTOR_ID = 1:

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON a.actor_id = fa.actor_id
WHERE a.actor_id = 1;

The result being:

FIRST_NAME      LAST_NAME  FILM_ID
PENELOPE        GUINESS    1
PENELOPE        GUINESS    23
PENELOPE        GUINESS    25
PENELOPE        GUINESS    106
PENELOPE        GUINESS    140
PENELOPE        GUINESS    166
...

Now, observe the execution plan if we run this query in Oracle:

--------------------------------------------------------------
| Id  | Operation                    | Name          | Rows  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT             |               |       |
|   1 |  NESTED LOOPS                |               |    19 |
|   2 |   TABLE ACCESS BY INDEX ROWID| ACTOR         |     1 |
|*  3 |    INDEX UNIQUE SCAN         | PK_ACTOR      |     1 |
|*  4 |   INDEX RANGE SCAN           | PK_FILM_ACTOR |    19 |
--------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   3 - access("A"."ACTOR_ID"=1)
   4 - access("FA"."ACTOR_ID"=1)

Specifically the predicate section is really interesting. The predicate ACTOR_ID = 1 is applied to both the ACTOR and FILM_ACTOR tables because of transitive closure. If:

  • A.ACTOR_ID = 1 (from the WHERE predicate) and…
  • A.ACTOR_ID = FA.ACTOR_ID (from the ON predicate)

Then:

  • FA.ACTOR_ID = 1

In other words, the query is rewritten to this:

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON a.actor_id = fa.actor_id
WHERE a.actor_id = 1
AND fa.actor_id = 1;

Or in this particular case, even this, as the A.ACTOR_ID = 1 predicate ensures a single column from the actor table, so a cross join might do as well (at least that’s what the plan indicates):

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON fa.actor_id = 1
WHERE a.actor_id = 1;

This has a few nice effects on more complex queries. In particular, the cardinality estimates will be much more precise this way, as we can pick the estimate based on a concrete, constant predicate value, rather than e.g. the average number of films per actor as in this query (which returns the same result):

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON a.actor_id = fa.actor_id
WHERE first_name = 'PENELOPE'
AND last_name = 'GUINESS'

The plan being:

----------------------------------------------------------------------------
| Id  | Operation                            | Name                | Rows  |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT                     |                     |       |
|   1 |  NESTED LOOPS                        |                     |     2 |
|*  2 |   TABLE ACCESS BY INDEX ROWID BATCHED| ACTOR               |     1 |
|*  3 |    INDEX RANGE SCAN                  | IDX_ACTOR_LAST_NAME |     3 |
|*  4 |   INDEX RANGE SCAN                   | PK_FILM_ACTOR       |    27 |
----------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - filter("A"."FIRST_NAME"='PENELOPE')
   3 - access("A"."LAST_NAME"='GUINESS')
   4 - access("A"."ACTOR_ID"="FA"."ACTOR_ID")

As you can see, the estimate for the number of FILM_ACTOR rows is too high, and the estimate for the NESTED LOOP result is too low. Here are some interesting numbers:

SELECT count(*) FROM film_actor WHERE actor_id = 1;

SELECT avg(c) FROM (
  SELECT count(*) c FROM film_actor GROUP BY actor_id
);

Resulting in:

19
27.315

That’s where those estimates come from. If the database knows we’re dealing with ACTOR_ID = 1, it can pick the statistics on the number of films for that actor. If it doesn’t know this (because our standard statistics don’t correlate FIRST_NAME / LAST_NAME with ACTOR_ID), then we get the average number of films for any actor. Simple, insignificant error in this particular case, but when that error propagates in a complex query, it can add up and lead to the wrong choice of JOIN down the line (or up the plan).

So, when you can, always design JOIN and ordinary predicates to profit from transitive closure.

What other databases support this?

DB2

Yes

Explain Plan                                               
-----------------------------------------------------------
ID | Operation              |                 Rows | Cost  
 1 | RETURN                 |                      |   13  
 2 |  NLJOIN                |              27 of 1 |   13  
 3 |   FETCH ACTOR          |     1 of 1 (100.00%) |    6  
 4 |    IXSCAN PK_ACTOR     |   1 of 200 (   .50%) |    0  
 5 |   IXSCAN PK_FILM_ACTOR | 27 of 5462 (   .49%) |    6  
                                                           
Predicate Information                                      
 4 - START (Q2.ACTOR_ID = 1)                               
      STOP (Q2.ACTOR_ID = 1)                               
 5 - START (1 = Q1.ACTOR_ID)                               
      STOP (1 = Q1.ACTOR_ID)                               

Btw, want cool execution plans like the above on DB2 LUW? Go visit Markus Winand’s script:
http://use-the-index-luke.com/s/last_explained

MySQL

Unfortunately, MySQL explain plans are not very useful for such analyses. We don’t really see the predicate itself in this output:

ID  SELECT TYPE  TABLE  TYPE   REF    ROWS
------------------------------------------
1   SIMPLE       a      const  const  1 
1   SIMPLE       fa     ref    const  19

But the fact that the REF column is two times “const” indicates that we’re scanning for a constant value in both tables. Conversely, the plan that queries for FIRST_NAME / LAST_NAME looks like this:

ID  SELECT TYPE  TABLE  TYPE   REF         ROWS
-----------------------------------------------
1   SIMPLE       a      ref    const       3 
1   SIMPLE       fa     ref    a.actor_id  27

And you can see that REF has now switched to a column reference from the JOIN predicate. The cardinality estimate is now almost the same as in Oracle.

So, yes, MySQL supports transitive closure, too.

PostgreSQL

Yes

QUERY PLAN                                                                          
------------------------------------------------------------------------------------
Nested Loop  (cost=4.49..40.24 rows=27 width=15)                                    
  ->  Seq Scan on actor a  (cost=0.00..4.50 rows=1 width=17)                        
        Filter: (actor_id = 1)                                                      
  ->  Bitmap Heap Scan on film_actor fa  (cost=4.49..35.47 rows=27 width=4)         
        Recheck Cond: (actor_id = 1)                                                
        ->  Bitmap Index Scan on film_actor_pkey  (cost=0.00..4.48 rows=27 width=0) 
              Index Cond: (actor_id = 1)                                            

SQL Server

Yes

  |--Nested Loops(Inner Join)
       |--Nested Loops(Inner Join)
       |    |--Index Seek (SEEK:([a].[actor_id]=(1)))
       |    |--RID Lookup
       |--Index Seek (SEEK:([fa].[actor_id]=(1)))

Summary

All databases can do transitive closure:

Database Transitive closure
DB2 LUW 10.5 Yep
MySQL 8.0.2 Yep
Oracle 12.2.0.1 Yep
PostgreSQL 9.6 Yep
SQL Server 2014 Yep

Stay tuned, though, for #6. There are more complex cases of transitive closure, where not all databases get it right.

2. Impossible Predicates and Unneeded Table Accesses

This optimisation is really silly, but hey, why not. If users write impossible predicates, then why even execute them? Here are some examples:

-- "Obvious"
SELECT * FROM actor WHERE 1 = 0

-- "Subtle"
SELECT * FROM actor WHERE NULL = NULL

The first query should obviously never return any results, but the same is true for the second one, because while NULL IS NULL yields TRUE, always, NULL = NULL evaluates to NULL, which has the same effect as FALSE according to three-valued logic.

This doesn’t need much explanation, so let’s immediately jump to see which databases optimise this:

DB2

Yes

Explain Plan                       
-----------------------------------
ID | Operation      |   Rows | Cost
 1 | RETURN         |        |    0
 2 |  TBSCAN GENROW | 0 of 0 |    0

As you can see, the table access to the ACTOR table is completely eliminated from the plan. There’s only a GENROW operation, which generates zero rows. Perfect.

MySQL

Yes

ID  SELECT TYPE  TABLE   EXTRAS
-----------------------------------------
1   SIMPLE         Impossible WHERE

This time, MySQL has been so kind to indicate that the WHERE clause is impossible. Thanks, that’s helpful when analysing – more than the other databases

Oracle

Yes

---------------------------------------------------------------
| Id  | Operation          | Name  | Starts | E-Rows | A-Rows |
---------------------------------------------------------------
|   0 | SELECT STATEMENT   |       |      1 |        |      0 |
|*  1 |  FILTER            |       |      1 |        |      0 |
|   2 |   TABLE ACCESS FULL| ACTOR |      0 |    200 |      0 |
---------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - filter(NULL IS NOT NULL)

Now, observe that the plan still shows the table access to the ACTOR table, and the estimated number of rows is still 200, but there’s a FILTER operation on Id=1, which can never be true. Because Oracle really really doesn’t like the SQL standard BOOLEAN type, they display NULL IS NOT NULL in the plan, rather than simply FALSE. Oh well 🙂

But seriously, do check for this predicate. I’ve been debugging 1000-line-long execution plan subtrees with super high costs before noticing that the entire subtree was “cut off” by NULL IS NOT NULL. A bit misleading, if you ask me.

PostgreSQL

Yes

QUERY PLAN                                 
-------------------------------------------
Result  (cost=0.00..0.00 rows=0 width=228) 
  One-Time Filter: false                   

That’s nicer. No noisy ACTOR access and a nice little FALSE predicate.

SQL Server

Yes

  |--Constant Scan

SQL Server calls this a “constant scan”, i.e. a scan where nothing happens – just like DB2.

All databases can eliminate impossible predicates:

Database Impossible predicates Unneeded table access
DB2 LUW 10.5 Yep Yep
MySQL 8.0.2 Yep Yep
Oracle 12.2.0.1 Yep Yep
PostgreSQL 9.6 Yep Yep
SQL Server 2014 Yep Yep

3. JOIN Elimination

In the previous section, we’ve seen unneeded table access for single table queries. But what happens if one out of several table accesses is unneeded in a JOIN?

I’ve already blogged about JOIN elimination in a previous blog post. SQL engines can determine, based on the way a query is written, and based on the presence of PRIMARY KEYs and FOREIGN KEYs, whether any given JOIN is really required in a query, or whether it could be eliminated without affecting the semantics of the query.

In all of the following three examples, the JOIN is unnecessary:

to-one INNER JOINs can be removed if there’s a NOT NULL FOREIGN KEY

Instead of this:

SELECT first_name, last_name
FROM customer c
JOIN address a ON c.address_id = a.address_id

The database can run this:

SELECT first_name, last_name
FROM customer c

to-one INNER JOINs can be replaced if there’s a nullable FOREIGN KEY

The above works if there’s also a NOT NULL constraint on the FOREIGN KEY. If there isn’t, e.g. as in this query:

SELECT title
FROM film f
JOIN language l ON f.original_language_id = l.language_id

The JOIN can still be eliminated, but there needs to be a replacement NOT NULL predicate, as such:

SELECT title
FROM film
WHERE original_language_id IS NOT NULL

to-one OUTER JOINs can be removed if there’s a UNIQUE KEY

Instead of this:

SELECT first_name, last_name
FROM customer c
LEFT JOIN address a ON c.address_id = a.address_id

The database can again run this:

SELECT first_name, last_name
FROM customer c

… even if there is no FOREIGN KEY on CUSTOMER.ADDRESS_ID.

to-many DISTINCT OUTER JOINs can be removed

Instead of this:

SELECT DISTINCT first_name, last_name
FROM actor a
LEFT JOIN film_actor fa ON a.actor_id = fa.actor_id

The database can run this:

SELECT DISTINCT first_name, last_name
FROM actor a

All of these examples are explained in detail in the previous article, so I’m not going to repeat it, but here’s again the summary of what each database can eliminate:

Here’s a summary of what databases can eliminate:

Database INNER JOIN:
to-one
INNER JOIN nullable:
to-one
OUTER JOIN:
to-one
OUTER JOIN DISTINCT:
to-many
DB2 LUW 10.5 Yep Yep Yep Yep
MySQL 8.0.2 Nope Nope Nope Nope
Oracle 12.2.0.1 Yep Yep Yep Nope
PostgreSQL 9.6 Nope Nope Yep Nope
SQL Server 2014 Yep Nope Yep Yep

Unfortunately, not all databases can eliminate all joins. DB2 and SQL Server are the clear winners here!

4. Removing “Silly” Predicates

Equally silly are predicates that are (almost) always true. As you can imagine, if you search for

SELECT * FROM actor WHERE 1 = 1;

Then, databases will not actually evaluate the predicate but ignore it. This was a recent Stack Overflow question that I’ve answered, which actually gave me the idea to write this blog post.

I’ll leave it to you to check this, but what happens if the predicate is just slightly less silly, e.g.:

SELECT * FROM film WHERE release_year = release_year;

Do we actually have to compare the value with itself on each row? No, there’s no value where this can be FALSE, right? Right. But we still have to do a check. While the predicate can never be FALSE, it can totally be NULL, again because of three valued logic. The RELEASE_YEAR column is a nullable column, and if RELEASE_YEAR IS NULL for any given row, then NULL = NULL yields NULL, and the row must be excluded.

So, the query is transformed into this:

SELECT * FROM film WHERE release_year IS NOT NULL;

Which databases do this?

DB2

Yes

Explain Plan                                     
-------------------------------------------------
ID | Operation    |                   Rows | Cost
 1 | RETURN       |                        |   49
 2 |  TBSCAN FILM | 1000 of 1000 (100.00%) |   49
                                                 
Predicate Information                            
 2 - SARG Q1.RELEASE_YEAR IS NOT NULL            

MySQL

Very regrettably, again, because MySQL doesn’t display predicates in their execution plans, it’s a bit hard to find out whether MySQL performs this particular optimisation. We could benchmark things and see if some really big string comparisons are executed or not. Or, we add an index:

CREATE INDEX i_release_year ON film (release_year);

And get the plans for these queries instead:

SELECT * FROM film WHERE release_year = release_year;
SELECT * FROM film WHERE release_year IS NOT NULL;

If the optimisation works, then both queries should produce exactly the same plan. But they don’t in this case:

ID  TABLE  POSSIBLE_KEYS   ROWS  FILTERED  EXTRA
------------------------------------------------------
1   film             1000  10.00           Using where

ID  TABLE  POSSIBLE_KEYS   ROWS  FILTERED  EXTRA
------------------------------------------------------
1   film   i_release_year  1000  100.00    Using where

As you can see, the two queries differ substantially in that the POSSIBLE_KEYS and FILTERED columns yield different values. I’m making an educated guess and say MySQL does not optimise this.

Oracle

Yes

----------------------------------------------------
| Id  | Operation         | Name | Starts | E-Rows |
----------------------------------------------------
|   0 | SELECT STATEMENT  |      |      1 |        |
|*  1 |  TABLE ACCESS FULL| FILM |      1 |   1000 |
----------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - filter("RELEASE_YEAR" IS NOT NULL)

PostgreSQL

Disappointingly, no!

QUERY PLAN                                                    
--------------------------------------------------------------
Seq Scan on film  (cost=0.00..67.50 rows=5 width=386)         
  Filter: ((release_year)::integer = (release_year)::integer) 

The plans and the costs are different. Specifically, observe the cardinality estimate, which is totally off, when this predicate:

SELECT * FROM film WHERE release_year IS NOT NULL;

… yields much better results

QUERY PLAN                                               
---------------------------------------------------------
Seq Scan on film  (cost=0.00..65.00 rows=1000 width=386) 
  Filter: (release_year IS NOT NULL)                     

Bummer!

SQL Server

Surprisingly, also SQL Server doesn’t seem to do this:

  |--Table Scan(OBJECT:([film]), WHERE:([release_year]=[release_year]))

However, the cardinality estimate is correct when looking at the visual plan, and the costs are all correct as well. From what I’ve seen in the past on SQL Server, though, I’m going to say that in this case, the optimisation is not taking place because SQL server would display the actually executed predicate in the plan (look at the CHECK constraint examples below to see why).

What about “silly” predicates on NOT NULL columns?

The above transformation was only needed, because RELEASE_YEAR is a nullable column. What if we did the same silly query with e.g. FILM_ID?

SELECT * FROM film WHERE film_id = film_id

This is now the same as not putting a predicate at all. Or at least it should be. Is it, though?

DB2

Yes!

Explain Plan                                     
-------------------------------------------------
ID | Operation    |                   Rows | Cost
 1 | RETURN       |                        |   49
 2 |  TBSCAN FILM | 1000 of 1000 (100.00%) |   49

No predicate is applied at all, and we’re selecting all the films.

MySQL

Yes (educated guess, again)

ID  TABLE  POSSIBLE_KEYS   ROWS  FILTERED  EXTRA
------------------------------------------------------
1   film                   1000  100.00

Observe how now the EXTRA column is empty as if we didn’t have any WHERE clause!

Oracle

Yes

----------------------------------------------------
| Id  | Operation         | Name | Starts | E-Rows |
----------------------------------------------------
|   0 | SELECT STATEMENT  |      |      1 |        |
|   1 |  TABLE ACCESS FULL| FILM |      1 |   1000 |
----------------------------------------------------

Again, no predicates are applied.

PostgreSQL

Gee, still no!

QUERY PLAN                                            
------------------------------------------------------
Seq Scan on film  (cost=0.00..67.50 rows=5 width=386) 
  Filter: (film_id = film_id)                         

The filter is applied and the cardinality estimate is still 5. Bummer!

SQL Server

Also, still no!

  |--Table Scan(OBJECT:([film]), WHERE:([film_id]=[film_id]))

Summary

This appears like a simple optimisation, but it is not applied in all databases, surprisingly not in SQL Server!

Database Silly but needed predicates
(NULL semantics)
Silly unneeded predicates
(no NULL semantics)
DB2 LUW 10.5 Yep Yep
MySQL 8.0.2 Nope Yep
Oracle 12.2.0.1 Yep Yep
PostgreSQL 9.6 Nope Nope
SQL Server 2014 Nope Nope

5. Projections in EXISTS Subqueries

Interestingly, this one, I get asked all the time in my SQL Masterclass where I advocate that SELECT * is mostly bad.

The question then is, is it OK to use SELECT * in an EXISTS subquery? For instance, if we wanted to find actors who have played in films:

SELECT first_name, last_name
FROM actor a
WHERE EXISTS (
  SELECT * -- Is this OK?
  FROM film_actor fa
  WHERE a.actor_id = fa.actor_id
)

And the answer is: Yes it is OK. The asterisk has no impact on the query. How can we “prove” this? Consider the following query:

-- DB2
SELECT 1 / 0 FROM sysibm.dual

-- Oracle
SELECT 1 / 0 FROM dual

-- PostgreSQL, SQL Server
SELECT 1 / 0

-- MySQL
SELECT pow(-1, 0.5);

All databases report a division by zero error. Note that interestingly, in MySQL, dividing by zero yields NULL, not an error, so we’re doing something else that’s illegal.

Now, what happens if we do this, instead?

-- DB2
SELECT CASE WHEN EXISTS (
  SELECT 1 / 0 FROM sysibm.dual
) THEN 1 ELSE 0 END
FROM sysibm.dual

-- Oracle
SELECT CASE WHEN EXISTS (
  SELECT 1 / 0 FROM dual
) THEN 1 ELSE 0 END
FROM dual

-- PostgreSQL
SELECT EXISTS (SELECT 1 / 0)

-- SQL Server
SELECT CASE WHEN EXISTS (
  SELECT 1 / 0
) THEN 1 ELSE 0 END

-- MySQL
SELECT EXISTS (SELECT pow(-1, 0.5));

Now, none of the databases fail the query. All of them return TRUE or 1. This means that none of the databases actually evaluated the projection (i.e. the SELECT clause) of the EXISTS subquery.

SQL Server, for instance, shows the following plan:

  |--Constant Scan(VALUES:((CASE WHEN (1) THEN (1) ELSE (0) END)))

As you can see, the CASE expression was transformed to a constant, the subquery has been eliminated. Other databases still have the subquery in their plan and don’t mention anything about a projection, so let’s again look at the original query’s plan in Oracle:

SELECT first_name, last_name
FROM actor a
WHERE EXISTS (
  SELECT *
  FROM film_actor fa
  WHERE a.actor_id = fa.actor_id
)

The plan for the above is:

------------------------------------------------------------------
| Id  | Operation             | Name                    | E-Rows |
------------------------------------------------------------------
|   0 | SELECT STATEMENT      |                         |        |
|*  1 |  HASH JOIN SEMI       |                         |    200 |
|   2 |   TABLE ACCESS FULL   | ACTOR                   |    200 |
|   3 |   INDEX FAST FULL SCAN| IDX_FK_FILM_ACTOR_ACTOR |   5462 |
------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - access("A"."ACTOR_ID"="FA"."ACTOR_ID")
 
Column Projection Information (identified by operation id):
-----------------------------------------------------------
 
   1 - (#keys=1) LAST_NAME, FIRST_NAME
   2 - (rowset=256) A.ACTOR_ID, FIRST_NAME, LAST_NAME
   3 - FA.ACTOR_ID

Observe the projection information on the FILM_ACTOR access in Id=3. In fact, we’re not even accessing the FILM_ACTOR table, because we don’t have to. The EXISTS predicate can be executed using the foreign key index on the ACTOR_ID column only, that’s all we need for this query – despite us having written SELECT *

Summary

Luckily, all databases can remove the projection in EXISTS subqueries

Database EXISTS projection
DB2 LUW 10.5 Yep
MySQL 8.0.2 Yep
Oracle 12.2.0.1 Yep
PostgreSQL 9.6 Yep
SQL Server 2014 Yep

6. Predicate Merging

This one is interesting and has bitten me in the past when I erroneously assumed that a given database could do it.

Consider the following query:

SELECT * 
FROM actor
WHERE actor_id IN (2, 3, 4)
AND actor_id IN (1, 2, 3);

Obviously, the two predicates overlap and can be merged. I would expect the database to transform the above into:

SELECT * 
FROM actor
WHERE actor_id IN (2, 3);

Looks obvious, right? It is a more sophisticated case of transitive closure. Another case would be merging two ranges. When running the following query:

SELECT * 
FROM film
WHERE film_id BETWEEN 1 AND 100
AND film_id BETWEEN 99 AND 200

We’d hope for the database to rewrite the query to this:

SELECT * 
FROM film
WHERE film_id BETWEEN 99 AND 100

The cardinality of the latter predicate should be 2 rows, but the first, combined ranges might not look like it, and the database might choose a full table scan when it should pick the index

Which database can do these optimisations?

DB2

Merging IN predicates

Yes

Explain Plan                                      
--------------------------------------------------
ID | Operation         |               Rows | Cost
 1 | RETURN            |                    |   11
 2 |  FETCH ACTOR      |   2 of 2 (100.00%) |   11
 3 |   IXSCAN PK_ACTOR | 2 of 200 (  1.00%) |    0
                                                  
Predicate Information                             
 3 - SARG Q3.ACTOR_ID IN (2, 3)                   

Merging range predicates

Yes (but don’t be fooled by the plan!)

Explain Plan                                      
--------------------------------------------------
ID | Operation        |                Rows | Cost
 1 | RETURN           |                     |   13
 2 |  FETCH FILM      |    2 of 2 (100.00%) |   13
 3 |   IXSCAN PK_FILM | 2 of 1000 (   .20%) |    6
                                                  
Predicate Information                             
 3 - START (99 <= Q1.FILM_ID)                     
      STOP (Q1.FILM_ID <= 100)                    
      SARG (Q1.FILM_ID <= 200)                    
      SARG (1 <= Q1.FILM_ID)                      

As you can see, the predicate was not optimised away entirely. There’s still a filter (SARG) that checks for the overall upper and lower bounds of the combined range, but the important bits are the START and STOP operations, which indicate fast index access. Besides, the cardinality is also correct.

If you want to be sure, just run this impossible predicate here:

SELECT * 
FROM film
WHERE film_id BETWEEN 1 AND 2
AND film_id BETWEEN 199 AND 200;

To get the correct plan:

Explain Plan                       
-----------------------------------
ID | Operation      |   Rows | Cost
 1 | RETURN         |        |    0
 2 |  TBSCAN GENROW | 0 of 0 |    0
                                   
Predicate Information              
 2 - RESID (1 = 0)                 

MySQL

Merging IN predicates

Again, unfortunately, MySQL doesn’t display the predicate information very nicely. We get the same plan for both queries:

ID  TABLE  TYPE   KEY      ROWS  FILTERED  EXTRA
------------------------------------------------------
1   actor  range  PRIMARY  2     100.00    Using where

2x the same cardinalities, 2x “Using where” with no indication what exactly is being done inside of “where”, but given the cardinality, we can assume that the transformation happened correctly. We can look at it differently, let’s try this query:

SELECT * FROM actor
WHERE actor_id IN (3, 4, 5)
AND actor_id IN (1, 2, 3);

Which should be transformed into this one:

SELECT * FROM actor
WHERE actor_id = 3;

And indeed, it happens:

ID  TABLE  TYPE   KEY      ROWS  FILTERED  EXTRA
------------------------------------------------------
1   actor  const  PRIMARY  1     100.00

Observe how TYPE=range changed to TYPE=const

So, we can conclude that yes, MySQL implements this optimisation.

Merging range predicates

Again, the plan is not helpful at all:

ID  TABLE  TYPE   KEY      ROWS  FILTERED  EXTRA
------------------------------------------------------
1   film   range  PRIMARY  2     100.00    Using where

But we can again prove that the optimisation is being done by creating an “impossible” predicate as such:

SELECT * 
FROM film
WHERE film_id BETWEEN 1 AND 2
AND film_id BETWEEN 199 AND 200

In case of which the plan switches to:

ID  TABLE  EXTRA
-----------------------------------------
1          no matching row in const table

So, again good news for MySQL

Oracle

Merging IN predicates

Yes

----------------------------------------------------------
| Id  | Operation                    | Name     | E-Rows |
----------------------------------------------------------
|   0 | SELECT STATEMENT             |          |        |
|   1 |  INLIST ITERATOR             |          |        |
|   2 |   TABLE ACCESS BY INDEX ROWID| ACTOR    |      2 |
|*  3 |    INDEX UNIQUE SCAN         | PK_ACTOR |      2 |
----------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   3 - access(("ACTOR_ID"=2 OR "ACTOR_ID"=3))

The predicate being applied only includes the values 2 and 3, so the transformation has worked out correctly.

Merging range predicates

Again, yes:

----------------------------------------------------------------
| Id  | Operation                           | Name    | E-Rows |
----------------------------------------------------------------
|   0 | SELECT STATEMENT                    |         |        |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| FILM    |      2 |
|*  2 |   INDEX RANGE SCAN                  | PK_FILM |      2 |
----------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - access("FILM_ID">=99 AND "FILM_ID"<=100)

PostgreSQL

Merging IN predicates

Regrettably, no, this is not optimised!

QUERY PLAN                                                                                     
-----------------------------------------------------------------------------------------------
Seq Scan on actor  (cost=0.00..5.50 rows=1 width=25)                                           
  Filter: ((actor_id = ANY ('{2,3,4}'::integer[])) AND (actor_id = ANY ('{1,2,3}'::integer[])))

Both predicates are still present in the execution plan, and the cardinality estimate is wrong, it should be 2, not 1. If I manually transform the query, I’m getting this plan instead:

QUERY PLAN                                           
-----------------------------------------------------
Seq Scan on actor  (cost=0.00..4.50 rows=2 width=25) 
  Filter: (actor_id = ANY ('{2,3}'::integer[]))      

In particular, we can see the wrong plan if the two predicates do not overlap, in case of which an impossible predicate is formed:

SELECT * 
FROM actor
WHERE actor_id IN (2, 3, 4)
AND actor_id IN (7, 8, 9)

Still, this yields a “wrong” plan:

QUERY PLAN                                                                                     
-----------------------------------------------------------------------------------------------
Seq Scan on actor  (cost=0.00..5.50 rows=1 width=25)                                           
  Filter: ((actor_id = ANY ('{2,3,4}'::integer[])) AND (actor_id = ANY ('{7,8,9}'::integer[])))

Bummer!

Merging range predicates

This doesn’t look better

QUERY PLAN                                                                                  
--------------------------------------------------------------------------------------------
Index Scan using film_pkey on film  (cost=0.28..8.30 rows=1 width=386)                      
  Index Cond: ((film_id >= 1) AND (film_id <= 100) AND (film_id >= 99) AND (film_id <= 200))

Now, it’s hard to say whether this worked or not. Ultimately, we have gotten the correct plan with a reasonable cardinality as before, and it might just work out as on DB2. But what happens if we again create an impossible predicate?

SELECT * 
FROM film
WHERE film_id BETWEEN 1 AND 2
AND film_id BETWEEN 199 AND 200;

The plan got worse:

QUERY PLAN                                                                                 
-------------------------------------------------------------------------------------------
Index Scan using film_pkey on film  (cost=0.28..8.42 rows=5 width=386)                     
  Index Cond: ((film_id >= 1) AND (film_id >= 2) AND (film_id >= 199) AND (film_id >= 200))

The cardinality increased instead of it decreasing! And after all, we shouldn’t run this query anyway. No points for PostgreSQL

SQL Server

Merging IN predicates

Yes, this works:

  |--Nested Loops(Inner Join)
       |--Index Seek(SEEK:([actor_id]=(2) OR [actor_id]=(3)))
       |--RID Lookup(OBJECT:([actor]))

Merging range predicates

This again looks like the DB2 case:

  |--Nested Loops(Inner Join)
       |--Index Seek(SEEK:([film_id] >= (1) AND [film_id] <= (100)), WHERE:([film_id]>=(99) AND [film_id]<=(200)))
       |--RID Lookup(OBJECT:([film]))

Unfortunately, observe the distinction between SEEK and WHERE. We want the range [99, 100] in SEEK (as DB2 did) because SEEK is the fast, O(log N) index access, whereas WHERE is linear in O(N) time. Bummer!

This looks like a bug to me, because the impossible predicate yields a more reasonable:

  |--Constant Scan

Summary

Note that there are many different kinds of predicates that might be merged in one database but not in the other. If in doubt, do check your execution plans!

Database Merging IN Merging ranges
DB2 LUW 10.5 Yep Yep
MySQL 8.0.2 Yep Yep
Oracle 12.2.0.1 Yep Yep
PostgreSQL 9.6 Nope Nope
SQL Server 2014 Yep Nope

7. Provably Empty Sets

This one is really cool. We’ve seen Impossible predicates and unneeded table accesses before. What if we do this again, but this time with a JOIN? Can JOIN elimination kick in, too?

We’re trying these queries:

IS NULL on NOT NULL column

The predicate in the WHERE clause cannot be TRUE, because we have a NOT NULL constraint on the FILM_ID column.

SELECT first_name, last_name
FROM actor a
JOIN (
  SELECT *
  FROM film_actor
  WHERE film_id IS NULL
) fa ON a.actor_id = fa.actor_id;

The derived table FA cannot return any rows, because of that NOT NULL constraint on the FA.FILM_ID column, so it is provably empty. Because an INNER JOIN with an empty table cannot produce any rows either, this should save us from accessing the ACTOR table, so the above query should be rewritten to something like this:

SELECT NULL AS first_name, NULL AS last_name
WHERE 1 = 0;

I.e. the predicate is never evaluated and the JOIN is eliminated.

INTERSECT NULL and NOT NULL columns

In principle, this is the same as the previous example, but using a bit more sophisticated syntax:

SELECT *
FROM actor a
JOIN (
  SELECT actor_id, film_id
  FROM film_actor
  INTERSECT
  SELECT NULL, NULL
  FROM dual
) fa ON a.actor_id = fa.actor_id;

Because of the NOT NULL constraints on both FA.ACTOR_ID and FA.FILM_ID, an INTERSECT operation with a (NULL, NULL) tuple should not yield any results, and thus the derived table is provably empty, and thus the INNER JOIN can be eliminated.

Funky, but why not?

Let’s repeat, with EXISTS

Finally, let’s repeat the above type of query, but this time with an SEMI JOIN instead of an INNER JOIN. First with an impossible predicate

SELECT *
FROM actor a
WHERE a.actor_id IN (
  SELECT actor_id
  FROM film_actor
  WHERE actor_id IS NULL
);

… then again with an intersection.

SELECT *
FROM actor a
WHERE a.actor_id IN (
  SELECT actor_id
  FROM film_actor
  INTERSECT
  SELECT NULL
  FROM sysibm.dual
)

Let’s go. Which database can do which optimisation?

DB2

Joining a provably empty set (IS NULL predicate):

Explain Plan                       
-----------------------------------
ID | Operation      |   Rows | Cost
 1 | RETURN         |        |    0
 2 |  TBSCAN GENROW | 0 of 0 |    0
                                   
Predicate Information              
 2 - RESID (1 = 0)                 

Joining a provably empty set (INTERSECT):

Explain Plan                       
-----------------------------------
ID | Operation      |   Rows | Cost
 1 | RETURN         |        |    0
 2 |  TBSCAN GENROW | 0 of 0 |    0
                                   
Predicate Information              
 2 - RESID (1 = 0)                 

Semi joining a provably empty set (IS NULL predicate):

Explain Plan                       
-----------------------------------
ID | Operation      |   Rows | Cost
 1 | RETURN         |        |    0
 2 |  TBSCAN GENROW | 0 of 0 |    0
                                   
Predicate Information              
 2 - RESID (1 = 0)                 

Semi joining a provably empty set (INTERSECT):

Explain Plan                       
-----------------------------------
ID | Operation      |   Rows | Cost
 1 | RETURN         |        |    0
 2 |  TBSCAN GENROW | 0 of 0 |    0
                                   
Predicate Information              
 2 - RESID (1 = 0)                 

Wow, cool! Looks like a winner!

MySQL

Joining a provably empty set (IS NULL predicate):

ID  TABLE   EXTRA
----------------------------
1           Impossible WHERE

Cool! I didn’t expect this!

Joining a provably empty set (INTERSECT):

MySQL doesn’t support INTERSECT, regrettably.

Semi joining a provably empty set (IS NULL predicate):

ID  TABLE   EXTRA
----------------------------
1           Impossible WHERE

Semi joining a provably empty set (INTERSECT):

MySQL doesn’t support INTERSECT, regrettably.

But still, that’s a great result for MySQL!

Oracle

Joining a provably empty set (IS NULL predicate):

---------------------------------------------------------------------------
| Id  | Operation              | Name          | Starts | E-Rows | A-Rows |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT       |               |      1 |        |      0 |
|*  1 |  FILTER                |               |      1 |        |      0 |
|*  2 |   HASH JOIN            |               |      0 |   5462 |      0 |
|   3 |    TABLE ACCESS FULL   | ACTOR         |      0 |    200 |      0 |
|   4 |    INDEX FAST FULL SCAN| PK_FILM_ACTOR |      0 |   5462 |      0 |
---------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - filter(NULL IS NOT NULL)
   2 - access("A"."ACTOR_ID"="FILM_ACTOR"."ACTOR_ID")

Again, a very confusing execution plan in Oracle, but the NULL IS NOT NULL filter is there, and it happens before all the other operations, which are not executed.

Joining a provably empty set (INTERSECT):

---------------------------------------------------------------------------------
| Id  | Operation                    | Name          | Starts | E-Rows | A-Rows |
---------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |               |      1 |        |      0 |
|   1 |  NESTED LOOPS                |               |      1 |      1 |      0 |
|   2 |   NESTED LOOPS               |               |      1 |      1 |      0 |
|   3 |    VIEW                      |               |      1 |      1 |      0 |
|   4 |     INTERSECTION             |               |      1 |        |      0 |
|   5 |      SORT UNIQUE             |               |      1 |   5462 |   5463 |
|   6 |       INDEX FAST FULL SCAN   | PK_FILM_ACTOR |      1 |   5462 |   5463 |
|   7 |      FAST DUAL               |               |      1 |      1 |      1 |
|*  8 |    INDEX UNIQUE SCAN         | PK_ACTOR      |      0 |      1 |      0 |
|   9 |   TABLE ACCESS BY INDEX ROWID| ACTOR         |      0 |      1 |      0 |
---------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   8 - access("A"."ACTOR_ID"="FA"."ACTOR_ID")

Interesting. This plan will indeed access the entire FILM_ACTOR primary key. It can save accesses to the ACTOR table and primary key index, because it does the derived table first (which yields no rows), but still those Ids=5 and 6 should not be there. Bummer!

Semi joining a provably empty set (IS NULL predicate):

This works again:

-------------------------------------------------------------------------------------
| Id  | Operation              | Name                    | Starts | E-Rows | A-Rows |
-------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT       |                         |      1 |        |      0 |
|*  1 |  FILTER                |                         |      1 |        |      0 |
|*  2 |   HASH JOIN SEMI       |                         |      0 |    200 |      0 |
|   3 |    TABLE ACCESS FULL   | ACTOR                   |      0 |    200 |      0 |
|   4 |    INDEX FAST FULL SCAN| IDX_FK_FILM_ACTOR_ACTOR |      0 |   5462 |      0 |
-------------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - filter(NULL IS NOT NULL)
   2 - access("A"."ACTOR_ID"="ACTOR_ID")

… with the same confusing plan that keeps around the unexecuted subtree.

Semi joining a provably empty set (INTERSECT):

Again, no optimisation here:

-------------------------------------------------------------------------------------------
| Id  | Operation                    | Name                    | Starts | E-Rows | A-Rows |
-------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                         |      1 |        |      0 |
|   1 |  NESTED LOOPS                |                         |      1 |      1 |      0 |
|   2 |   NESTED LOOPS               |                         |      1 |      1 |      0 |
|   3 |    VIEW                      | VW_NSO_1                |      1 |      1 |      0 |
|   4 |     INTERSECTION             |                         |      1 |        |      0 |
|   5 |      SORT UNIQUE             |                         |      1 |   5462 |    200 |
|   6 |       INDEX FAST FULL SCAN   | IDX_FK_FILM_ACTOR_ACTOR |      1 |   5462 |   5463 |
|   7 |      FAST DUAL               |                         |      1 |      1 |      1 |
|*  8 |    INDEX UNIQUE SCAN         | PK_ACTOR                |      0 |      1 |      0 |
|   9 |   TABLE ACCESS BY INDEX ROWID| ACTOR                   |      0 |      1 |      0 |
-------------------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   8 - access("A"."ACTOR_ID"="ACTOR_ID")

Not so good!

PostgreSQL

Disappointingly, PostgreSQL doesn’t fare well in this experiment!

Joining a provably empty set (IS NULL predicate):

Nope:

QUERY PLAN                                                                                  
--------------------------------------------------------------------------------------------
Hash Join  (cost=8.31..13.07 rows=1 width=13)                                               
  Hash Cond: (a.actor_id = film_actor.actor_id)                                             
  ->  Seq Scan on actor a  (cost=0.00..4.00 rows=200 width=17)                              
  ->  Hash  (cost=8.30..8.30 rows=1 width=2)                                                
        ->  Index Scan using idx_fk_film_id on film_actor  (cost=0.28..8.30 rows=1 width=2) 
              Index Cond: (film_id IS NULL)                                                 

Joining a provably empty set (INTERSECT):

Even worse:

QUERY PLAN                                                                                         
---------------------------------------------------------------------------------------------------
Hash Join  (cost=166.60..171.36 rows=1 width=29)                                                   
  Hash Cond: (a.actor_id = fa.actor_id)                                                            
  ->  Seq Scan on actor a  (cost=0.00..4.00 rows=200 width=25)                                     
  ->  Hash  (cost=166.59..166.59 rows=1 width=4)                                                   
        ->  Subquery Scan on fa  (cost=0.00..166.59 rows=1 width=4)                                
              ->  HashSetOp Intersect  (cost=0.00..166.58 rows=1 width=8)                          
                    ->  Append  (cost=0.00..139.26 rows=5463 width=8)                              
                          ->  Subquery Scan on "*SELECT* 2"  (cost=0.00..0.02 rows=1 width=8)      
                                ->  Result  (cost=0.00..0.01 rows=1 width=4)                       
                          ->  Subquery Scan on "*SELECT* 1"  (cost=0.00..139.24 rows=5462 width=8) 
                                ->  Seq Scan on film_actor  (cost=0.00..84.62 rows=5462 width=4)   

Semi joining a provably empty set (IS NULL predicate):

Same as inner join:

QUERY PLAN                                                                                       
-------------------------------------------------------------------------------------------------
Hash Semi Join  (cost=6.06..10.60 rows=1 width=25)                                               
  Hash Cond: (a.actor_id = film_actor.actor_id)                                                  
  ->  Seq Scan on actor a  (cost=0.00..4.00 rows=200 width=25)                                   
  ->  Hash  (cost=6.05..6.05 rows=1 width=2)                                                     
        ->  Index Only Scan using film_actor_pkey on film_actor  (cost=0.28..6.05 rows=1 width=2)
              Index Cond: (actor_id IS NULL)                                                     

Semi joining a provably empty set (INTERSECT):

Unsurprisingly:

QUERY PLAN                                                                                        
--------------------------------------------------------------------------------------------------
Hash Semi Join  (cost=152.94..157.48 rows=1 width=25)                                             
  Hash Cond: (a.actor_id = "ANY_subquery".actor_id)                                               
  ->  Seq Scan on actor a  (cost=0.00..4.00 rows=200 width=25)                                    
  ->  Hash  (cost=152.93..152.93 rows=1 width=2)                                                  
        ->  Subquery Scan on "ANY_subquery"  (cost=0.00..152.93 rows=1 width=2)                   
              ->  HashSetOp Intersect  (cost=0.00..152.92 rows=1 width=6)                         
                    ->  Append  (cost=0.00..139.26 rows=5463 width=6)                             
                          ->  Subquery Scan on "*SELECT* 2"  (cost=0.00..0.02 rows=1 width=6)     
                                ->  Result  (cost=0.00..0.01 rows=1 width=2)                      
                          ->  Subquery Scan on "*SELECT* 1"  (cost=0.00..139.24 rows=5462 width=6)
                                ->  Seq Scan on film_actor  (cost=0.00..84.62 rows=5462 width=2)  

SQL Server

SQL Server shines, like DB2:

Joining a provably empty set (IS NULL predicate):

  |--Constant Scan

Joining a provably empty set (INTERSECT):

  |--Constant Scan

Semi joining a provably empty set (IS NULL predicate):

  |--Constant Scan

Semi joining a provably empty set (INTERSECT):

  |--Constant Scan

Summary

Database JOIN / NULL JOIN / INTERSECT SEMI JOIN / NULL SEMI JOIN / INTERSECT
DB2 LUW 10.5 Yep Yep Yep Yep
MySQL 8.0.2 Yep Not supported Yep Not supported
Oracle 12.2.0.1 Yep Nope Yep Nope
PostgreSQL 9.6 Nope Nope Nope Nope
SQL Server 2014 Yep Yep Yep Yep

On a side note, this could be done in thousands of other ways. Feel free to comment with your own ideas on how to create “provably empty sets” to see if this is optimised by any of the databases.

8. CHECK Constraints

Oh, this is cool! Our Sakila database has a CHECK constraint on the FILM.RATING table:

CREATE TABLE film (
  ..
  RATING varchar(10) DEFAULT 'G',
  ..
  CONSTRAINT check_special_rating 
    CHECK (rating IN ('G','PG','PG-13','R','NC-17')),
  ..
);

Seriously, use CHECK constraints for data integrity. The cost of adding them is super low – much less than other constraints like PRIMARY, UNIQUE, and FOREIGN KEY constraints, as the do not profit from an index to enforce them, so you get them almost for “free”.

But there’s also an interesting optimisation aspect here! Check out these queries:

Impossible predicate

We’ve seen impossible predicates before, even with NOT NULL constraints (which are special types of CHECK constraints, in fact), but this is even more powerful:

SELECT *
FROM film
WHERE rating = 'N/A';

There can be no such film, because the CHECK constraint prevents its insertion (or update). This should again be transformed into a NOOP. Now, what about this?

CREATE INDEX idx_film_rating ON film (rating);

SELECT count(*)
FROM film
WHERE rating NOT IN ('G','PG','PG-13','R');

With the above index, we should probably simply run a quick index scan to count all the films of rating = ‘NC-17’, because that’s the only remaining rating. So the query should be rewritten to this:

SELECT count(*)
FROM film
WHERE rating = 'NC-17';

It should be, regardless of the index, because comparing the column with a single value is faster than comparing it with 4 values.

So, which database can do these things?

DB2

Impossible predicate (rating = ‘N/A’)

Cool!

Explain Plan                       
-----------------------------------
ID | Operation      |   Rows | Cost
 1 | RETURN         |        |    0
 2 |  TBSCAN GENROW | 0 of 0 |    0
                                   
Predicate Information              
 2 - RESID (1 = 0)                 

Inverse predicate (rating = ‘NC-17’)

Nope…

Explain Plan                                                
------------------------------------------------------------
ID | Operation                |                  Rows | Cost
 1 | RETURN                   |                       |   34
 2 |  GRPBY (COMPLETE)        |    1 of 210 (   .48%) |   34
 3 |   IXSCAN IDX_FILM_RATING | 210 of 1000 ( 21.00%) |   34
                                                            
Predicate Information                                       
 3 - SARG  NOT(Q1.RATING IN ('G', 'PG', 'PG-13', 'R'))      

While the index is used on ID=3 and while the cardinalities are correct, it is scanned entirely, as we do not have a range predicate but a “SARG” predicate. For more details, see Markus Winand’s overview here.

We can also show this by manually inverting the predicate to get:

Explain Plan                                                
------------------------------------------------------------
ID | Operation                |                  Rows | Cost
 1 | RETURN                   |                       |    7
 2 |  GRPBY (COMPLETE)        |    1 of 210 (   .48%) |    7
 3 |   IXSCAN IDX_FILM_RATING | 210 of 1000 ( 21.00%) |    7
                                                            
Predicate Information                                       
 3 - START (Q1.RATING = 'NC-17')                            
      STOP (Q1.RATING = 'NC-17')                            

Now, we’re getting the desired range predicate

MySQL

MySQL supports the CHECK constraint syntax but doesn’t enforce it for whatever reason. Try this:

CREATE TABLE x (a INT CHECK (a != 0));
INSERT INTO x VALUES (0);
SELECT * FROM x;

You’ll get:

A
-
0

Zero points for MySQL (really, why not just support CHECK constraints?)

Oracle

Impossible predicate (rating = ‘N/A’)

--------------------------------------------------------------
| Id  | Operation          | Name | Starts | E-Rows | A-Rows |
--------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |      1 |        |      0 |
|*  1 |  FILTER            |      |      1 |        |      0 |
|*  2 |   TABLE ACCESS FULL| FILM |      0 |     89 |      0 |
--------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - filter(NULL IS NOT NULL)
   2 - filter("RATING"='N/A')

Again, the super confusing NULL IS NOT NULL filter that cuts off the FULL TABLE SCAN, which might as well be removed entirely from the plan. But at least it works!

Inverse predicate (rating = ‘NC-17’)

Ooops:

----------------------------------------------------------------------------
| Id  | Operation             | Name            | Starts | E-Rows | A-Rows |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |                 |      1 |        |      1 |
|   1 |  SORT AGGREGATE       |                 |      1 |      1 |      1 |
|*  2 |   INDEX FAST FULL SCAN| IDX_FILM_RATING |      1 |    415 |    210 |
----------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - filter((RATING'PG-13' AND RATING'R' AND RATING'PG' AND RATING'G'))

The predicate could not be inversed, we get a much off cardinality estimate, we get an INDEX FAST FULL SCAN, instead of an INDEX RANGE SCAN, and a filter predicate rather than an access predicate. Here’s what we should have gotten, e.g. when manually inverting the predicate:

------------------------------------------------------------------------
| Id  | Operation         | Name            | Starts | E-Rows | A-Rows |
------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |                 |      1 |        |      1 |
|   1 |  SORT AGGREGATE   |                 |      1 |      1 |      1 |
|*  2 |   INDEX RANGE SCAN| IDX_FILM_RATING |      1 |    210 |    210 |
------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - access("RATING"='NC-17')

Bummer!

PostgreSQL

Note that the Sakila database in its PostgreSQL version uses an ENUM type instead of a CHECK constraint on the RATING column. I’ve duplicated the table to use a CHECK constraint instead.

Impossible predicate (rating = ‘N/A’)

Doesn’t work:

QUERY PLAN                                            
------------------------------------------------------
Seq Scan on film2  (cost=0.00..67.50 rows=1 width=385)
  Filter: ((rating)::text = 'N/A'::text)              

Inverse predicate (rating = ‘NC-17’)

Also nope:

QUERY PLAN                                                        
------------------------------------------------------------------
Aggregate  (cost=70.53..70.54 rows=1 width=8)                     
  ->  Seq Scan on film2  (cost=0.00..70.00 rows=210 width=0)      
        Filter: ((rating)::text  ALL ('{G,PG,PG-13,R}'::text[]))

Too bad!

NOTE: As was kindly pointed out by David Rowley in the comments, this feature can be opted in by specifying:

SET constraint_exclusion TO on;

SQL Server

Impossible predicate (rating = ‘N/A’)

Yes!

  |--Constant Scan

Inverse predicate (rating = ‘NC-17’)

Also yes!

  |--Compute Scalar
       |--Stream Aggregate
            |--Index Seek(OBJECT:([idx_film_rating]), SEEK:([rating]='NC-17'))

Summary

Database Impossible predicate Inverse predicate
DB2 LUW 10.5 Yep Nope
MySQL 8.0.2 Not supported Not supported
Oracle 12.2.0.1 Yep Nope
PostgreSQL 9.6 Nope Nope
SQL Server 2014 Yep Yep

9. Unneeded Self JOIN

When your queries get more complex, it might well happen that you’re going to self JOIN a table based on its primary key. Trust me, this is common practice when you build complex views and JOIN them to each other, so a database noticing this is a crucial step in optimising complex SQL. I won’t show a complex example, but a simple one, e.g.

SELECT a1.first_name, a1.last_name
FROM actor a1
JOIN actor a2 ON a1.actor_id = a2.actor_id;

This could be considered a special case of JOIN elimination as we don’t really need the JOIN of A2, we can do everything with A1 only. Now, INNER JOIN elimination normally works in the presence of a FOREIGN KEY only, which we don’t have here. But because of the PRIMARY KEY on ACTOR_ID, we can prove that in fact A1 = A2. In a way, this is transitive closure all over again.

We can take this one step further and use columns from both A1 and A2:

SELECT a1.first_name, a2.last_name
FROM actor a1
JOIN actor a2 ON a1.actor_id = a2.actor_id;

In the classic JOIN elimination case, we could no longer eliminate the JOIN because we’re projecting from both tables. But since we’ve already proven that A1 = A2, we can use them interchangeably, so the expectation is for this query to be transformed into:

SELECT first_name, last_name
FROM actor;

Who can do this?

DB2

Projecting from A1 only

Yes:

Explain Plan                                    
------------------------------------------------
ID | Operation     |                 Rows | Cost
 1 | RETURN        |                      |   20
 2 |  TBSCAN ACTOR | 200 of 200 (100.00%) |   20

Projecting from A1 and A2

… and yes:

Explain Plan                                    
------------------------------------------------
ID | Operation     |                 Rows | Cost
 1 | RETURN        |                      |   20
 2 |  TBSCAN ACTOR | 200 of 200 (100.00%) |   20

MySQL

Projecting from A1 only

Nope

ID  TABLE  REF          EXTRA
-----------------------------------
1   a1
1   a2     a1.actor_id  Using index

Projecting from A1 and A2

… and nope

ID  TABLE  REF          EXTRA
-----------------------------------
1   a1
1   a2     a1.actor_id  

That’s disappointing…

Oracle

Projecting from A1 only

Yes

--------------------------------------------
| Id  | Operation         | Name  | E-Rows |
--------------------------------------------
|   0 | SELECT STATEMENT  |       |        |
|   1 |  TABLE ACCESS FULL| ACTOR |    200 |
--------------------------------------------

Projecting from A1 and A2

And yes

--------------------------------------------
| Id  | Operation         | Name  | E-Rows |
--------------------------------------------
|   0 | SELECT STATEMENT  |       |        |
|   1 |  TABLE ACCESS FULL| ACTOR |    200 |
--------------------------------------------

PostgreSQL

Projecting from A1 only

Nope:

QUERY PLAN                                                          
--------------------------------------------------------------------
Hash Join  (cost=6.50..13.25 rows=200 width=13)                     
  Hash Cond: (a1.actor_id = a2.actor_id)                            
  ->  Seq Scan on actor a1  (cost=0.00..4.00 rows=200 width=17)     
  ->  Hash  (cost=4.00..4.00 rows=200 width=4)                      
        ->  Seq Scan on actor a2  (cost=0.00..4.00 rows=200 width=4)

Projecting from A1 and A2

And nope:

QUERY PLAN                                                           
---------------------------------------------------------------------
Hash Join  (cost=6.50..13.25 rows=200 width=13)                      
  Hash Cond: (a1.actor_id = a2.actor_id)                             
  ->  Seq Scan on actor a1  (cost=0.00..4.00 rows=200 width=10)      
  ->  Hash  (cost=4.00..4.00 rows=200 width=11)                      
        ->  Seq Scan on actor a2  (cost=0.00..4.00 rows=200 width=11)

SQL Server

Projecting from A1 only

Surprisingly, no! (But remember, this is SQL Server 2014, maybe this got fixed in a more recent version. I should definitely upgrade!)

  |--Merge Join(Inner Join, MERGE:([a2].[actor_id])=([a1].[actor_id]))
       |--Index Scan(OBJECT:([a2]))
       |--Sort(ORDER BY:([a1].[actor_id] ASC))
            |--Table Scan(OBJECT:([a1]))

Projecting from A1 and A2

Also no, and even with a different, worse plan:

  |--Hash Match(Inner Join, HASH:([a1].[actor_id])=([a2].[actor_id]))
       |--Table Scan(OBJECT:([sakila].[dbo].[actor] AS [a1]))
       |--Table Scan(OBJECT:([sakila].[dbo].[actor] AS [a2]))

Summary

I would have frankly expected this to work on all databases, but I was proven very wrong, which is a shame. Along with JOIN elimination, this is one of the most crucial optimisations to enable building huge SQL queries from reusable parts, such as views and table valued functions. Unfortunately, this is not supported 3/5 of the most popular databases.

Database Self-join elimination,
single table projection
Self-join elimination,
complete projection
DB2 LUW 10.5 Yep Yep
MySQL 8.0.2 Nope Nope
Oracle 12.2.0.1 Yep Yep
PostgreSQL 9.6 Nope Nope
SQL Server 2014 Nope Nope

10. Predicate Pushdown

This optimisation doesn’t belong here 100%, because it is not entirely true to assume this transformation is not cost based. But since I cannot think of a single obvious reason why an optimiser should not push down predicates into derived tables, I’m listing this here along with the other, non-cost-based optimisations.

Consider this query:

SELECT *
FROM (
  SELECT *
  FROM actor
) a
WHERE a.actor_id = 1;

The derived table has absolutely no value in this query and it should be eliminated as well, by unnesting it. But let’s ignore that for a moment.

We’d expect the database to perform this query instead:

SELECT *
FROM (
  SELECT *
  FROM actor
  WHERE actor_id = 1
) a;

And then again, possibly, eliminate the outer query.

A more sophisticated example would be when using UNION:

SELECT *
FROM (
  SELECT first_name, last_name, 'actor' type
  FROM actor
  UNION ALL
  SELECT first_name, last_name, 'customer' type
  FROM customer
) people
WHERE people.last_name = 'DAVIS';

The result of this query is:

FIRST_NAME  LAST_NAME  TYPE
----------------------------
JENNIFER    DAVIS      actor
SUSAN       DAVIS      actor
SUSAN       DAVIS      actor
JENNIFER    DAVIS      customer

Now, we’d love the database optimiser to run this statement instead:

SELECT *
FROM (
  SELECT first_name, last_name, 'actor' type
  FROM actor
  WHERE last_name = 'DAVIS'
  UNION ALL
  SELECT first_name, last_name, 'customer' type
  FROM customer
  WHERE last_name = 'DAVIS'
) people;

I.e. pushing down the predicate into the derived table, and from there on into the two UNION ALL subqueries, because after all, we have indexes on both ACTOR.LAST_NAME and CUSTOMER.LAST_NAME columns.

Again, this transformation might be motivated based on costs in most databases, but I still think it’s a no-brainer to do anyway, because it’s almost always better to reduce the number of processed tuples as early as possible in any algorithm. If you know a case where this transformation is a bad idea, please comment! I’d be very curious.

So, which databases can do this? (And please, this is so basic, yet important, let the answer be: all)

DB2

Simple derived table

Yes

Explain Plan                                      
--------------------------------------------------
ID | Operation         |               Rows | Cost
 1 | RETURN            |                    |    6
 2 |  FETCH ACTOR      |   1 of 1 (100.00%) |    6
 3 |   IXSCAN PK_ACTOR | 1 of 200 (   .50%) |    0
                                                  
Predicate Information                             
 3 - START (Q1.ACTOR_ID = 1)                      
      STOP (Q1.ACTOR_ID = 1)                      

UNION derived table

Yes, again:

Explain Plan                                                     
-----------------------------------------------------------------
ID | Operation                        |               Rows | Cost
 1 | RETURN                           |                    |   20
 2 |  UNION                           |             2 of 1 |   20
 3 |   FETCH CUSTOMER                 |   1 of 1 (100.00%) |   13
 4 |    IXSCAN IDX_CUSTOMER_LAST_NAME | 1 of 599 (   .17%) |    6
 5 |   FETCH ACTOR                    |   1 of 1 (100.00%) |    6
 6 |    IXSCAN IDX_ACTOR_LAST_NAME    | 1 of 200 (   .50%) |    0
                                                                 
Predicate Information                                            
 4 - START (Q1.LAST_NAME = 'DAVIS')                              
      STOP (Q1.LAST_NAME = 'DAVIS')                              
 6 - START (Q3.LAST_NAME = 'DAVIS')                              
      STOP (Q3.LAST_NAME = 'DAVIS')                              

Also, in both cases, the derived table (view) was removed from the plan as it is not really necessary.

MySQL

Simple derived table

Yes

ID  TABLE  TYPE   KEY      REF    EXTRA
---------------------------------------
1   actor  const  PRIMARY  const

The usual PRIMARY KEY access by a constant value is applied.

UNION derived table

Oops, nope

ID  SELECT_TYPE  TABLE       TYPE  KEY          REF    ROWS  EXTRA
------------------------------------------------------------------
1   PRIMARY        ref   	const  10
2   DERIVED      actor       ALL                       200
3   UNION        customer    ALL                       599

The manual transformation would yield:

ID  SELECT_TYPE  TABLE       TYPE  KEY                  REF    ROWS  EXTRA
--------------------------------------------------------------------------
1   PRIMARY        ALL                               5
2   DERIVED      actor       ref   idx_actor_last_name  const  3
3   UNION        customer    ref   idx_last_name        const  1

That’s really a problem if you want to nest complex queries in MySQL!

Oracle

Simple derived table

Yes, works

---------------------------------------------------------------------------
| Id  | Operation                   | Name     | Starts | E-Rows | A-Rows |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |          |      1 |        |      1 |
|   1 |  TABLE ACCESS BY INDEX ROWID| ACTOR    |      1 |      1 |      1 |
|*  2 |   INDEX UNIQUE SCAN         | PK_ACTOR |      1 |      1 |      1 |
---------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   2 - access("ACTOR"."ACTOR_ID"=1)

The derived table has been unnested, too.

UNION derived table

Works as well:

---------------------------------------------------------------------------------
| Id  | Operation                             | Name                   | E-Rows |
---------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                      |                        |        |
|   1 |  VIEW                                 |                        |      4 |
|   2 |   UNION-ALL                           |                        |        |
|   3 |    TABLE ACCESS BY INDEX ROWID BATCHED| ACTOR                  |      3 |
|*  4 |     INDEX RANGE SCAN                  | IDX_ACTOR_LAST_NAME    |      3 |
|   5 |    TABLE ACCESS BY INDEX ROWID BATCHED| CUSTOMER               |      1 |
|*  6 |     INDEX RANGE SCAN                  | IDX_CUSTOMER_LAST_NAME |      1 |
---------------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   4 - access("LAST_NAME"='DAVIS')
   6 - access("LAST_NAME"='DAVIS')

However, without unnesting the derived table. The Id=1 “VIEW” indicates that it’s still there. This isn’t a problem in this case, just perhaps a bit cosmetic overhead.

PostgreSQL

Simple derived table

Yes, it works:

QUERY PLAN                                          
----------------------------------------------------
Seq Scan on actor  (cost=0.00..4.50 rows=1 width=25)
  Filter: (actor_id = 1)                            

Note, interestingly, PostgreSQL sometimes doesn’t even use the PRIMARY KEY for a single row lookup but scans the entire table. In this case, 200 rows x 25 bytes per row (“width”) fits in a single block, so why bother reading the index anyway, generating more I/O for this small table access?

UNION derived table

Yes, this works as well:

QUERY PLAN                                                                         
-----------------------------------------------------------------------------------
Append  (cost=0.00..12.83 rows=4 width=45)                                         
  ->  Seq Scan on actor  (cost=0.00..4.50 rows=3 width=45)                         
        Filter: ((last_name)::text = 'DAVIS'::text)                                
  ->  Index Scan using idx_last_name on customer  (cost=0.28..8.29 rows=1 width=45)
        Index Cond: ((last_name)::text = 'DAVIS'::text)                            

Again, the index on ACTOR.LAST_NAME is not used, but the one on CUSTOMER.LAST_NAME is, as the CUSTOMER table is quite larger.

SQL Server

Simple derived table

Yep, works

  |--Nested Loops(Inner Join)
       |--Index Seek(SEEK:([actor_id]=(1)))
       |--RID Lookup(OBJECT:([actor]))

UNION derived table

Works as well.

  |--Concatenation
       |--Compute Scalar(DEFINE:([Expr1003]='actor'))
       |    |--Nested Loops(Inner Join)
       |         |--Index Seek(SEEK:([actor].[last_name]='DAVIS'))
       |         |--RID Lookup(OBJECT:([actor]))
       |--Compute Scalar(DEFINE:([Expr1007]='customer'))
            |--Nested Loops(Inner Join)
                 |--Index Seek(SEEK:([customer].[last_name]='DAVIS'))
                 |--RID Lookup(OBJECT:([customer]))

Summary

My hopes were scattered. MySQL 8.0.2 doesn’t support this simple optimisation completely yet. All others do, however:

Database Simple derived table pushdown UNION derived table pushdown
DB2 LUW 10.5 Yep Yep
MySQL 8.0.2 Yep Nope
Oracle 12.2.0.1 Yep Yep
PostgreSQL 9.6 Yep Yep
SQL Server 2014 Yep Yep

Conclusion

The list presented here is far from complete. There are many more of these simple SQL transformations that are (or should be) a no-brainer for a database to implement, even before the cost-based optimiser kicks in. They remove what I call unnecessary, optional work (as opposed to unnecessary, mandatory work). They are essential tools for:

  • Preventing silly mistakes from affecting SQL performance. Everyone makes mistakes, and as projects grow larger and SQL queries grow more complex, these mistakes might accumulate, yet hopefully, without effect
  • Enabling the reuse of complex building blocks, such as views and table-valued functions, which can be inlined into parent SQL queries, transformed, and parts removed or rewritten

These features are essential for the second part. Without them, it is very difficult to build 4000 LOC SQL queries that still perform decently, based on a library of reusable SQL components.

Unfortunately for users of PostgreSQL and MySQL, these two popular Open Source databases are still much behind their commercial counterparts DB2, Oracle, and SQL Server – where DB2 fared best in this article, Oracle and SQL Server being roughly on par.

SQL is a wonderful language, because it is declarative and any statement can be rewritten to something simpler or more sophisticated, which performs much better than what the author has written. If you have liked this article, you may also like:

JOIN Elimination: An Essential Optimiser Feature for Advanced SQL Usage

The SQL language has one great advantage over procedural, object oriented, and “ordinary” functional programming languages. The fact that it is truly declarative (i.e. a 4GL / fourth generation programming language) means that a sophisticated optimiser can easily transform one SQL expression into another, equivalent SQL expression, which might be faster to execute.

How does this work?

Expression Tree Equivalence

Here’s an introduction to equivalent expression trees from my SQL Masterclass: Let’s assume we want to evaluate the following expression:

A + (A - B)

Now in maths, it can be proven trivially that by the laws of associativity, the above expression is really the same as this one:

(A + A) - B

We didn’t really win anything yet, but we can equally trivially turn the above addition into a multiplication that can be proven to be exactly equivalent:

(2 * A) - B

Now, imagine that A is an extremely “expensive” value, e.g. a value that we have to fetch from the disk, or worse, from the network. The cost of accessing A is thus very high and if we can avoid one access to A by the above transformation, then the resulting expression is much faster to evaluate than the original one, even if mathematically speaking, it does not matter at all.

That’s what optimisers do all the time. They transform expressions into equivalent expressions which are faster to execute. And they constantly adapt, so if the DBA chooses to move A from a remote server to the local server, thus reducing the cost of access to A, perhaps, suddenly, the original plan will be better again, because of the cost of multiplication (just an example).

A SQL Example

An equally trivial SQL example from my SQL Masterclass shows that it really doesn’t matter mathematically if we run this query:

SELECT first_name, last_name
FROM customer
WHERE first_name = 'JAMIE'

Or this one:

SELECT *
FROM (
  SELECT first_name, last_name
  FROM customer
)
WHERE first_name = 'JAMIE'

With the SQL language, it may be a bit harder to see that these are exactly equivalent SQL statements, but if we translate the above queries to relational algebra, it may become more visible:

Selection before projection

… or WHERE before SELECT:

Projection then selection

… or SELECT before WHERE:

Don’t be fooled by relational algebra‘s term “selection”. It does not correspond to the SELECT clause, but to the WHERE clause!

We can prove (let’s leave the exercise to the reader), that both expressions are exactly equivalent, so optimisers can pick whichever they have a more efficient matching algorithm for:

  • Ordinary row stores will probably apply the selection first, before projecting, as the expensive operation is accessing rows and if we can filter rows early (e.g. through indexes) then the whole query is less expensive)
  • A column store might (just a hypothesis) apply the projection first, as the expensive operation is accessing the columns. We then might have to traverse the entire column anyway to filter out the rows

Let’s Talk About JOINs (and Their Elimination)

JOIN elimination is one of the most basic and yet most powerful SQL transformations, which is implemented by most modern databases in one way or another. It is so powerful, because we’re writing (potentially useless) JOINs all the time, when writing a bit more complex queries. See also our article about JOINs for a general overview.

Now, consider the following simplified schema, taken from the Sakila database:

CREATE TABLE address (
  address_id INT NOT NULL,
  address VARCHAR(50) NOT NULL,
  CONSTRAINT pk_address PRIMARY KEY (address_id)
);

CREATE TABLE customer (
  customer_id INT NOT NULL,
  first_name VARCHAR(45) NOT NULL,
  last_name VARCHAR(45) NOT NULL,
  address_id INT NOT NULL,
  CONSTRAINT pk_customer PRIMARY KEY  (customer_id),
  CONSTRAINT fk_customer_address FOREIGN KEY (address_id) 
    REFERENCES address(address_id)
);

Let’s ignore indexing and other useful features for this example.

INNER JOIN Elimination

The following query shows a common JOIN use-case, joining a parent table (ADDRESS) to a child table (CUSTOMER) in a to-one relationship:

SELECT c.*
FROM customer c
JOIN address a 
ON c.address_id = a.address_id

We intended to fetch all customers and their addresses. But observe: We project only columns from the CUSTOMER table and we don’t have any predicates at all, specifically not predicates using the ADDRESS table. So, we’re completely ignoring any contributions from the ADDRESS table. We never really needed the JOIN in the first place!

And in fact, the optimiser can prove this too, because of the FOREIGN KEY constraint on C.ADDRESS_ID, which guarantees that every CUSTOMER record has exactly one corresponding ADDRESS record. The JOIN does not duplicate, nor remove any CUSTOMER rows, so it is unneeded and thus eliminated (by some, not all databases, will list each database at the end of the article).

So, the database can rewrite the SQL statement to the following, equivalent SQL statement in the presence of said FOREIGN KEY:

SELECT *
FROM customer c

Now, quite obviously, this query will be faster than the previous one, if the entire JOIN can be avoided, and thus the entire access to the ADDRESS table. Neat, huh? Who would have thought that FOREIGN KEYs can be so useful in terms of performance.

The above works if there’s also a NOT NULL constraint on the FOREIGN KEY. If there isn’t, e.g. as in this query:

SELECT title
FROM film f
JOIN language l ON f.original_language_id = l.language_id

The JOIN can still be eliminated, but there needs to be a replacement NOT NULL predicate, as such:

SELECT title
FROM film
WHERE original_language_id IS NOT NULL

OUTER JOIN Elimination

A LEFT [ OUTER ] JOIN will JOIN the right table to the left table but keep rows from the left table if there is no match (again, an explanation of joins can be seen here). When we apply LEFT JOIN to the previous query…

SELECT c.*
FROM customer c
LEFT JOIN address a 
ON c.address_id = a.address_id

… then we’ll fetch all rows from CUSTOMER regardless if that customer has any ADDRESS. This is useful if the FOREIGN KEY is optional (nullable), or completely absent, e.g. through:

ALTER TABLE customer DROP CONSTRAINT fk_customer_address

OUTER JOIN is even easier to eliminate, as it doesn’t require any FOREIGN KEY constraint for the database to prove that it is unneeded. A UNIQUE constraint on the parent table (here: ADDRESS.ADDRESS_ID) is sufficient to show that for every CUSTOMER there can be at most one ADDRESS, so the LEFT JOIN won’t duplicate any CUSTOMER rows (Unlike INNER JOIN, OUTER JOIN never remove rows).

Hence, the above query can again be rewritten to the more optimal:

SELECT *
FROM customer c

OUTER JOIN Elimination with DISTINCT

Another interesting case of OUTER JOIN elimination is the following one, which unfortunately didn’t work on Oracle for a customer of ours, recently, in a complex query that ran rogue. Let’s look at some other tables of the Sakila database, which expose a to-many relationship:

CREATE TABLE actor (
  actor_id numeric NOT NULL ,
  first_name VARCHAR(45) NOT NULL,
  last_name VARCHAR(45) NOT NULL,
  CONSTRAINT pk_actor PRIMARY KEY (actor_id)
);

CREATE TABLE film (
  film_id int NOT NULL,
  title VARCHAR(255) NOT NULL,
  CONSTRAINT pk_film PRIMARY KEY (film_id)
);

CREATE TABLE film_actor (
  actor_id INT NOT NULL,
  film_id  INT NOT NULL,
  CONSTRAINT pk_film_actor PRIMARY KEY (actor_id, film_id),
  CONSTRAINT fk_film_actor_actor FOREIGN KEY (actor_id)
    REFERENCES actor (actor_id),
  CONSTRAINT fk_film_actor_film FOREIGN KEY (film_id)
    REFERENCES film (film_id)
);

Now, consider this query:

SELECT DISTINCT first_name, last_name
FROM actor a
LEFT JOIN film_actor fa ON a.actor_id = fa.actor_id

We’re looking for all actors and their films, but then we project only distinct actors. Again, the JOIN to FILM_ACTOR doesn’t contribute anything to the result, but because we’re joining a to-many relationship here (from parent table ACTOR to child table FILM_ACTOR), the JOIN is producing duplicate rows. Without DISTINCT, we’d get something like:

FIRST_NAME   LAST_NAME
----------------------
...
PENELOPE     GUINESS
PENELOPE     GUINESS
PENELOPE     GUINESS
NICK         WAHLBERG
NICK         WAHLBERG
...

But thanks to the DISTINCT keyword, the result is (provably) no different from the result of this much simpler query:

SELECT DISTINCT first_name, last_name
FROM actor a

(Note, DISTINCT cannot be eliminated, unless we already have a UNIQUE constraint on (FIRST_NAME, LAST_NAME)).

Why not Just Refactor the SQL Manually?

Of course, all of this shouldn’t be needed if our SQL were perfect. In the above trivial examples, the SQL can (and should) be re-written manually to improve quality. But note that:

  • Developers make mistakes, and those mistakes may be very subtle when queries get more complex. I’ll show an example below.
  • The presence of this feature actually encourages writing more complex SQL, especially when using reusable views. I’ll show another example below.
  • Finally, I’ve previously advocated avoiding needless, mandatory work, like SELECT *. Such work is mandatory because the optimiser cannot prove its needlessness. In the case of these JOINs, the optimiser can prove the needlessness, so the work is no longer mandatory. It can be eliminated.

Here are some complex examples as promised, where this optimiser feature really shines:

Subtle Mistakes

Let’s consider the following query (in PostgreSQL syntax):

SELECT c.name, count(*)
FROM actor a
JOIN film_actor fa USING (actor_id)
JOIN film f USING (film_id)
JOIN film_category fc USING (film_id)
JOIN category c USING (category_id)
WHERE actor_id = 1
GROUP BY c.name
ORDER BY count(*) DESC

What does it do? For ACTOR_ID = 1 (Penelope Guiness), we’re looking for all the different film categories she played in, and the number of films per category. This is easier to understand when we look at the result:

NAME         COUNT
Horror       3
Family       2
New          2
Classics     2
Games        2
Music        1
Sci-Fi       1
Animation    1
Sports       1
Children     1
Comedy       1
Documentary  1
Foreign      1

Now, can you spot the unneeded JOINs? In fact, we never needed ACTOR, nor did we need FILM

SELECT c.name, count(*)
FROM film_actor fa
JOIN film_category fc USING (film_id)
JOIN category c USING (category_id)
WHERE actor_id = 1
GROUP BY c.name
ORDER BY count(*) DESC

Cool, eh? The JOINs can be eliminated (again, in some databases, see below) and our “mistake” is no longer relevant to the query. The mistake could have also snuck (or sneaked?) in from a previous query version, which may have looked like this, projecting also the actor information and the list of films per category, in case of which the additional JOIN are needed:

SELECT 
  c.name, count(*), 
  a.first_name, a.last_name, 
  array_agg(f.title ORDER BY f.title)
FROM actor a
JOIN film_actor fa USING (actor_id)
JOIN film f USING (film_id)
JOIN film_category fc USING (film_id)
JOIN category c USING (category_id)
WHERE actor_id = 1
GROUP BY c.name, a.first_name, a.last_name
ORDER BY count(*) DESC

The result being:

NAME         COUNT  FIRST_NAME  LAST_NAME  FILMS
Horror       3      PENELOPE    GUINESS    {"ELEPHANT TROJAN","LADY STAGE","RULES HUMAN"}
Family       2      PENELOPE    GUINESS    {"KING EVOLUTION","SPLASH GUMP"}
New          2      PENELOPE    GUINESS    {"ANGELS LIFE","OKLAHOMA JUMANJI"}
Classics     2      PENELOPE    GUINESS    {"COLOR PHILADELPHIA","WESTWARD SEABISCUIT"}
Games        2      PENELOPE    GUINESS    {"BULWORTH COMMANDMENTS","HUMAN GRAFFITI"}
Music        1      PENELOPE    GUINESS    {"WIZARD COLDBLOODED"}
Sci-Fi       1      PENELOPE    GUINESS    {"CHEAPER CLYDE"}
Animation    1      PENELOPE    GUINESS    {"ANACONDA CONFESSIONS"}
Sports       1      PENELOPE    GUINESS    {"GLEAMING JAWBREAKER"}
Children     1      PENELOPE    GUINESS    {"LANGUAGE COWBOY"}
Comedy       1      PENELOPE    GUINESS    {"VERTIGO NORTHWEST"}
Documentary  1      PENELOPE    GUINESS    {"ACADEMY DINOSAUR"}
Foreign      1      PENELOPE    GUINESS    {"MULHOLLAND BEAST"}

As you can see, this optimisation can be very useful on your legacy SQL, because if we maintain a complex query, we might not always be able to see all the JOINs that are really needed.

Reusable Views

Sometimes, we simply add additional JOINs for convenience, when building complex queries from simpler ones, e.g. by using views (which is a completely underrated RDBMS feature! You should all write more views).

Consider this view:

CREATE VIEW v_customer AS
SELECT 
  c.first_name, c.last_name, 
  a.address, ci.city, co.country
FROM customer c
JOIN address a USING (address_id)
JOIN city ci USING (city_id)
JOIN country co USING (country_id)

It’s not unlikely that we will write a view like this, simply because we’re incredibly bored to constantly join all these tables all the time. Every time we do something with customers and addresses, we need the CITY and COUNTRY table as well.

From now on (with this view), we can simply select from the view and “forget” about how it came to be. Now, let’s consider we completely forget about the underlying table, because the view was so useful all the time. We could think about doing this:

SELECT first_name, last_name
FROM v_customer

What do you think will happen? Exactly. JOIN elimination. A view isn’t really anything special, just a “macro” of some stored SQL (beware of some databases, where this isn’t always the case, e.g. MySQL, which Bill Karwin was kind enough to hint me at). So the above statement will be transformed into:

SELECT first_name, last_name
FROM (
  SELECT 
    c.first_name, c.last_name, 
    a.address, ci.city, co.country
  FROM customer c
  JOIN address a USING (address_id)
  JOIN city ci USING (city_id)
  JOIN country co USING (country_id)
) v_customer

… which can be transformed into this (we don’t need all columns in the nested select):

SELECT first_name, last_name
FROM (
  SELECT 
    c.first_name, c.last_name
  FROM customer c
  JOIN address a USING (address_id)
  JOIN city ci USING (city_id)
  JOIN country co USING (country_id)
) v_customer

… which can be transformed into this (JOINs can be eliminated):

SELECT first_name, last_name
FROM (
  SELECT 
    c.first_name, c.last_name
  FROM customer c
) v_customer

… and finally (the subquery is not useful):

SELECT first_name, last_name
FROM customer

The view is even very useful for this particular query, thanks to JOIN elimination!

Note, the SQL transformations exposed above are simply educational. Actual optimisers may perform transformations in an entirely differently, or in a different order. This is just to show what’s possible, and what kind of stuff is being done.

Cool, So Can My Database Do It?

Perhaps! Let’s look at the three different types of JOIN elimination in the context of these databases:

  • DB2 LUW 10.5
  • MySQL 8.0.2
  • Oracle 12.2.0.1
  • PostgreSQL 9.6
  • SQL Server 2014

INNER JOIN Elimination

Remember, this depends on the presence (and usefulness) of a FOREIGN KEY constraint. The SQL statement we’re using here is:

SELECT first_name, last_name
FROM customer c
JOIN address a ON c.address_id = a.address_id

We’re hoping to get:

SELECT first_name, last_name
FROM customer c

DB2 LUW

The following execution plan (created with Markus Winand’s cool utility) shows that this works in DB2, there’s no access to the ADDRESS table:

Explain Plan                                                           |
-----------------------------------------------------------------------|
ID | Operation                           |                 Rows | Cost |
 1 | RETURN                              |                      |   61 |
 2 |  FETCH CUSTOMER                     | 599 of 599 (100.00%) |   61 |
 3 |   IXSCAN IDX_CUSTOMER_FK_ADDRESS_ID | 599 of 599 (100.00%) |   20 |

MySQL

MySQL 8, apart from finally introducing CTE and window functions (yay), has a lot of new optimiser features, read Morgan Tocker’s useful optimiser guide for details. Unfortunately, INNER JOIN elimination is not implemented:

ID  TABLE  TYPE    REF                  ROWS   EXTRA
1   c      ALL                          599    
1   a      eq_ref  sakila.c.address_id  1      Using index

Not only is the JOIN executed, but it is executed using a nested loop with 599 index lookups, as MySQL still only supports NESTED LOOP JOINs, not HASH JOINs.

Bummer.

Oracle

No problem at all for Oracle:

------------------------------------------------------------------------------
| Id  | Operation         | Name     | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |          |   599 | 28752 |     5   (0)| 00:00:01 |
|   1 |  TABLE ACCESS FULL| CUSTOMER |   599 | 28752 |     5   (0)| 00:00:01 |
------------------------------------------------------------------------------

… the JOIN is eliminated as expected.

PostgreSQL

Unfortunately, PostgreSQL cannot eliminate INNER JOIN:

Hash Join  (cost=19.57..42.79 rows=599 width=13)
  Hash Cond: (c.address_id = a.address_id)
  ->  Seq Scan on customer c  (cost=0.00..14.99 rows=599 width=15)
  ->  Hash  (cost=12.03..12.03 rows=603 width=4)
        ->  Seq Scan on address a  (cost=0.00..12.03 rows=603 width=4)

Not as bad as in MySQL, though, as PostgreSQL chose to use a HASH JOIN to combine the two tables.

SQL Server

No problemo for SQL Server, the ADDRESS table access is gone!

  |--Table Scan(OBJECT:([sakila].[dbo].[customer] AS [c]))

Notice, however, that SQL Server can only eliminate INNER JOIN on NOT NULL FOREIGN KEYs!

Excellent. What about…

OUTER JOIN Elimination

This one is a bit easier to prove for the database, remember? We don’t rely on any FOREIGN KEY anymore. A UNIQUE key in the parent table is sufficient to eliminate an OUTER JOIN. We can safely expect that if the INNER JOIN could be eliminated (DB2, Oracle, SQL Server), then an OUTER JOIN can be eliminated, too.

Here’s the query:

SELECT first_name, last_name
FROM customer c
LEFT JOIN address a ON c.address_id = a.address_id

And the outcome:

DB2 LUW

Good

Explain Plan                                                           |
-----------------------------------------------------------------------|
ID | Operation                           |                 Rows | Cost |
 1 | RETURN                              |                      |   61 |
 2 |  FETCH CUSTOMER                     | 599 of 599 (100.00%) |   61 |
 3 |   IXSCAN IDX_CUSTOMER_FK_ADDRESS_ID | 599 of 599 (100.00%) |   20 |

MySQL

Still nope:

ID  TABLE  TYPE    REF                  ROWS   EXTRA
1   c      ALL                          599    
1   a      eq_ref  sakila.c.address_id  1      Using index

Oracle

Perfect:

------------------------------------------------------------------------------
| Id  | Operation         | Name     | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |          |   599 | 28752 |     5   (0)| 00:00:01 |
|   1 |  TABLE ACCESS FULL| CUSTOMER |   599 | 28752 |     5   (0)| 00:00:01 |
------------------------------------------------------------------------------

PostgreSQL

Unlike INNER JOIN elimination, this works. Great!

Seq Scan on customer c  (cost=0.00..14.99 rows=599 width=13)

SQL Server

As expected, good:

  |--Table Scan(OBJECT:([sakila].[dbo].[customer] AS [c]))

Finally…

OUTER JOIN Elimination with DISTINCT

Remember, the query here navigates a to-many relationship, producing duplicate records of the parent table, but then removes all those duplicates again by

  • Ignoring contributions from the child table
  • Removing duplicates with DISTINCT

It’s easy to prove that this:

SELECT DISTINCT first_name, last_name
FROM actor a
LEFT JOIN film_actor fa ON a.actor_id = fa.actor_id

Is equivalent to this:

SELECT DISTINCT first_name, last_name
FROM actor a

Remember also, this only works with OUTER JOIN, not with INNER JOIN, as the latter might remove rows, so we have to execute it to see if it does.

DB2 LUW

Cool, this actually works!

Explain Plan                                                          |
----------------------------------------------------------------------|
ID | Operation        |                 Rows | Cost                   |
 1 | RETURN           |                      |   20                   |
 2 |  TBSCAN          | 200 of 200 (100.00%) |   20                   |
 3 |   SORT (UNIQUE)  | 200 of 200 (100.00%) |   20                   |
 4 |    TBSCAN ACTOR  | 200 of 200 (100.00%) |   20                   |

There’s no access to the FILM_ACTOR table, nor to its indexes. Very nice.

MySQL

As this is a more sophisticated transformation than the previous ones, we don’t have high hopes here.

ID  TABLE  TYPE    REF                  ROWS   EXTRA
1   a      ALL                          200    Using temporary
1   fa     ref     sakila.a.actor_id    27     Using index; Distinct

This has become a rather expensive query, again because of the lack of HASH JOIN support in MySQL!

Oracle

I’m very surprised to see that Oracle doesn’t support this optimisation, we’re executing the full query:

---------------------------------------------------------------
| Id  | Operation           | Name                    | Rows  |
---------------------------------------------------------------
|   0 | SELECT STATEMENT    |                         |  5462 |
|   1 |  HASH UNIQUE        |                         |  5462 |
|   2 |   NESTED LOOPS OUTER|                         |  5462 |
|   3 |    TABLE ACCESS FULL| ACTOR                   |   200 |
|*  4 |    INDEX RANGE SCAN | IDX_FK_FILM_ACTOR_ACTOR |    27 |
---------------------------------------------------------------

Curiously, Oracle also chose a NESTED LOOP JOIN in this case, even if we could have loaded the entire index on the FILM_ACTOR table into memory and then HASH JOINed it to ACTOR. Note that the cardinality estimate of the resulting query is quite off, too, despite the DISTINCT operation. This can lead to significant effects in an upstream query, which selects from this query (e.g. if stored as a view) – which is what happened to our customer.

PostgreSQL

PostgreSQL also doesn’t support this elimination, but at least gets cardinality estimates much more accurately and chooses a HASH JOIN operation:

HashAggregate  (cost=193.53..194.81 rows=128 width=13)
  Group Key: a.first_name, a.last_name
  ->  Hash Right Join  (cost=6.50..166.22 rows=5462 width=13)
        Hash Cond: (fa.actor_id = a.actor_id)
        ->  Seq Scan on film_actor fa  (cost=0.00..84.62 rows=5462 width=2)
        ->  Hash  (cost=4.00..4.00 rows=200 width=17)
              ->  Seq Scan on actor a  (cost=0.00..4.00 rows=200 width=17)

SQL Server

The pleasant surprise came from SQL Server, which does support this optimisation too:

  |--Sort(DISTINCT ORDER BY:([a].[first_name] ASC, [a].[last_name] ASC))
       |--Table Scan(OBJECT:([sakila].[dbo].[actor] AS [a]))

As you can see, no access to any FILM_ACTOR related objects!

Summary

Here’s a summary of what databases can eliminate:

Database INNER JOIN:
to-one
INNER JOIN nullable:
to-one
OUTER JOIN:
to-one
OUTER JOIN DISTINCT:
to-many
DB2 LUW 10.5 Yep Yep Yep Yep
MySQL 8.0.2 Nope Nope Nope Nope
Oracle 12.2.0.1 Yep Yep Yep Nope
PostgreSQL 9.6 Nope Nope Yep Nope
SQL Server 2014 Yep Nope Yep Yep

Conclusion

JOIN elimination is a very simple to understand, yet incredibly powerful feature that modern databases support to help developers build and maintain complex SQL queries without worrying too much about performance side effects.

It is possible because SQL is a 4GL (fourth-generation programming language), i.e. a declarative language whose parsed expression trees can “easily” be transformed into equivalent, simpler, and faster to execute expression trees. This work is constantly done by the optimiser behind the scenes, often without you even noticing (see example where unnecessary ACTOR and FILM tables were removed).

Currenly, DB2 and SQL Server are the leaders here with Oracle being a close runner-up, at least in my investigation. There’s hope for PostgreSQL, and a bit less hope for MySQL right now. There are tons of other interesting SQL transformations, which I’ll blog about in future blog posts, which may make the difference in other kinds of complex queries.

If you were intrigued by this sort of functionality, do have a look at my most recent SQL talk, which helps developers understand the real value of SQL in the context of the optimiser: