Sokrates on Oracle

Find first n gaps in integer primary key

Posted by Matthias Rogel on 13. September 2016

Setup

sokrates@12.1 > create table t( pk int primary key check(pk > 0));

Table created.

sokrates@12.1 > insert /*+ignore_row_on_dupkey_index(t(pk)) */ into t
sokrates@12.1 > select trunc(dbms_random.value(1, 1e5)) from dual
sokrates@12.1 > connect by level <= 1e5 
sokrates@12.1 > /

63187 rows created.

Finding the first n gaps

sokrates@12.1 > variable n number
sokrates@12.1 > exec :n := 1000

PL/SQL procedure successfully completed.

sokrates@12.1 > set autotr traceonly timi on
sokrates@12.1 > with
sokrates@12.1 > gaps(g, counter, isgap) as
sokrates@12.1 > (
sokrates@12.1 >    select 0, 1, cast(null as varchar2(1)) from dual
sokrates@12.1 >    union all
sokrates@12.1 >    select
sokrates@12.1 >       gaps.g + 1,
sokrates@12.1 >       gaps.counter + case when t.pk is null then 1 else 0 end,
sokrates@12.1 >       case when t.pk is null then 'x' end
sokrates@12.1 >    from gaps, t
sokrates@12.1 >    where gaps.counter <= :n
sokrates@12.1 >    and t.pk(+) = gaps.g + 1
sokrates@12.1 > )
sokrates@12.1 > search breadth first by g asc set o
sokrates@12.1 > cycle g set is_cycle to 1 default 0
sokrates@12.1 > select
sokrates@12.1 >    gaps.g
sokrates@12.1 > from
sokrates@12.1 >    gaps
sokrates@12.1 > where
sokrates@12.1 >    gaps.isgap = 'x'
sokrates@12.1 > /

1000 rows selected.

Elapsed: 00:00:00.12

Execution Plan
----------------------------------------------------------
Plan hash value: 3013247790

----------------------------------------------------------------------------------------------------------
| Id  | Operation                                 | Name         | Rows  | Bytes | Cost (%CPU)| Time  |
----------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                          |              |     2 |    30 |     5  (20)| 00:00:01 |
|*  1 |  VIEW                                     |              |     2 |    30 |     5  (20)| 00:00:01 |
|   2 |   UNION ALL (RECURSIVE WITH) BREADTH FIRST|              |       |       |            |       |
|   3 |    FAST DUAL                              |              |     1 |       |     2   (0)| 00:00:01 |
|   4 |    NESTED LOOPS OUTER                     |              |     1 |    39 |     2   (0)| 00:00:01 |
|*  5 |     RECURSIVE WITH PUMP                   |              |       |       |            |       |
|*  6 |     INDEX UNIQUE SCAN                     | SYS_C0087690 |     1 |    13 |     0   (0)| 00:00:01 |
----------------------------------------------------------------------------------------------------------

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

   1 - filter("GAPS"."ISGAP"='x')
   5 - filter("GAPS"."COUNTER"<=TO_NUMBER(:N))
   6 - access("T"."PK"(+)="GAPS"."G"+1)

Note
-----
   - dynamic statistics used: dynamic sampling (level=2)


Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
       2656  consistent gets
          0  physical reads
          0  redo size
       9313  bytes sent via SQL*Net to client
        500  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
       2635  sorts (memory)
          0  sorts (disk)
       1000  rows processed
Advertisements

3 Responses to “Find first n gaps in integer primary key”

  1. Hi Matthias,

    Just for fun, another solution:

    select lat.g
    from (
    select 
      l, pk, n
    from (
       select
             t.pk
            ,lag(t.pk,1,0) over(order by t.pk) l
            ,row_number()over(order by t.pk) rn
            ,t.pk - row_number()over(order by t.pk) N
       from t
       order by pk
       )
    where l+1!=pk
    ) v
    , lateral(select v.l+level g from dual connect by v.l+level<v.pk) lat
    where rownum<=:n
    

    I’ve tested it on my test db and it seems it has less number of logical reads and sorts:

    Execution Plan
    ----------------------------------------------------------
    Plan hash value: 3552639947
    
    ---------------------------------------------------------------------------------------------------
    | Id  | Operation                       | Name            | Rows  | Bytes | Cost (%CPU)| Time     |
    ---------------------------------------------------------------------------------------------------
    |   0 | SELECT STATEMENT                |                 | 63417 |  2415K|   126K  (1)| 00:00:05 |
    |*  1 |  COUNT STOPKEY                  |                 |       |       |            |          |
    |   2 |   NESTED LOOPS                  |                 | 63417 |  2415K|   126K  (1)| 00:00:05 |
    |*  3 |    VIEW                         |                 | 63417 |  1610K|    30   (0)| 00:00:01 |
    |   4 |     WINDOW SORT                 |                 | 63417 |   309K|    30   (0)| 00:00:01 |
    |   5 |      TABLE ACCESS FULL          | T               | 63417 |   309K|    30   (0)| 00:00:01 |
    |   6 |    VIEW                         | VW_LAT_4DB60E85 |     1 |    13 |     2   (0)| 00:00:01 |
    |*  7 |     CONNECT BY WITHOUT FILTERING|                 |       |       |            |          |
    |   8 |      FAST DUAL                  |                 |     1 |       |     2   (0)| 00:00:01 |
    ---------------------------------------------------------------------------------------------------
    
    Predicate Information (identified by operation id):
    ---------------------------------------------------
    
       1 - filter(ROWNUM<=TO_NUMBER(:N))
       3 - filter("PK"<>"L"+1)
       7 - filter("PK">"L"+LEVEL)
    
    
    Statistics
    ----------------------------------------------------------
              0  recursive calls
              0  db block gets
            107  consistent gets
              0  physical reads
              0  redo size
          11628  bytes sent via SQL*Net to client
           1100  bytes received via SQL*Net from client
             68  SQL*Net roundtrips to/from client
            634  sorts (memory)
              0  sorts (disk)
           1000  rows processed
    

    Kind regards,
    Sayan

    • I’m sorry, I’ve posted wrong version. This one is a bit better:

      select lat.g
      from (
      select 
        l, pk, n
      from (
         select--+ index_asc(t (pk))
               t.pk
              ,lag(t.pk,1,0) over(order by t.pk) l
              ,row_number()over(order by t.pk) rn
              ,t.pk - row_number()over(order by t.pk) N
         from t
         order by pk
         )
      where l+1!=pk
      order by pk
      ) v
      , lateral(select v.l+level g from dual connect by v.l+level<v.pk) lat
      where rownum<=:n
      
      • Hi Sayan,

        thanks very much !
        That was my first idea, however, I didn’t get it to work … (LATERAL is pretty awesome, I have to get used to use it !)

        Seems indeed to be cheaper, I have to test it deeper.

        Matthias

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: