Oracle mechanics

26.09.2012

Оценка стоимости запроса с использованием рекусивных операций WITH (Recursive Subquery Factoring)

Filed under: CBO,heuristics,Oracle,Oracle new features — Игорь Усольцев @ 08:31
Tags: , , ,

Саян Малакшинов описал интересный и эффективный способ получения неповноряющихся значений — Удивительная оптимизация получения distinct values из индекса, а также TopN для каждого

Однако, как я понимаю, оптимизатор пока не умеет правильно оценивать стоимость операции Recursive Subquery Factoring и предложенный способ, несмотря на безусловную эффективность в отдельных случаях, не является универсальным и фактически требует ручного контроля стоимости запроса в зависимости от используемых данных

Тестовый DDL:

11.2.0.3.ORCL112@SCOTT SQL> create table xt_test(a not null,b not null,c)
  2  as
  3  select
  4      length(object_name)
  5     ,nvl(object_id,0)
  6     ,o.OBJECT_NAME
  7  from dba_objects o
  8  ;

Table created.

SQL> create index ix_test_a on xt_test(a);

Index created.

SQL> exec dbms_stats.gather_table_stats( '', 'XT_TEST');

PL/SQL procedure successfully completed.

Саян показал эффективный и недорогой запрос для извлечения неповноряющихся значений стобца A с использованием INDEX RANGE SCAN (MIN/MAX):

11.2.0.3.ORCL112@SCOTT SQL> 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  select * from t_unique where a is not null;

30 rows selected.

Elapsed: 00:00:00.01

-------------------------------------------------------------------------------------------------------
| 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
----------------------------------------------------------
         36  consistent gets
         32  sorts (memory)
          0  sorts (disk)
         30  rows processed

Если же попробовать применить этот же метод с другим стобцом можно видеть, например, что для фактически уникального столбца B со множеством distinct значений (75919), и соответсвенно с тысячами рекурсивных запросов, Oracle вычисляет тот же скромный Cost=4 , что и для столбца A с 30 неповторяющимися значениями :(

SQL> create index ix_test_b on xt_test(b);

Index created.

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

75919 rows selected.

Elapsed: 00:00:01.52

-------------------------------------------------------------------------------------------------------
| 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 |     5 |            |          |
|   4 |     INDEX FULL SCAN (MIN/MAX)             | IX_TEST_B |     1 |     5 |     2   (0)| 00:00:01 |
|   5 |    SORT AGGREGATE                         |           |     1 |     5 |            |          |
|   6 |     FIRST ROW                             |           |     1 |     5 |     2   (0)| 00:00:01 |
|*  7 |      INDEX RANGE SCAN (MIN/MAX)           | IX_TEST_B |     1 |     5 |     2   (0)| 00:00:01 |
|*  8 |    RECURSIVE WITH PUMP                    |           |       |       |            |          |
-------------------------------------------------------------------------------------------------------

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

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

Statistics
----------------------------------------------------------
     130789  db block gets
       6564  consistent gets
          0  physical reads
          0  redo size
      75921  sorts (memory)
          0  sorts (disk)
      75919  rows processed

— при этом запрос выполняется ожидаемо медленно:  много чтений и сортировок, никак не отраженных в стоимости

Данные о количестве DISTINCT_KEYS в статистике столбцов и индексов по-прежнему в наличии — просто они никак не учитываются оптимизатором:

SQL> 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_B                              75919      75919          1         168                       1                       1
IX_TEST_A                                 30      75919          1         148                       4                     213

В то же время выбираемый оптимизатором по умолчанию (возможно, в силу каких-то внутренних правил / heuristics) INDEX FAST FULL SCAN оказывается  хоть и менее выгодным для столбцов с малым количеством неповторяющихся значений, но универсально подходит для столбцов с любым распределением значений и в смысле скорости выполнения и в смысле более точной оценки числа возвращаемых строк и вычисляемой стоимости:

SQL> select distinct b from xt_test;

75919 rows selected.

Elapsed: 00:00:00.26

-------------------------------------------------------------------------------------------
| Id  | Operation             | Name      | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |           | 75919 |   370K|       |   282   (2)| 00:00:04 | -- точная оценка
|   1 |  HASH UNIQUE          |           | 75919 |   370K|   904K|   282   (2)| 00:00:04 |
|   2 |   INDEX FAST FULL SCAN| IX_TEST_B | 75919 |   370K|       |    48   (3)| 00:00:01 |
-------------------------------------------------------------------------------------------

Statistics
----------------------------------------------------------
          0  db block gets
        175  consistent gets
          0  physical reads
          0  redo size
          0  sorts (memory)
          0  sorts (disk)
      75919  rows processed

SQL> select distinct a from xt_test;

30 rows selected.

Elapsed: 00:00:00.04

-----------------------------------------------------------------------------------
| Id  | Operation             | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |           |    30 |    90 |    46   (9)| 00:00:01 | -- -//-
|   1 |  HASH UNIQUE          |           |    30 |    90 |    46   (9)| 00:00:01 |
|   2 |   INDEX FAST FULL SCAN| IX_TEST_A | 75919 |   222K|    42   (0)| 00:00:01 |
-----------------------------------------------------------------------------------

Statistics
----------------------------------------------------------
          0  db block gets
        155  consistent gets
         37  physical reads
          0  redo size
          0  sorts (memory)
          0  sorts (disk)
         30  rows processed

— при построении этих планов Oracle успешно учитывает статистику DISTINCT_KEYS

Предполагаю, что Recursive Subquery Factoring — достаточно свежая техника запросов (11.2+) и пока не подкреплена соответствующими методами расчёта стоимости

И, вероятно, разработчики Oracle, зная об этой «слабости», пока сознательно избегают использовать эти новые, при определённых условиях безусловно эффективные преобразования при формировании планов запросов?)

