Интернет-журнал «FORS» Архив номеров На Главную

Оптимизация distinct и Top N по индексу

Саян Малакшинов,
xt.and.r@gmail.com
Промсвязьбанк

Источник: статья предоставлена автором для публикации в FORS Magazine

1. Получение distinct значений из индекса

Зачастую количество уникальных значений ведущих полей индекса невелико или, по крайней мере, существенно меньше общего количества строк в индексе. В таких случаях, когда индекс весьма большого размера крайне неэффективно получать их через index full scan или index fast full scan. Ведь очевидно, что это можно сделать более эффективно используя структуру ветвей, а не простым проходом по листьям. Далее я покажу как это можно сделать с помощью recursive subquery factoring.

Пусть есть таблица с индексом на столбце а:

SQL>create table ttt
     (owner not null,object_name,created not null,subobject_name,timestamp,object_type)
  2  as
  3  select
  4      o.OWNER
  5     ,o.OBJECT_NAME
  6     ,o.CREATED
  7     ,o.SUBOBJECT_NAME
  8     ,o.TIMESTAMP
  9     ,o.OBJECT_TYPE
 10  from dba_objects o
 11      ,xmltable('1,2,3');

Table created.

SQL> create index ix_ttt on ttt(owner,created);

Index created.

Индекс:


OWNER      NAME       BLEVEL  LF_BLOCKS      NDV   NUM_ROWS     CLRF   kBytes   BLOCKS LFB_PER_KEY
---------- ---------- ------ ---------- -------- ---------- -------- -------- -------- -----------
XTENDER    IX_TTT          2        719     2269     208251     4067     6144      768 1

Попробуем получить "distinct owner" обычным способом:

SQL> select distinct owner from ttt;

OWNER     
------------------------------
OWBSYS_AUDIT        
...
...
SYS       
WMSYS     

30 rows selected.

Elapsed: 00:00:00.09
SQL> @last

PLAN_TABLE_OUTPUT          
-------------------------
SQL_ID  cdgdkqgk56ksk, child number 0          
-------------------------------------          
select distinct owner from ttt                 
                 
Plan hash value: 321052436           
                 
------------------------------------------------------------------------------------------
| Id  | Operation        | Name   | Starts | A-Rows |   A-Time   | Buffers | Reads  |  
------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |        |      1 |     30 |00:00:00.08 |     732 |      2 | 
|   1 |  HASH UNIQUE          |        |      1 |     30 |00:00:00.08 |     732 |      2 | 
|   2 |   INDEX FAST FULL SCAN| IX_TTT |      1 |    208K|00:00:00.04 |     732 |      2 | 
------------------------------------------------------------------------------------------ 

Как видите, уникальных значений всего 30, но сколько пришлось прочесть(732 Buffers) и сколько было затрачено времени, чтобы их получить! C IFS и sort unique nosort ситуация не лучше:

SQL> select/*+ index(ttt) */ distinct owner from ttt;
...
...

30 rows selected.

Elapsed: 00:00:00.11
SQL> @last

PLAN_TABLE_OUTPUT           
------------------------
SQL_ID  g9awxq9xvzaat, child number 0           
-------------------------------------           
select/*+ index(ttt) */ distinct owner from ttt           
        
Plan hash value: 1959809473           
        
------------------------------------------------------------------------------ 
| Id  | Operation          | Name   | Starts | A-Rows |   A-Time   | Buffers | 
------------------------------------------------------------------------------ 
|   0 | SELECT STATEMENT   |        |      1 |     30 |00:00:00.08 |     723 | 
|   1 |  SORT UNIQUE NOSORT|        |      1 |     30 |00:00:00.08 |     723 | 
|   2 |   INDEX FULL SCAN  | IX_TTT |      1 |    208K|00:00:00.04 |     723 | 
------------------------------------------------------------------------------ 

А теперь смотрите как это можно оптимизировать с recursive subquery factoring:

SQL> with t_unique( a ) as (
  2 select min(owner)
  3 from ttt
  4 union all
  5 select (select min(t1.owner) from ttt t1 where t1.owner>t.a)
  6 from t_unique t
  7 where a is not null
  8  )
  9  select * from t_unique where a is not null;

A         
------------------------------
APEX_030200         
...
...
XDB       
XTENDER   

30 rows selected.

Elapsed: 00:00:00.04

Всего 67 consistent gets:


