EXPLAIN EXTENDED

From Stack Overflow:

Say I have the following data:

Name	Value
Small	10
Medium	100
Large	1000

Imagine that these represent the volumes of boxes.

I have some items that I want to put in the boxes, and I want the smallest box possible.

I need an SQL query that will:

1. Return the row with the smallest row greater than my query parameter
2. If there is no such row, then return the largest row

I’m on Oracle 11g, so any special Oracle goodness is OK.

There certainly is a special Oracle goodness, and I’ll cover it in this article.

Let’s create the sample table and fill it with 1,000,000 rows to illustrate the point:

Table creation details

DROP USER "20090424_lowest" CASCADE
/
CREATE USER "20090424_lowest" IDENTIFIED BY "20090424_lowest"
/
GRANT CREATE ANY TABLE TO "20090424_lowest"
/
GRANT UNLIMITED TABLESPACE TO "20090424_lowest"
/
ALTER SESSION SET CURRENT_SCHEMA="20090424_lowest"
/
CREATE TABLE t_orderer (
        id      NUMBER NOT NULL,
        value   NUMBER NOT NULL
)
/
ALTER TABLE t_orderer
ADD CONSTRAINT pk_orderer_id PRIMARY KEY (id)
/
CREATE INDEX ix_orderer_value ON t_orderer (value)
/
INSERT
INTO    t_orderer (id, value)
SELECT  level, level
FROM    dual
CONNECT BY
        level <= 1000000
/
COMMIT
/
BEGIN
        DBMS_STATS.gather_schema_stats('"20090424_lowest"');
END;
/

Now, what do we have here?

As we need to find the least row greater than a given value, it’s a good work for an INDEX SCAN along with a COUNT STOPKEY.

We can make it with ORDER BY and rownum = 1:

SELECT  *
FROM    (
        SELECT  *
        FROM    t_orderer
        WHERE   value > 314159
        ORDER BY
                value
        )
WHERE   rownum = 1

SELECT STATEMENT
 COUNT STOPKEY
  VIEW
   TABLE ACCESS BY INDEX ROWID, 20090424_lowest.T_ORDERER
    INDEX RANGE SCAN, 20090424_lowest.IX_ORDERER_VALUE

This, though, will not return anything if there are no rows with value greater than the parameter provided.

If it is the case, we’ll just need to select the row with a maximal value:

SELECT  *
FROM    t_orderer
WHERE   rownum = 1
ORDER BY
        value DESC

SELECT STATEMENT
 COUNT STOPKEY
  TABLE ACCESS BY INDEX ROWID, 20090424_lowest.T_ORDERER
   INDEX FULL SCAN DESCENDING, 20090424_lowest.IX_ORDERER_VALUE

As you can see, both these queries use the index on value and are virtually instant.

Now, we need to unite them.

Unfortunately, Oracle does not allow using ORDER BY inside a UNION ALL.

That’s why we’ll need to do the following:

1. Wrap these queries into inline views
2. UNION ALL these views
3. Wrap the result into a subquery
4. Select the first row from the UNION ALL

This will return the lowest value greater than a given parameter if the former exists; or the maximal value if it does not.

Here’s the result:

WITH    lowest AS
        (
        SELECT  *
        FROM    (
                SELECT  *
                FROM    t_orderer
                WHERE   value > 314159
                ORDER BY
                        value
                )
        WHERE   rownum = 1
        ),
        maximal AS (
        SELECT  *
        FROM    (
                SELECT  *
                FROM    t_orderer
                ORDER BY
                        value DESC
                )
        WHERE   rownum = 1
        )
SELECT  *
FROM    (
        SELECT  *
        FROM    lowest
        UNION ALL
        SELECT  *
        FROM    maximal
        )
WHERE   rownum = 1

SELECT STATEMENT
 COUNT STOPKEY
  VIEW
   UNION-ALL
    VIEW
     COUNT STOPKEY
      VIEW
       TABLE ACCESS BY INDEX ROWID, 20090424_lowest.T_ORDERER
        INDEX RANGE SCAN, 20090424_lowest.IX_ORDERER_VALUE
    VIEW
     COUNT STOPKEY
      VIEW
       TABLE ACCESS BY INDEX ROWID, 20090424_lowest.T_ORDERER
        INDEX FULL SCAN DESCENDING, 20090424_lowest.IX_ORDERER_VALUE

