Удивительная оптимизация получения distinct values из индекса, а также TopN для каждого


Несколько дней назад на форуме задали, как изначально показалось, старый, скучный, вдоль и поперек изъезженный вопрос:
Есть лента новостей. Все новости разделены на 10 категорий(Политика, спорт, авто, недвижимость и тд).
Надо 1 запросом для каждой категории выбрать 4 новости.
Получается если перебрать результат - сразу идет 4 новости о политике, затем 4 новости о спорте и тд.
Однако, задача стояла - сделать это оптимально, а стандартное решение с обычным TopN через row_number никак оптимальным не назвать, особенно в случае больших таблиц, относительно небольшого количества категорий и неравномерного распределения или просто общей низкой селективности. И вот после нескольких более-менее хороших вариантов, подглядев в решение с PostgreSQL(правда я в нем не стал сильно разбираться, достаточно было увидеть рекурсию, min и предикат), получился отличный вариант.

Но обо всем по порядку:

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

Пусть есть табличка с индексом на поле а:
create table xt_test(a not null,b not null,c)
as
select 
    length(object_name)
   ,nvl(object_id,0)
   ,o.OBJECT_NAME 
from dba_objects o;
create index ix_test_a on xt_test(a);
DB11G/XTENDER> select i.index_name
  2        ,i.distinct_keys,i.num_rows
  3        ,i.blevel,i.leaf_blocks
  4        ,i.avg_leaf_blocks_per_key,i.avg_data_blocks_per_key
  5  from user_indexes i where i.table_name='XT_TEST';

INDEX_NAME  DISTINCT_KEYS  NUM_ROWS   BLEVEL LEAF_BLOCKS AVG_LEAF_BLOCKS_PER_KEY AVG_DATA_BLOCKS_PER_KEY
----------- ------------- --------- -------- ----------- ----------------------- -----------------------
IX_TEST_A              30     69230        1         135                       4                     191

1 row selected.
drop table xt_test purge;
create table xt_test(a not null,b not null,c)
as
select 
    length(object_name)
   ,nvl(object_id,0)
   ,o.OBJECT_NAME 
from dba_objects o 
;
create index ix_test_a on xt_test(a);
begin
  dbms_stats.gather_table_stats( ''
                                ,'XT_TEST'
                                ,estimate_percent=>100
                                ,cascade=>true
                                ,method_opt => 'for all indexed columns size auto'
                               ); 
end;
/

select i.index_name
      ,i.distinct_keys,i.num_rows
      ,i.blevel,i.leaf_blocks
      ,i.avg_leaf_blocks_per_key,i.avg_data_blocks_per_key 
from user_indexes i where i.table_name='XT_TEST';

Распределение значений у этого поля очень неравномерное:
ACOUNT(*)
111
220
359
492
5178
6251
7521
9570
10636
8640
11962
12970
131151
151363
141544
161692
182021
172023
192550
202606
213050
223171
233395
243472
293527
273596
263698
284130
254268
3017063
Всего69230
Стандартный запрос c distinct очень неудачен - в индексе всего 30 distinct_keys, а прочитать придется 135 блоков!
С IFS:
DB11G/XTENDER> select/*+ INDEX(xt_test) */ distinct a from xt_test;

30 rows selected.

Elapsed: 00:00:00.02

Execution Plan
----------------------------------------------------------
Plan hash value: 3405466263

--------------------------------------------------------------------------------
| Id  | Operation          | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           |    30 |    90 |   140   (3)| 00:00:02 |
|   1 |  SORT UNIQUE NOSORT|           |    30 |    90 |   140   (3)| 00:00:02 |
|   2 |   INDEX FULL SCAN  | IX_TEST_A | 69230 |   202K|   137   (1)| 00:00:02 |
--------------------------------------------------------------------------------


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
        138  consistent gets
          0  physical reads
          0  redo size
        751  bytes sent via SQL*Net to client
        431  bytes received via SQL*Net from client
          3  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
         30  rows processed
C IFFS:
DB11G/XTENDER> select distinct a from xt_test;

30 rows selected.

Elapsed: 00:00:00.05

Execution Plan
----------------------------------------------------------
Plan hash value: 4206828362