-----------------------------------------------------------------------------------------------------
| Id  | Operation                                 | Name   | Starts | A-Rows |   A-Time   | Buffers |
-----------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                          |        |      1 |     30 |00:00:00.01 |      67 |
|*  1 |  VIEW                                     |        |      1 |     30 |00:00:00.01 |      67 |
|   2 |   UNION ALL (RECURSIVE WITH) BREADTH FIRST|        |      1 |     31 |00:00:00.01 |      67 |
|   3 |    SORT AGGREGATE                         |        |      1 |      1 |00:00:00.01 |       3 |
|   4 |     INDEX FULL SCAN (MIN/MAX)             | IX_TTT |      1 |      1 |00:00:00.01 |       3 |
|   5 |    SORT AGGREGATE                         |        |     30 |     30 |00:00:00.01 |      64 |
|   6 |     FIRST ROW                             |        |     30 |     29 |00:00:00.01 |      64 |
|*  7 |      INDEX RANGE SCAN (MIN/MAX)           | IX_TTT |     30 |     29 |00:00:00.01 |      64 |
|   8 |    RECURSIVE WITH PUMP                    |        |     31 |     30 |00:00:00.01 |       0 |
-----------------------------------------------------------------------------------------------------
            
Predicate Information (identified by operation id): 
--------------------------------------------------- 
            
   1 - filter("A" IS NOT NULL)  
   7 - access("T1"."OWNER">:B1)           

Разница очевидна: 67 consistent gets на 30 значений, вместо 723. И это очень маленькая табличка с соотношением количества дистинкт значений к общему количеству строк = 208тысяч на 30 = 6941 записей на одно значение, в случае же больших таблиц и индексов разница будет еще более огромной. С небольшой модификацией этот подход можно использовать и для поиска уникальных значений нескольких ведущих столбцов индекса.

Поясню алгоритм:

2. Топ N записей для каждого значению ключа

Теперь рассмотрим получение Top 5 наиболее ранних строк для каждого owner. Обычно в таких случаях используют запросы вида:

select *
from (
     select
       t.*
      ,row_number() over(partition by ... order by ...) rn
     from t
     where ...
     )
where rn<=N

Прежде всего я хотел бы показать проблему использования "partition by" в таких запросах. Для примера возьмем примитивный запрос, который будет возвращать ТОП 5 наиболее ранних объектов у которых владелец - SYS, и попробуем его с partition by и без.

Не обращайте внимания на то что это аналог простого "select * from (select ... order by ...) where rownum<=5", т.к. это только пример и на самом деле вместо row_number мог бы быть rank или dense_rank.

1. без partition by:

SQL> select *
  2  from (
  3       select
  4          ttt.*
  5         ,row_number() over(/*partition by ttt.owner*/ order by created) rn
  6       from ttt
  7       where owner='SYS'
  8       ) t
  9  where
 10  rn<=5;


OWNER           OBJECT_NAME        OBJECT_TYPE   RN
--------------- -----------------  ----------- ----
SYS             C_OBJ#             CLUSTER        1
SYS             C_OBJ#             CLUSTER        2
SYS             C_OBJ#             CLUSTER        3
SYS             ICOL$              TABLE          4
SYS             ICOL$              TABLE          5

Elapsed: 00:00:00.06

--------------------------------------------------------------------------------------------------
| Id  | Operation                     | Name   | Starts | A-Rows |   A-Time   | Buffers | Reads  |
--------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT              |        |      1 |      5 |00:00:00.05 |       7 |      5 |
|*  1 |  VIEW                         |        |      1 |      5 |00:00:00.05 |       7 |      5 |
|*  2 |   WINDOW NOSORT STOPKEY       |        |      1 |      5 |00:00:00.05 |       7 |      5 |
|   3 |    TABLE ACCESS BY INDEX ROWID| TTT    |      1 |      6 |00:00:00.05 |       7 |      5 |
|*  4 |     INDEX RANGE SCAN          | IX_TTT |      1 |      6 |00:00:00.04 |       4 |      3 |
--------------------------------------------------------------------------------------------------

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

   1 - filter("RN"<=5)
   2 - filter(ROW_NUMBER() OVER ( ORDER BY "CREATED")<=5)
   4 - access("OWNER"='SYS')

2. c partition by:

SQL> select *
  2  from (
  3       select
  4          ttt.*
  5         ,row_number() over(partition by ttt.owner order by created) rn
  6       from ttt
  7       where owner='SYS'
  8       ) t
  9  where
 10  rn<=5;