We see that the inner query plans remained the same and just one final UNION-ALL with a COUNT STOPKEY is added to the top.

Let’s check how this query works for a parameter greater than the MAX(value):

WITH    lowest AS
        (
        SELECT  *
        FROM    (
                SELECT  *
                FROM    t_orderer
                WHERE   value > 31415926
                ORDER BY
                        value
                )
        WHERE   rownum = 1
        ),
        maximal AS (
        SELECT  *
        FROM    (
                SELECT  *
                FROM    t_orderer
                ORDER BY
                        value DESC
                )
        WHERE   rownum = 1
        )
SELECT  *
FROM    (
        SELECT  *
        FROM    lowest
        UNION ALL
        SELECT  *
        FROM    maximal
        )
WHERE   rownum = 1

SELECT STATEMENT
 COUNT STOPKEY
  VIEW
   UNION-ALL
    VIEW
     COUNT STOPKEY
      VIEW
       TABLE ACCESS BY INDEX ROWID, 20090424_lowest.T_ORDERER
        INDEX RANGE SCAN, 20090424_lowest.IX_ORDERER_VALUE
    VIEW
     COUNT STOPKEY
      VIEW
       TABLE ACCESS BY INDEX ROWID, 20090424_lowest.T_ORDERER
        INDEX FULL SCAN DESCENDING, 20090424_lowest.IX_ORDERER_VALUE

Right answer and it’s instant again.

One more side note: Oracle is smart enough to avoid the second query execution if the first one succeeds.

Let’s change the second subquery (which selects the maximal value) so that index becomes unusable, and run the query with a big parameter (which makes the maximal value to be returned from the second subquery):

WITH    lowest AS
        (
        SELECT  *
        FROM    (
                SELECT  *
                FROM    t_orderer
                WHERE   value > 31415926
                ORDER BY
                        value
                )
        WHERE   rownum = 1
        ),
        maximal AS (
        SELECT  *
        FROM    (
                SELECT  *
                FROM    t_orderer
                ORDER BY
                        (value + 1) DESC
                        -- The ORDER BY condition above makes the index unusable
                )
        WHERE   rownum = 1
        )
SELECT  *
FROM    (
        SELECT  *
        FROM    lowest
        UNION ALL
        SELECT  *
        FROM    maximal
        )
WHERE   rownum = 1

SELECT STATEMENT
 COUNT STOPKEY
  VIEW
   UNION-ALL
    VIEW
     COUNT STOPKEY
      VIEW
       TABLE ACCESS BY INDEX ROWID, 20090424_lowest.T_ORDERER
        INDEX RANGE SCAN, 20090424_lowest.IX_ORDERER_VALUE
    VIEW
     COUNT STOPKEY
      VIEW
       SORT ORDER BY STOPKEY
        TABLE ACCESS FULL, 20090424_lowest.T_ORDERER

The plan for the second subquery now includes SORT, that’s why it runs for more than 500 ms.

But if we change the parameter to a small one (which is satisfied by the first subquery):

WITH    lowest AS
        (
        SELECT  *
        FROM    (
                SELECT  *
                FROM    t_orderer
                WHERE   value > 314159
                ORDER BY
                        value
                )
        WHERE   rownum = 1
        ),
        maximal AS (
        SELECT  *
        FROM    (
                SELECT  *
                FROM    t_orderer
                ORDER BY
                        (value + 1) DESC
                        -- The ORDER BY condition above makes the index unusable
                )
        WHERE   rownum = 1
        )
SELECT  *
FROM    (
        SELECT  *
        FROM    lowest
        UNION ALL
        SELECT  *
        FROM    maximal
        )
WHERE   rownum = 1

SELECT STATEMENT
 COUNT STOPKEY
  VIEW
   UNION-ALL
    VIEW
     COUNT STOPKEY
      VIEW
       TABLE ACCESS BY INDEX ROWID, 20090424_lowest.T_ORDERER
        INDEX RANGE SCAN, 20090424_lowest.IX_ORDERER_VALUE
    VIEW
     COUNT STOPKEY
      VIEW
       SORT ORDER BY STOPKEY
        TABLE ACCESS FULL, 20090424_lowest.T_ORDERER

, the first subquery returns the result instantly, and the second subquery doesn’t even gets a change to be run.

That’s why the whole query is as fast as the initial one.