11

I have a table A with intervals (COL1, COL2):

CREATE TABLE A (
  COL1 NUMBER(15) NOT NULL,
  COL2 NUMBER(15) NOT NULL,
  VAL1 ...,
  VAL2 ...
);
ALTER TABLE A ADD CONSTRAINT COL1_BEFORE_COL2 CHECK (COL1 <= COL2);

The intervals are guaranteed to be "exclusive", i.e. they will never overlap. In other words, this query yields no rows:

SELECT *
FROM (
  SELECT
    LEAD(COL1, 1) OVER (ORDER BY COL1) NEXT,
    COL2
  FROM A
)
WHERE COL2 >= NEXT;

There is currently an index on (COL1, COL2). Now, my query is the following:

SELECT /*+FIRST_ROWS(1)*/ *
FROM A
WHERE :some_value BETWEEN COL1 AND COL2
AND ROWNUM = 1

This performs well (less than a ms for millions of records in A) for low values of :some_value, because they're very selective on the index. But it performs quite badly (almost a second) for high values of :some_value because of a lower selectivity of the access predicate.

The execution plan seems good to me. As the existing index already fully covers the predicate, I get the expected INDEX RANGE SCAN:

------------------------------------------------------
| Id  | Operation                    | Name | E-Rows |
------------------------------------------------------
|   0 | SELECT STATEMENT             |      |        |
|*  1 |  COUNT STOPKEY               |      |        |
|   2 |   TABLE ACCESS BY INDEX ROWID| A    |      1 |
|*  3 |    INDEX RANGE SCAN          | A_PK |        |
------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter(ROWNUM=1)
   3 - access("VAL2">=:some_value AND "VAL1"<=:some_value)
       filter("VAL2">=:some_value)

In 3, it becomes obvious that the access predicate is selective only for low values of :some_value whereas for higher values, the filter operation "kicks in" on the index.

Is there any way to generally improve this query to be fast regardless of the value of :some_value? I can completely redesign the table if further normalisation is needed.

4 Answers 4

11

Your attempt is good, but misses a few crucial issues.

Let's start slowly. I'm assuming an index on COL1 and I actually don't mind if COL2 is included there as well.

Due to the constraints you have on your data (especially non-overlapping) you actually just want the row before the row where COL1 is <= some value....[--take a break--] it you order by COL1

This is a classic Top-N query:

select *
  FROM ( select *
          from A
         where col1 <= :some_value
         order by col1 desc
       )
 where rownum <= 1;

Please note that you must use ORDER BY to get a definite sort order. As WHERE is applied after ORDER BY you must now also wrap the top-n filter in an outer query.

That's almost done, the only reason why we actually need to filter on COL2 too is to filter out records that don't fall into the range at all. E.g. if some_value is 5 and you are having this data:

  COL1 | COL2
     1 |  2
     3 |  4   <-- you get this row 
     6 | 10

This row would be correct as result, if COL2 would be 5, but unfortunately, in this case the correct result of your query is [empty set]. That's the only reason we need to filter for COL2 like this:

select *
  FROM ( select *
           FROM ( select *
                    from A
                   where col1 <= :some_value
                   order by col1 desc
                )
          where rownum <= 1
        )
  WHERE col2 >= :some_value;

Your approach had several problems:

  • missing ORDER BY - dangerous in connection with rownum filter!
  • applying the Top-N clause (rownum filter) too early. What if there is no result? Database reads index until the end, the rownum (STOPKEY) never kicks in.
  • An optimizer glitch. With the between predicate, my 11g installation doesn't come to the idea to read the index in descending order, so it was actually reading it from the beginning (0) upwards until it found a COL2 value that matched --OR-- the COL1 run out of the range.

.

COL1 | COL2
   1 |  2   ^
   3 |  4   |      (2) go up until first match.
            +----- your intention was to start here
   6 | 10

What was actually happening was:

  COL1 | COL2
     1 |  2   +----- start at the beginning of the index
     3 |  4   |      Go down until first match.      
              V
     6 | 10

Look at the execution plan of my query:

------------------------------------------------------------------------------------------
| Id  | Operation                       | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                |        |     1 |    26 |     4   (0)| 00:00:01 |
|*  1 |  VIEW                           |        |     1 |    26 |     4   (0)| 00:00:01 |
|*  2 |   COUNT STOPKEY                 |        |       |       |            |          |
|   3 |    VIEW                         |        |     2 |    52 |     4   (0)| 00:00:01 |
|   4 |     TABLE ACCESS BY INDEX ROWID | A      | 50000 |   585K|     4   (0)| 00:00:01 |
|*  5 |      INDEX RANGE SCAN DESCENDING| SIMPLE |     2 |       |     3   (0)| 00:00:01 |
------------------------------------------------------------------------------------------