OWNER           OBJECT_NAME       OBJECT_TYPE         RN
--------------- ----------------- ------------------- ----------
SYS             C_OBJ#            CLUSTER             1
SYS             C_OBJ#            CLUSTER             2
SYS             C_OBJ#            CLUSTER             3
SYS             ICOL$             TABLE               4
SYS             ICOL$             TABLE               5

Elapsed: 00:00:00.20

-------------------------------------------------------------------------------
| Id  | Operation                     | Name   | Starts | A-Rows |   A-Time   |
-------------------------------------------------------------------------------
|   0 | SELECT STATEMENT              |        |      1 |      5 |00:00:00.18 |
|*  1 |  VIEW                         |        |      1 |      5 |00:00:00.18 |
|*  2 |   WINDOW NOSORT               |        |      1 |  93183 |00:00:00.16 |
|   3 |    TABLE ACCESS BY INDEX ROWID| TTT    |      1 |  93183 |00:00:00.10 |
|*  4 |     INDEX RANGE SCAN          | IX_TTT |      1 |  93183 |00:00:00.03 |
-------------------------------------------------------------------------------

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

   1 - filter("RN"<=5)
   2 - filter(ROW_NUMBER() OVER ( PARTITION BY "TTT"."OWNER" ORDER BY "CREATED")<=5)
   4 - access("OWNER"='SYS')

Заметьте, как все изменилось с добавлением "partition by":
WINDOW NOSORT STOPKEY
заменился на просто
WINDOW NOSORT,
вследствие чего прочитаны были все строки с owner='SYS'.
Поэтому по возможности лучше разделять получение Топ N для каждого значения, например, через union all.

Вернемся теперь к начальному вопросу и посмотрим как будет работать стандартный запрос:

select *
from (
     select
        ttt.*
       ,row_number() over(partition by ttt.owner order by created) rn
     from ttt
     ) t
where 
   rn<=5;

-------------------------------------------------------------------------------------------
| Id  | Operation                | Name | Starts | A-Rows |   A-Time   | Buffers | Reads  |
-------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT         |      |      1 |    148 |00:00:00.95 |    2123 |   2118 |
|*  1 |  VIEW                    |      |      1 |    148 |00:00:00.95 |    2123 |   2118 |
|*  2 |   WINDOW SORT PUSHED RANK|      |      1 |    208K|00:00:00.91 |    2123 |   2118 |
|   3 |    TABLE ACCESS FULL     | TTT  |      1 |    208K|00:00:00.42 |    2123 |   2118 |
-------------------------------------------------------------------------------------------

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

   1 - filter("RN"<=5)
   2 - filter(ROW_NUMBER() OVER ( PARTITION BY "TTT"."OWNER" ORDER BY "CREATED")<=5)

Как видите, ради 148 строк пришлось прочитать и отсортировать всю таблицу, хотя у нас есть прекрасно подходящий индекс.

Теперь вооруженные легким получением каждого начального значения, мы легко можем получить Топ для каждого из них, но для этого придется воспользоваться либо XMLtable/xmlsequence, либо недокументированным Lateral() с включением соответствующего ивента, либо более простым и стандартным table(multiset(...)). В случае использования Lateral и table(multiset()) остается проблема только в том, что воспользоваться инлайн вью с row_number/rownum не получится, т.к. предикат с верхнего уровня не просунется, и придется воспользоваться простым ограничением по count stopkey(по rownum) c обязательным доступом по IRS descending (order by там в общем лишний, но дополнительно уменьшает стоимость чтения IRS descending который нам и нужен для неявной сортировки) c подсказкой index_desc, чтобы прибить намертво, иначе сортировка может слететь:

Пример с TABLE и MULTISET:


SQL> with t_unique( owner ) as (
  2      select min(owner)
  3      from ttt
  4      union all
  5      select (select min(t1.owner) from ttt t1 where t1.owner>t.owner)
  6      from t_unique t
  7      where owner is not null
  8  )
  9  select/*+ use_nl(rids ttt) */ ttt.*
 10  from t_unique v
 11      ,table(
 12  cast(
 13       multiset(
 14      select/*+ index_asc(tt ix_ttt) */ tt.rowid rid
 15      from ttt tt
 16      where tt.owner=v.owner
 17        and rownum<=5
 18      order by tt.created asc
 19     )
 20       as sys.odcivarchar2list
 21      )
 22  ) rids
 23      ,ttt
 24  where
 25    v.owner is not null
 26    and ttt.rowid=rids.column_value
 27  order by ttt.owner,ttt.created asc;