4 комментария »

  1. Спасибо, Игорь за ответ, исследование и комментарий. Мне самому некогда было, поэтому я не стал рассчитывать более точную формулу, когда мой алгоритм применять выгоднее. Но грубое приближение таково: number_distinct_values*blevel*2<leafblocks: то есть количество чтений при спуске по дереву должно быть меньше самого размера индекса. Но эта прикидка весьма грубая и не учитывая ни кэширование, ни мультипассы. Кстати, у меня индекс размером больше 42 гигов мой алгоритм обрабатывает за 6 секунд, при том что стандартного дистинкт я тупо не дождался :) Хочу еще заметить что IFFS будет выгоден только при таком маленьком количестве блоков индекса и небольшой размазанности значений по блокам индекса. В большинстве же случаев будет выгоднее sort unique nosort + IFS. Кстати мой алгоритм можно применять очень выгодно и для получения набора ведущих дистинкт полей из индекса. А по поводу стоимости рекурсивного запроса, то это в общем-то характерная такая проблема и для более-менее сложных connect by: редко рассчитывается правильная глубина дерева. При правильном расчете глубины стоимость бы они смогли получить верную.

    комментарий от Саян Малакшинов — 26.09.2012 @ 10:01 | Ответить

  2. Да, еще поправка к «универсально подходит для столбцов с любым распределением значений и в смысле скорости выполнения»: большее значение имеет соотношение размера индекса к количеству дистинктов, безотносительно распределения. В моем как раз случае с 42-гиговым индексом был весьма сильный разброс: были значения как с десятком строк, так и с десятками миллионов. Вообще редко бывает, когда значения более-менее равномерно размазаны.

    комментарий от Саян Малакшинов — 26.09.2012 @ 10:15 | Ответить

    • Спасибо за уточнение, Саян, так правильнее
      было бы совсем хорошо найти простой способ (без труднопрогнозируемых рекурсий) стимулировать поиск distinct’ов с использованием в основном корневых блоков индекса, что умеют делать операции INDEX * SCAN (MIN/MAX)

      комментарий от Igor Usoltsev — 26.09.2012 @ 10:37 | Ответить

      • Да, было бы замечательно. Можно попробовать как все время советует Тимур Ахмадеев оформить SR :) Но особо не верится, у меня баги-то по два месяца оформляются)

        комментарий от Sayan Malakshinov — 26.09.2012 @ 14:15 | Ответить


RSS feed for comments on this post. TrackBack URI

Добавить комментарий

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

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

Блог на WordPress.com.

%d такие блоггеры, как: