TOP N query with an IN List iterator

This post is an example of an interesting little problem I came across with TOP N queries recently.

Consider the following table, CALLS, that could contain telephone call records:

create table calls (customer_id     integer not null,
                    call_type_id    integer not null,
                    call_start_time date    not null,
                    call_duration   integer not null);

create index calls_idx1 on calls (customer_id, call_start_time);

Now create some data so that we have 100 customers, each with 1000 calls of various durations and start_times:

insert into calls 
select mod(level, 100),
       mod(level, 3),
       sysdate - level,
       mod(level, 1000)
from dual
connect by level <= 100000;

A query to get the 10 newest calls for a given customer would look like:

select /*+ gather_plan_statistics */
       * 
from
(
  select *
  from calls
  where customer_id = 1
  order by call_start_time desc
) where rownum <= 10;


select * 
from table (dbms_xplan.display_cursor(format => 'allstats last'));           

-------------------------------------------------------------------------------------------------------
| Id  | Operation                      | Name       | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
-------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT               |            |      1 |        |     10 |00:00:00.01 |       7 |
|*  1 |  COUNT STOPKEY                 |            |      1 |        |     10 |00:00:00.01 |       7 |
|   2 |   VIEW                         |            |      1 |   1000 |     10 |00:00:00.01 |       7 |
|   3 |    TABLE ACCESS BY INDEX ROWID | CALLS      |      1 |   1000 |     10 |00:00:00.01 |       7 |
|*  4 |     INDEX RANGE SCAN DESCENDING| CALLS_IDX1 |      1 |     10 |     10 |00:00:00.01 |       3 |
-------------------------------------------------------------------------------------------------------

Note that Oracle can get 10 rows from the index, access the table and return the result very efficiently, without sorting the data. This is vital if the full result set contains millions of rows.

Now lets make a subtle change to the query:

select /*+ gather_plan_statistics */
       * 
from
(
  select /*+ index(c calls_idx1) */ 
         *
  from calls c
  where (customer_id = 1 or customer_id = 2)
  order by call_start_time desc
) where rownum <= 10;


select * 
from table (dbms_xplan.display_cursor(format => 'allstats last'));           

This time we want the top 10 rows when sorted between two customer_ids:

-----------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                       | Name       | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
 -----------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                |            |      1 |        |     10 |00:00:00.01 |     633 |       |       |          |
|*  1 |  COUNT STOPKEY                  |            |      1 |        |     10 |00:00:00.01 |     633 |       |       |          |
|   2 |   VIEW                          |            |      1 |   2232 |     10 |00:00:00.01 |     633 |       |       |          |
|*  3 |    SORT ORDER BY STOPKEY        |            |      1 |   2232 |     10 |00:00:00.01 |     633 | 20480 | 20480 |18432  (0)|
|   4 |     INLIST ITERATOR             |            |      1 |        |   2000 |00:00:00.01 |     633 |       |       |          |
|   5 |      TABLE ACCESS BY INDEX ROWID| CALLS      |      2 |   2232 |   2000 |00:00:00.01 |     633 |       |       |          |
|*  6 |       INDEX RANGE SCAN          | CALLS_IDX1 |      2 |    438 |   2000 |00:00:00.01 |      11 |       |       |          |
-----------------------------------------------------------------------------------------------------------------------------------

There are two things to note:

• A SORT ORDER BY STOPKEY operation has got into the plan before the COUNT STOPKEY operation
• The actual rows returned at step 6 has gone from 10 to 2000 (each customer has 1000 calls).

What is also interesting is that for 1 customer it took 7 LIOs to answer the query, but for two it required 633.

What I would have expected to happen, is Oracle would notice this is a top N query, and it would have gotten the top 10 rows for customer 1 and then the top 10 rows for customer 2, and sorted those 20 rows to find the top 10 overall. Unfortunately, what it seems to do is find all the rows that match the where clause for each customer (1000 each) and then sort the 2000 to return 10. In this example the number of rows is small, so it doesn't matter much, but if each customer had 1 million calls the performance would be terrible.

I searched high and wide for a solution to this problem and finally got an answer from Oracle that this is a limitation in the current database version (11gR2 and below).

It turns out this is a rare case where a bit of procedural code will outperform a single SQL statement. The best solution is to use a pipelined function to iterate over the list of customers, running an efficient top N query for each one, returning at most N results. If the pipelined function is called in a nested view, then each set of N results can be sorted together to give the overall top N rows.

It also highlighted an very important point about TOP N queries for me. When looking at the explain plan for a TOP N query, you need to ensure there are no 'sort' operations in the plan before the COUNT STOPKEY operation. If there is, it is a sign the index on the table is not able to access the TOP N rows efficiently for a very large result set.