-----------------------------------------------------------------------------------------------------------------
| Id  | Operation                                    | Name   | Starts | A-Rows |   A-Time   | Buffers | Reads  |
-----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                             |        |      1 |    148 |00:00:00.37 |     190 |     53 |
|   1 |  SORT ORDER BY                               |        |      1 |    148 |00:00:00.37 |     190 |     53 |
|   2 |   NESTED LOOPS                               |        |      1 |    148 |00:00:00.37 |     190 |     53 |
|   3 |    NESTED LOOPS                              |        |      1 |    148 |00:00:00.18 |     157 |     22 |
|*  4 |     VIEW                                     |        |      1 |     30 |00:00:00.18 |      66 |     22 |
|   5 |      UNION ALL (RECURSIVE WITH) BREADTH FIRST|        |      1 |     31 |00:00:00.18 |      66 |     22 |
|   6 |       SORT AGGREGATE                         |        |      1 |      1 |00:00:00.01 |       3 |      3 |
|   7 |        INDEX FULL SCAN (MIN/MAX)             | IX_TTT |      1 |      1 |00:00:00.01 |       3 |      3 |
|   8 |       SORT AGGREGATE                         |        |     30 |     30 |00:00:00.17 |      63 |     19 |
|   9 |        FIRST ROW                             |        |     30 |     29 |00:00:00.17 |      63 |     19 |
|* 10 |         INDEX RANGE SCAN (MIN/MAX)           | IX_TTT |     30 |     29 |00:00:00.17 |      63 |     19 |
|  11 |       RECURSIVE WITH PUMP                    |        |     31 |     30 |00:00:00.01 |       0 |      0 |
|  12 |     COLLECTION ITERATOR SUBQUERY FETCH       |        |     30 |    148 |00:00:00.01 |      91 |      0 |
|* 13 |      COUNT STOPKEY                           |        |     30 |    148 |00:00:00.01 |      91 |      0 |
|* 14 |       INDEX RANGE SCAN                       | IX_TTT |     30 |    148 |00:00:00.01 |      91 |      0 |
|  15 |    TABLE ACCESS BY USER ROWID                | TTT    |    148 |    148 |00:00:00.19 |      33 |     31 |
-----------------------------------------------------------------------------------------------------------------

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

   4 - filter("V"."OWNER" IS NOT NULL)   
  10 - access("T1"."OWNER">:B1)          
  13 - filter(ROWNUM<=5)       
  14 - access("TT"."OWNER"=:B1)          

Пример с Lateral:

SQL> alter session set events '22829 trace name context forever';

Session altered.

Elapsed: 00:00:00.00
SQL> with t_unique( owner ) as (
  2      select min(owner)
  3      from ttt
  4      union all
  5      select (select min(t1.owner) from ttt t1 where t1.owner>t.owner)
  6      from t_unique t
  7      where owner is not null
  8  )
  9  select r.*
 10  from t_unique v
 11      ,lateral(
 12      select/*+ index_asc(tt ix_ttt) */ tt.*
 13      from ttt tt
 14      where tt.owner=v.owner
 15        and rownum<=5
 16      order by tt.created asc
 17    ) r
 18  where
 19    v.owner is not null
 20  order by r.owner,r.created asc;

...
...
...
----------------------------------------------------------------------------------------------------------------
| Id  | Operation                                   | Name   | Starts | A-Rows |   A-Time   | Buffers | Reads  |
----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                            |        |      1 |    148 |00:00:00.46 |     191 |     53 |
|   1 |  SORT ORDER BY                              |        |      1 |    148 |00:00:00.46 |     191 |     53 |
|   2 |   NESTED LOOPS                              |        |      1 |    148 |00:00:00.46 |     191 |     53 |
|*  3 |    VIEW                                     |        |      1 |     30 |00:00:00.30 |      66 |     22 |
|   4 |     UNION ALL (RECURSIVE WITH) BREADTH FIRST|        |      1 |     31 |00:00:00.30 |      66 |     22 |
|   5 |      SORT AGGREGATE                         |        |      1 |      1 |00:00:00.07 |       3 |      3 |
|   6 |       INDEX FULL SCAN (MIN/MAX)             | IX_TTT |      1 |      1 |00:00:00.07 |       3 |      3 |
|   7 |      SORT AGGREGATE                         |        |     30 |     30 |00:00:00.22 |      63 |     19 |
|   8 |       FIRST ROW                             |        |     30 |     29 |00:00:00.22 |      63 |     19 |
|*  9 |        INDEX RANGE SCAN (MIN/MAX)           | IX_TTT |     30 |     29 |00:00:00.22 |      63 |     19 |
|  10 |      RECURSIVE WITH PUMP                    |        |     31 |     30 |00:00:00.01 |       0 |      0 |
|  11 |    VIEW                                     |        |     30 |    148 |00:00:00.16 |     125 |     31 |
|  12 |     SORT ORDER BY                           |        |     30 |    148 |00:00:00.16 |     125 |     31 |
|* 13 |      COUNT STOPKEY                          |        |     30 |    148 |00:00:00.16 |     125 |     31 |
|  14 |       TABLE ACCESS BY INDEX ROWID           | TTT    |     30 |    148 |00:00:00.16 |     125 |     31 |
|* 15 |        INDEX RANGE SCAN                     | IX_TTT |     30 |    148 |00:00:00.01 |      91 |      0 |
----------------------------------------------------------------------------------------------------------------
           