-----------------------------------------------------------------------------------
| Id  | Operation             | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |           |    30 |    90 |    42  (10)| 00:00:01 |
|   1 |  HASH UNIQUE          |           |    30 |    90 |    42  (10)| 00:00:01 |
|   2 |   INDEX FAST FULL SCAN| IX_TEST_A | 69230 |   202K|    38   (0)| 00:00:01 |
-----------------------------------------------------------------------------------


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
        143  consistent gets
          0  physical reads
          0  redo size
        751  bytes sent via SQL*Net to client
        431  bytes received via SQL*Net from client
          3  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
         30  rows processed
А ведь можно же было бы идти по дереву заходя только в нужные блоки, а не по всем листовым блокам! Однако, Oracle сам по себе такое не осилит и тут как раз придется его выкрутиться: у Oracle помимо IFS(min/max) есть и IRS(min/max) хорошо работающий с диапазонами и границами, и с помощью рекурсивного запроса, можно заставить его читать только нужное!
DB11G/XTENDER> with t_unique( a ) as (
  2                select min(t1.a)
  3                from xt_test t1
  4                union all
  5                select (select min(t1.a) from xt_test t1 where t1.a>t.a)
  6                from t_unique t
  7                where a is not null
  8  )
  9  select * from t_unique where a is not null;

30 rows selected.

Elapsed: 00:00:00.00

Execution Plan
----------------------------------------------------------
Plan hash value: 2791305641

-------------------------------------------------------------------------------------------------------
| Id  | Operation                                 | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                          |           |     2 |    26 |     4   (0)| 00:00:01 |
|*  1 |  VIEW                                     |           |     2 |    26 |     4   (0)| 00:00:01 |
|   2 |   UNION ALL (RECURSIVE WITH) BREADTH FIRST|           |       |       |            |          |
|   3 |    SORT AGGREGATE                         |           |     1 |     3 |            |          |
|   4 |     INDEX FULL SCAN (MIN/MAX)             | IX_TEST_A |     1 |     3 |     2   (0)| 00:00:01 |
|   5 |    SORT AGGREGATE                         |           |     1 |     3 |            |          |
|   6 |     FIRST ROW                             |           |     1 |     3 |     2   (0)| 00:00:01 |
|*  7 |      INDEX RANGE SCAN (MIN/MAX)           | IX_TEST_A |     1 |     3 |     2   (0)| 00:00:01 |
|*  8 |    RECURSIVE WITH PUMP                    |           |       |       |            |          |
-------------------------------------------------------------------------------------------------------

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

   1 - filter("A" IS NOT NULL)
   7 - access("T1"."A">:B1)
   8 - filter("A" IS NOT NULL)


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
         36  consistent gets
          0  physical reads
          0  redo size
        751  bytes sent via SQL*Net to client
        431  bytes received via SQL*Net from client
          3  SQL*Net roundtrips to/from client
         32  sorts (memory)
          0  sorts (disk)
         30  rows processed
Разница очевидна: 36 consistent gets на 30 значений, вместо 135. И это очень маленькая табличка, а на миллионах и миллиардах записей разница будет еще более огромной!
Поясню алгоритм:
  • В первой части union all (3-4 строки плана) мы указываем с чего начать рекурсию, а конкретно выбираем минимальное(первое) значение из индекса.
  • Затем с помощью IRS(min/max) (7-6-5 строки плана) выбираем первое значение большее выбранного на предыдущем этапе
  • Повторяем рекурсию пока что-то находим

Переходим к следующему:

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

Теперь вооруженные легким получением каждого начального значения, мы легко можем получить Топ для каждого из них, но для этого придется воспользоваться либо недокументированным Lateral() с включением соответствующего ивента, либо более простым и стандартным table(). Проблема остается только в том, что воспользоваться инлайн вью с row_number/rownum не получится, т.к. предикат с верхнего уровня не просунется, и придется воспользоваться простым ограничением по count stop key(по rownum) c обязательным доступом по IRS descending (order by там в общем лишний, но дополнительно уменьшает стоимость чтения IRS descending который нам и нужен для неявной сортировки) c подсказкой index_desc, чтобы прибить намертво, иначе сортировка может слететь:
DB11G/XTENDER> with t_unique( a ) as (
  2                select min(t1.a)
  3                from xt_test t1
  4                union all
  5                select (select min(t1.a) from xt_test t1 where t1.a>t.a)
  6                from t_unique t
  7                where a is not null
  8  )
  9  select/*+ use_nl(rids tt) */ *
 10  from t_unique v
 11      ,table(
 12            cast(
 13                 multiset(
 14                          select/*+ index_desc(tt ix_xt_test_ab) */ tt.rowid rid
 15                          from xt_test tt
 16                          where tt.a=v.a
 17                            and rownum<=5
 18                          order by tt.b desc
 19                         )
 20                 as sys.odcivarchar2list
 21                )
 22            ) rids
 23      ,xt_test tt
 24  where tt.rowid=rids.column_value
 25  order by tt.a,tt.b desc;