Note the INDEX RANGE SCAN **DESCENDING**.

Finally, why didn't I include COL2 in the index? It's a single row-top-n query. You can save at most a single table access (irrespective of what the Rows estimation above says!) If you expect to find a row in most cases, you'll need to go to the table anyways for the other columns (probably) so you would not save ANYTHING, just consume space. Including the COL2 will only improve performance if you query doesn't return anything at all!

Related:

3
  • +1 for renaming your brand to "use the index Lukas". That's tailor-made support :-). I had also tested the doubly-nested ROWNUM filtering, but I'll test again. There had been quite a few analysis steps. Maybe, I did something wrong on the way... The key thing here might actually be leaving COL2 out of the index
    – Lukas Eder
    Mar 7, 2014 at 8:10
  • @LukasEder if you have can show your attempts we can see to find the problem. COL2 should not be an issue. Mar 7, 2014 at 8:17
  • While this query seems to perform just as well as the accepted answer, I'm a bit concerned about the E-Rows value being quite off in my query's actual plan. Thomas Köhne's answer seems to have a more optimal plan with a correct E-Rows value of 1 throughout the query (unless I'm missing something). Besides, it is very readable with respect to the mutual exclusivity of the queried intervals. But thanks anyway! It is always important to be reminded of the Oracle CBO's capability to leverage ROWNUM semantics!
    – Lukas Eder
    Mar 13, 2014 at 9:20
4

I think, because the ranges do not intersect, you can define col1 as primary key and execute the query like this:

SELECT *
  FROM    a
       JOIN
          (SELECT MAX (col1) AS col1
             FROM a
            WHERE col1 <= :somevalue) b
       ON a.col1 = b.col1;

If there are gaps between the ranges you wil have to add:

Where col2 >= :somevalue

as last line.

Execution Plan:

SELECT STATEMENT  
 NESTED LOOPS  
  VIEW  
   SORT AGGREGATE 
    FIRST ROW  
     INDEX RANGE SCAN (MIN/MAX) PKU1
  TABLE ACCESS BY INDEX A
   INDEX UNIQUE SCAN PKU1
9
  • That's quite a clever solution. I wonder what @MarkusWinand thinks about this...?
    – Lukas Eder
    Mar 7, 2014 at 12:40
  • Smart solution, thought of that myself. But I think that it is unlikely to outperform @MarkusWinand's one (or they both show the same results). Can you post the plan to compare? There should be INDEX RANGE SCAN and INDEX UNIQUE SCAN I guess. Mar 7, 2014 at 15:27
  • I have added the execution plan in my post. Mar 7, 2014 at 15:58
  • That's indeed a very cunning solution. I can reproduce this plan. Given the knowledge about ranges being mutually exclusive, this solution seems optimal and very readable. Thanks!
    – Lukas Eder
    Mar 13, 2014 at 9:13
  • 1
    @LukasEder As I said "although it is very likely cached". Physical IO won't suffer a lot, but logical IO will be twice as high as needed because it needs to Travers the tree twice.It's mostly about CPU and locking. Cutting CPU usage by half is usually a good thing ;) Especially if the DB you are using is changed on that basis... Mar 14, 2014 at 7:33
0

Maybe changing this heap table to IOT table would give better performance.

3
  • Not in my case. The existing index fully covers the predicate, so I'm good with an INDEX RANGE SCAN... I guess I should update my question with that info
    – Lukas Eder
    Mar 6, 2014 at 14:35
  • Hmm, In your place I would try to use hash partitioned global indexes.
    – rtbf
    Mar 6, 2014 at 14:51
  • Hmm, I've thought about partitioning before, but not about hash partitioning. Can you show some details about how (and why) this can be optimised with hash partitioning?
    – Lukas Eder
    Mar 6, 2014 at 14:58
-1

I didn't generate sample data to test this but you might want to give it a try.

ALTER TABLE A ADD COL3 NUMBER(15);

UPDATE A SET COL3 = COL2 - COL1;

Create index on COL3.

SELECT /*+FIRST_ROWS(1)*/ *
FROM A
WHERE :some_value < COL3
AND ROWNUM = 1;
1
  • 2
    That won't return the correct result. Example: :some_value = 5, COL1 = 4, COL2 = 6, (:some_value BETWEEN COL1 AND COL2) IS TRUE, COL3 = 2, (:some_value < COL3) IS FALSE
    – Lukas Eder
    Mar 6, 2014 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.