Predicate Information (identified by operation id):
---------------------------------------------------

PLAN_TABLE_OUTPUT   
----------------------------------------
          
   3 - filter("V"."OWNER" IS NOT NULL)  
   9 - access("T1"."OWNER">:B1)         
  13 - filter(ROWNUM<=5)      
  15 - access("TT"."OWNER"="V"."OWNER")

Эффект заметен сразу: 190-191 consistent gets против 2123.
C XMLtable будет похуже чем у lateral и table-multiset, но все равно гораздо меньше, чем в обычном варианте:

with t_unique( owner ) as (
    select min(owner)
    from ttt
    union all
    select (select min(t1.owner) from ttt t1 where t1.owner>t.owner)
    from t_unique t
    where owner is not null
)
select r.*
from t_unique v
    ,xmltable('/ROWSET/ROW'
    passing(
      dbms_xmlgen.getxmltype(
        q'[select *
           from (
   select/*+ index_asc(tt ix_ttt) */ owner, 
            to_char(created,'yyyy-mm-dd hh24:mi:ss') created
   from ttt tt
   where tt.owner=']'||v.owner||q'['
   order by tt.created asc
           )
           where rownum<=5
        ]'
      )
    )
    columns 
      owner   varchar2(30) path 'OWNER'
     ,created varchar2(30) path 'CREATED'
     ,x xmltype path '.'
   ) r
where
  v.owner is not null
order by r.owner,r.created asc;

-------------------------------------------------------------------------------------------------------------------
| Id  | Operation                                         | Name         | Starts | A-Rows |   A-Time   | Buffers |
-------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                                  |              |      1 |    148 |00:00:00.28 |     365 |
|   1 |  SORT ORDER BY                                    |              |      1 |    148 |00:00:00.28 |     365 |
|   2 |   NESTED LOOPS                                    |              |      1 |    148 |00:00:00.10 |     365 |
|*  3 |    VIEW                                           |              |      1 |     30 |00:00:00.01 |      66 |
|   4 |     UNION ALL (RECURSIVE WITH) BREADTH FIRST      |              |      1 |     31 |00:00:00.01 |      66 |
|   5 |      SORT AGGREGATE                               |              |      1 |      1 |00:00:00.01 |       3 |
|   6 |       INDEX FULL SCAN (MIN/MAX)                   | IX_TTT       |      1 |      1 |00:00:00.01 |       3 |
|   7 |      SORT AGGREGATE                               |              |     30 |     30 |00:00:00.01 |      63 |
|   8 |       FIRST ROW                                   |              |     30 |     29 |00:00:00.01 |      63 |
|*  9 |        INDEX RANGE SCAN (MIN/MAX)                 | IX_TTT       |     30 |     29 |00:00:00.01 |      63 |
|  10 |      RECURSIVE WITH PUMP                          |              |     31 |     30 |00:00:00.01 |       0 |
|  11 |    COLLECTION ITERATOR PICKLER FETCH    | XMLSEQUENCEFROMXMLTYPE |     30 |    148 |00:00:00.10 |     299 |
-------------------------------------------------------------------------------------------------------------------

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

   3 - filter("V"."OWNER" IS NOT NULL)
   9 - access("T1"."OWNER">:B1)

Эффективность этого метода зависит от упомянутого соотношения количества уникальных значений(NUM_DISTINCT столбца) и количества листовых блоков индекса(LEAF_BLOCKS) и, конечно, высоты дерева(BLEVEL).