150 rows selected.

Elapsed: 00:00:00.01

Execution Plan
----------------------------------------------------------
Plan hash value: 4085270117

----------------------------------------------------------------------------------------------------------------------
| Id  | Operation                                    | Name          | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
----------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                             |               |    11M|   506M|       |   149K  (1)| 00:29:54 |
|   1 |  SORT ORDER BY                               |               |    11M|   506M|   649M|   149K  (1)| 00:29:54 |
|   2 |   NESTED LOOPS                               |               |    11M|   506M|       | 16402   (1)| 00:03:17 |
|   3 |    NESTED LOOPS                              |               | 16336 |   239K|       |    60   (0)| 00:00:01 |
|   4 |     VIEW                                     |               |     2 |    26 |       |     4   (0)| 00:00:01 |
|   5 |      UNION ALL (RECURSIVE WITH) BREADTH FIRST|               |       |       |       |         |             |
|   6 |       SORT AGGREGATE                         |               |     1 |     3 |       |         |             |
|   7 |        INDEX FULL SCAN (MIN/MAX)             | IX_TEST_A     |     1 |     3 |       |     2   (0)| 00:00:01 |
|   8 |       SORT AGGREGATE                         |               |     1 |     3 |       |         |             |
|   9 |        FIRST ROW                             |               |     1 |     3 |       |     2   (0)| 00:00:01 |
|* 10 |         INDEX RANGE SCAN (MIN/MAX)           | IX_TEST_A     |     1 |     3 |       |     2   (0)| 00:00:01 |
|* 11 |       RECURSIVE WITH PUMP                    |               |       |       |       |         |             |
|  12 |     COLLECTION ITERATOR SUBQUERY FETCH       |               |  8168 | 16336 |       |    28   (0)| 00:00:01 |
|* 13 |      COUNT STOPKEY                           |               |       |       |       |         |             |
|* 14 |       INDEX RANGE SCAN DESCENDING            | IX_XT_TEST_AB |  2308 | 64624 |       |     8   (0)| 00:00:01 |
|* 15 |    TABLE ACCESS BY USER ROWID                | XT_TEST       |   692 | 22144 |       |     1   (0)| 00:00:01 |
----------------------------------------------------------------------------------------------------------------------

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

  10 - access("T1"."A">:B1)
  11 - filter("A" IS NOT NULL)
  13 - filter(ROWNUM<=5)
  14 - access("TT"."A"=:B1)
  15 - access(CHARTOROWID(VALUE(KOKBF$)))


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
        166  consistent gets
          0  physical reads
          0  redo size
       7523  bytes sent via SQL*Net to client
        519  bytes received via SQL*Net from client
         11  SQL*Net roundtrips to/from client
         33  sorts (memory)
          0  sorts (disk)
        150  rows processed
Аналогично можно через lateral:
alter session set events '22829 trace name context forever';
with t_unique( a ) as (
              select min(t1.a)
              from xt_test t1
              union all
              select (select min(t1.a) from xt_test t1 where t1.a>t.a)
              from t_unique t
              where a is not null
)
select/*+ use_nl(rids tt) */ *
from t_unique v
    ,lateral(
              select/*+ index_desc(tt ix_xt_test_ab) */ tt.*
              from xt_test tt
              where tt.a=v.a
                and rownum<=5
              order by tt.a, b desc
     ) r
order by r.a,r.b desc
В целом, конечно, можно было обойтись и без опасной сортировки, а взять и воспользоваться xmltable вместо table с передачей параметра сразу во внутренний подзапрос, но это чуток потяжелее чем обычный table.

Comments

Анонимный комментирует...

Интересный метод, спасибо, Саян

Имхо, имеет один недостаток, который может быть существенным, - пока не умеет считать стоимость для рекурсивных WITH.

Длинный коммент (>4096) не удалось оставить, поэтому отписал отдельно http://iusoltsev.wordpress.com/2012/09/26/recursive-subquery-factoring-cost/

Отправить комментарий