среда, 23 сентября 2015 г.

ORACLE: основы стоимостной оптимизации

На основе книги "ORACLE - основы стоимостной оптимизации" - автор Дж. Льюис.

Общие понятия


Селективность = (макс значение - мин значение отобранных данных)/(макс значение - мин значение всех данных)
в общем случае = отобранный интервал / весь интервал
Весь интервал определяется на основе статистики таблицы, это столбец destiny - разряженность: обратный показатель от кол-ва уникальных значений = 1/num_distinct.
Если на столбце есть гистограмма, то рассчитывается на основании ее, как сумма квадратов частоты нечастно встречающихся значения / (кол-во не пустых строк * кол-во не пустых нечастых строк)
т.е. на таблице с 2000 строк, где 1000 строк имеют одно значение, то без гистограммы destiny = 1/1001
с гистограммой = 1*1 / (2000 * 1) = 1/2000 в итоге получается, что запрос по гистограмме получится более селективным = отбираемый интервал * destiny, что справедливо, т.к. кроме уникальных значение будут использоваться гранулы гистограммы.

Итоговая селективность = селктивность * доля NULL полей

Особенности расчета:
* при расчете селективности при выходе за high_value (верхнее или нижне значение) - селективность линейно падает, т.е. не сразу обнуляется.
отсюда проблема : в динамичной oltp бд следуюем смещать high_value заранее перед началом нового дня, т.к. статистика собирается вконце дня, а запросы выше high_value уже идут
* когда селективность падает меньше числа строк таблицы, то селектиновсть = 1 / число строк таблицы

Селективности логических операций:
* and = селективность 1 * селективность 2
* or = селективность 1 + селективность 2 - (селективность 1 * селективность 2 )
* not = 1 - селективность 1

Кардинальность ( число отобранных записей ) = селективность * общее число записей

Стоимость = необходимое кол-во операций выраженное в стандартных единицах

Стоимость табличного доступа и системная статистика

Т.к. стоимость вырожается в стандартных единицах времени одноблочного чтения, то сначала определимся с системными показателями.
Собираются они на основе данных системы, через dbms_stats.gather_system_stats
Узнать их можно в таблице sys.aux_stats$
select * from sys.aux_stats$ where sname = 'SYSSTATS_MAIN' order by pname;

sreadtim - время одноблочного чтения в мс
mreadtim - время многоблочного чтеняи в мс
cpuspeed - время млн стандратных операций процессора под нагрузкой (CPUSPEEDNW - без нагрузки)
ioseektim - время поиска данных на диске и передачи их oracle
IOTFRSPEED - число байт читаемых oracle в мс

статистику под нагрузкой собирается коммандой:
dbms_stats.gather_system_stats('start');
-- промежуток времени под нагрузкой
dbms_stats.gather_system_stats('stop');

Если системной статистики под нагрузкой нет, то показатели sreadtim и mreadtim синтезируются, как время позиционирования на диске + время чтения блоков
sreadtim = ioseektim + db_block_size/IOTFRSPEED
mreadtim = ioseektim + db_file_multyblock_read_count * db_block_size/IOTFRSPEED

Стоимость табличного доступа:
Cost = (
 #Sreads * sreadtim +
 #MRds * mreadtim +
 #CPUCycles / cpuspeed
 ) / sreadtim
= (
 #Sreads + 
 #MRds * mreadtim / sreadtim +
 #CPUCycles / ( cpuspeed * sreadtim )
)

Где
#Sreads = число одноблочно читаемых блоков
#CPUCycles = число стандартных операций процессара
#MRds = число многоблочно читаемых блоков / db_file_multyblock_read_count

Т.е. стоимость табличного доступа = число одноблочных чтений + число многоблочных чтений преобразованных к одноблочным + число стандартных операций процессора во времени однобл. чтения.

Стоимость индексного доступа

=
  blevel + 
  ceiling(leaf_blocks * селективность по индексу) +
  ceiling(clustering_factor * селективность по таблице)

blevel - кол-во уровней ветвления дерева до листов (высота)
leaf_blocks - кол-во блоков в листе
clustering_factor - соответствие блоков индекса и таблицы

селективность индекса = кол-во отбираемых строк индекса от общего числа
Если индекс многостолбцовый и по первым N-1 есть сравнение отличное от "=" (или столбец вовсе пропущен), то oracle не использует условия столбцов m-N для фильтрации индекса (m- первый предикат отличный от =)
Т.е. селективность берется от первых m столбцов.
Так что столбцы, по которым предположительно будет фильтрация по диапазону лучше распологать вконце индекса.
Это событие можно отследить в плане по access_prediacate - доступ к индексу и filter_prediacate - фильтрация полученных блоков из таблицы

селективность таблицы = кол-во отбираемых строк таблицы от общего числа по столбцам которые есть и в индексе и в фильтре (тут уже условие и порядок не играет роли), т.к. результирующие данные индекса дофильтровываются оставшимися столбцами.
наибольший вклад в стоимость делает показатель "clustering_factor * селективность по таблице"

Параметры влияющие на фактор кластеризации индекса:
* segment freelist - количство точек доступа к таблице (указывается в DDL таблицы), уменьшает конкуренцию за ресурсы таблицы, но ооочень сильно увеличивать фактор кластеризации и как следствие скорость доступа по диапазону. Что приведет оптимизатор не использовать индекс по диапозону, а лучше сделать полное сканирование таблицы.
* reverse index - аналогично уменьшает конкуренцию за ресуры, но очень сильно повышает кластеризацию
Влияние constraint на план:
* Oracle может применить обычный индекс на столбце, даже если в запросе написана функция по нему " UPPER(t.col) = 'ABC' ", если на этом столбце есть constraint на обязательный UPPER. Запрос будет преобразован к " t.col = 'ABC' "
* Если на столбце есть ограничение по диапазону, то оно также будет перенесено в план запроса.

BM index
* если поле NOT NULL и по нему есть BITMAP индекс, то может эффективно использоваться операция отрицания индекса или minus 2 BM индексов. Если есть NULL, то это усложняет запросы дополнительным сканированием с поиском NULL в индексе.
* у BM нет информации о распределении данных, так что не посчитать правильно: фактор кластеризации, кардинальность
* Альтернативной использования 2 BM индексов при OR является хинт +use_concat - запрос будет трансформирован к union из сторон OR

Гистограммы:

статистическое распределение значение столбца по диапазоную
Количество собранных интервалов указывается параметром "SIZE"
dbms_stats.gather_table_stats (
 ownname    => user,
 tabname    => 'T2',
 method_opt => 'FOR ALL COLUMNS SIZE 254'
);

Вызов статистики соберет 254 интервала гистограммы, т.е. замеряем на 254 интервалов кол-ва записей.
Это необходимо, если данные распределены по таблицы неравномерно, что чаще всего и бывает.

Проблемы расчета селективности:

Секционированные таблицы
при выборке из нескольких секций используется статистика всей таблицы, а не сумма статистик партиций.
Проблему можно частично решить, если использовать гистограммы на глобальной статистике таблицы
/* План по секционированной таблице */ 

drop table t2;
create table t2
(
  n integer,
  txt varchar(254),
  part_id integer
)
partition by range (part_id) INTERVAL(1)
(
  partition P1 values less than (1)
  );
insert into t2(n, txt, part_id) select level, rpad(level, ceil(level/5), level) , 1 from dual connect by level < 1000;

begin
  dbms_stats.gather_table_stats (
     ownname    => user,
     tabname    => 'T2',
     method_opt => 'FOR ALL COLUMNS SIZE 1'
  );
end;

explain plan for select * from t2 where n between 200 and 300;

-- Ожидаемая кардинальность ~100
SELECT * FROM table(DBMS_XPLAN.DISPLAY); 

--------------------------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     | Pstart| Pstop |
--------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |   102 | 11016 |    14   (0)| 00:00:01 |       |       |
|   1 |  PARTITION RANGE ALL|      |   102 | 11016 |    14   (0)| 00:00:01 |     1 |1048575|
|*  2 |   TABLE ACCESS FULL | T2   |   102 | 11016 |    14   (0)| 00:00:01 |     1 |1048575|
--------------------------------------------------------------------------------------------

--добавляем меньшее число записей во вторую секцию:
insert into t2(n, txt, part_id) select level, rpad(level, ceil(level/5), level) , 2 from dual connect by level < 500;

begin
  dbms_stats.gather_table_stats (
     ownname    => user,
     tabname    => 'T2',
     method_opt => 'FOR ALL COLUMNS SIZE 1'
  );
end;

explain plan for select * from t2 where n between 200 and 300;

--вместо ожидаемых 200 записей, получаем 150 из-за статистики на уровне таблицы.
SELECT * FROM table(DBMS_XPLAN.DISPLAY);

--------------------------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     | Pstart| Pstop |
--------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |   153 | 14076 |    27   (0)| 00:00:01 |       |       |
|   1 |  PARTITION RANGE ALL|      |   153 | 14076 |    27   (0)| 00:00:01 |     1 |1048575|
|*  2 |   TABLE ACCESS FULL | T2   |   153 | 14076 |    27   (0)| 00:00:01 |     1 |1048575|
--------------------------------------------------------------------------------------------

-- Но если собрать гистограмму, то ситуация выправляется:
begin
  dbms_stats.gather_table_stats (
     ownname    => user,
     tabname    => 'T2',
     method_opt => 'FOR ALL COLUMNS SIZE 254'
  );
end;

explain plan for select * from t2 where n between 200 and 300;

--получили ожидаемые ~200 строк
SELECT * FROM table(DBMS_XPLAN.DISPLAY);

--------------------------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     | Pstart| Pstop |
--------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |   197 | 18124 |    27   (0)| 00:00:01 |       |       |
|   1 |  PARTITION RANGE ALL|      |   197 | 18124 |    27   (0)| 00:00:01 |     1 |1048575|
|*  2 |   TABLE ACCESS FULL | T2   |   197 | 18124 |    27   (0)| 00:00:01 |     1 |1048575|
--------------------------------------------------------------------------------------------

нельзя использовать очень большие (и очень мелкие) значения поумолчанию для столбцов
это приведет к неверному расчету селективнсти: (дата2-дата1)/(макс дата-мин дата)
Частично эту проблему можно решить, если собрать гистограмму по сканируемому столбцу.
create table t as select sysdate+level as dt, rpad(level, level, level) as rn from dual connect by level < 10000;

begin
dbms_stats.gather_table_stats(ownname => user, tabname => 'T');
end;

explain plan for select * from t where dt between to_date('19.09.2015','dd.mm.yyyy') and to_date('19.10.2015','dd.mm.yyyy');
SELECT * FROM table(DBMS_XPLAN.DISPLAY);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |    31 | 99479 |  2055   (1)| 00:00:25 |
|*  1 |  TABLE ACCESS FULL| T    |    31 | 99479 |  2055   (1)| 00:00:25 |
--------------------------------------------------------------------------


insert into t(dt, rn) values(sysdate-365*100, '*');
insert into t(dt, rn) values(sysdate+365*100, '$');

begin
dbms_stats.gather_table_stats(ownname => user, tabname => 'T');
end;

explain plan for select * from t where dt between to_date('19.09.2015','dd.mm.yyyy') and to_date('19.10.2015','dd.mm.yyyy');
SELECT * FROM table(DBMS_XPLAN.DISPLAY);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |     1 |  3208 |  2066   (1)| 00:00:25 |
|*  1 |  TABLE ACCESS FULL| T    |     1 |  3208 |  2066   (1)| 00:00:25 |
--------------------------------------------------------------------------

Нежелательно использовать текстовые ключи
Oracle не сможет определить кардинальность запроса по диапазону, т.к. не сможет вычислить число записей в нем

При поиске по бинд перменной селективность фиксированная = 5% (sysdate+5 - бинд, а sysdate - уже константа), если выключена bind piking

Проблема кореляции столбцов и высчитывание стоимости по AND. По формуле селективности перемножаются, хотя реально данные в столбца совпадают.
Пример, когда планироващик ожидает увидеть 10 записей (селктивность 10%*10%*10%=0,1%)
/* случайные данные */
drop table tt;
create table tt as 
select DBMS_RANDOM.VALUE(1,10000) n1, DBMS_RANDOM.VALUE(1,10000) n2, DBMS_RANDOM.VALUE(1,10000) n3
from dual connect by level <= 10000;
begin
dbms_stats.gather_table_stats(ownname => user, tabname => 'TT', method_opt => 'FOR ALL COLUMNS SIZE 1', estimate_percent => 100);
end;
explain plan for select * from TT where (N1 between 1 and 1000) AND (N2 BETWEEN 1 AND 1000) AND (N3 BETWEEN 1 AND 1000);
SELECT * FROM table(DBMS_XPLAN.DISPLAY(null,null,'ALL'));

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |    10 |   660 |    31   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| TT   |    10 |   660 |    31   (0)| 00:00:01 |
--------------------------------------------------------------------------


select COUNT(*) from TT where (N1 between 1 and 1000) AND (N2 BETWEEN 1 AND 1000) AND (N3 BETWEEN 1 AND 1000);

  COUNT(*)
----------
        11

/* связанные данные */
drop table tt;
create table tt as 
select level n1, level + 1 n2, level + 2  n3 
from dual connect by level <= 10000;
begin
dbms_stats.gather_table_stats(ownname => user, tabname => 'TT', method_opt => 'FOR ALL COLUMNS SIZE 1', estimate_percent => 100);
end;
explain plan for select * from TT where (N1 between 1 and 1000) AND (N2 BETWEEN 2 AND 1001) AND (N3 BETWEEN 3 AND 1002);
SELECT * FROM table(DBMS_XPLAN.DISPLAY(null,null,'ALL'));

-------------------------------------------------------------------------- 
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time 
-------------------------------------------------------------------------- 
|   0 | SELECT STATEMENT  |      |    10 |   120 |     8   (0)| 00:00:01 
|*  1 |  TABLE ACCESS FULL| TT   |    10 |   120 |     8   (0)| 00:00:01 
--------------------------------------------------------------------------    

select COUNT(*) from TT where (N1 between 1 and 1000) AND (N2 BETWEEN 1 AND 1000) AND (N3 BETWEEN 1 AND 1000);

  COUNT(*)
----------
      1000

 Эту проблему можно решить 2 способами:
 ** Хинт +dynamic_sampling - проходится по N случайным строкам и ищет соответствие where, на основе этого вычисляется селективность, а не из статистики
 ** можно решить через расширенную статистику https://blogs.oracle.com/optimizer/entry/extended_statistics
 В статистике создается псевдостолбец объединяющий несколько через перечисление, и при фильтре по этим столбцам будет использована статистика псевдостолбца.

Селективность соединения таблиц:

селективность = (число не Null строк на колонке t1 / число null строк t1) * (число не Null строк на колонке t2 / число null строк t2) / GREATEST( distinct t1.c1, distinct t2.c2 )

кардинальность соединения = кардинальность т1 (по отфильтрованным без null) * кардинальность т2 (по отфильтрованным без null) * селективность

т.е. в частном случае без null строк:
 селективность = 1 / GREATEST( distinct t1.c1, distinct t2.c2 )
 кардинальность = кардинальность t1 * кардинальность t2 / GREATEST( distinct t1.c1, distinct t2.c2 )

* если несколько условий содениения, то расчет селективности аналогичен п. "Расчет кардинальности для операторов"
* при соединении по диапазону <> или формулы (включая математические операции) используется фиксированная селективность = 5%
* если по соединяемым столбцам есть гистограмма, то селектисноть "GREATEST( distinct t1.c1, distinct t2.c2 )" учитывает пересечение распределение гистограмм

Стоимости соединения таблиц

стоимость NL = стоимость получения T1 + кардинальность Т1 * Стоимость одного обращения к Т2

стоимость HASH join = стоимость получения Т1 + стоимость получения Т2 + стоимость хэширования и сравнения.

Общие понятия:
1. для соединения HASH важна avg_col_len (средняя длина столбца в байтах), чтобы расчитать сколько займет хэш таблица в памяти, имеено по этому параметру выбирается начальная-хэшируемая Т1
2. Количество хэш групп = 0.8 x hash_area_size / (db_block_size * hash_multiblock_io_count)
20% размер hash_area_size резервируется под вспомогательные структуры
3. хэш таблица в Oracle это - хэш массив указателей на связанные списки данных

Если хэш целиком не влезает в память:
Хэширование левой таблицы:
* Левая таблица последовательно хэшируется. Если секция целиком не влезает в память, то блоки из связанного списка записываются на диск
* Минимум 1 блок в 8КБ выделяется под битовый массив принадлежности строк левой таблицы.
Массив используется для пробирования строк, если значение есть в таблице, то соотвествующий бит массива будет установлен в 1, иначе 0
Эта битовая маска облегчит быстрое пробирование правой таблицы без частого обращения к хэш таблице
* Когда левая таблица целиком прохэширована, происходит реорганизация секций, так чтобы максимальное число секций оказалось в памяти

Зондирование правой таблицы:
* Для каждой строки правой таблицы применятся хэш функция битового массива и проверяется, установлен ли соответствующий бит
** если бит = 0, то соответствия однозначно нет
** если бит = 1, и соответсвующая хэш секция в памяти, то происходит пробирование данных
** если бит = 1, но секция не целиком в памяти
Хэш значение правой таблицы записывается на диск или в память (если еще есть), сами данные не пробируется в левой (пропускается)

После первого прохода по правой таблице у нас есть полная информация о всех секция обеих сторон, о количестве строк, секций и распределении память/диск.

* Секция левой таблицы выгружается из памяти и берется следующая, которая целиком в памяти. Это может быть как секция из левой, так и из правой таблицы (swap joins)
* Т.к. данные о всех секциях уже есть, то пробируется не вся таблица целиком, а только соотвествующая секция другой таблицы

Стоимость такого соединения будет больше максимум в 3 раза от соединения в памяти, т.к. дополнительно повторно потребуется считывать как левую, так и правую таблицы.


Более плохой вариант, когда ни одна хэш секция не влезает в память целиком. Для полного пробирования так или иначе нужно просмотреть все значения в хэш секции.
Отличия:
* выбирается секция с максимальным числом строк в памяти и последовательно зондируется правая таблица.
* Если соответствие найдено, то данные выводятся в поток, если нет - то строка пропускается, а ее хэш записывается на диск.
* Когда правая таблица целиком пройдена, часть секции левой таблицы выгружается из памяти и загружается с диска в память следующая часть секции левой таблицы
* Соответствующая секция правой таблицы зондируется заново (исключенные ранее записи) и т.д.

В этом случае число чтений возрастает в разы, т.к. кроме перевыгрузки секции целиком (соединение в один проход) нужно перегружать и части одной секции и считывать заново правую таблицу для новой порции.
Такое соединение называется - в несколько проходов, т.к. одна секция пробируется по несколько раз.
Такой подход малоэффективен и лучше бы подошло рекурсивное хэширование: когда секция целиком не влезает в память, она бьется еще на более мелкие части новой хэширующей функцией, пока целиком не влезет в память (но в Oracle сделано не так).
Подробное описание hash join можно почитать в статье Oracle: реализация hash соединения


стоимость соединения слиянием (merge):
для соединения слиянием нужно, чтобы обе выборки были отсортированы. Т.е. большую часть стоимости дает сортировка, а поиск совпадений в подготовленных выборках уже мало влияет на стоимость.

для сортировки слиянием, если есть дубли нужна вспомогательная таблица, куда будут сохранятся промежуточные результаты, т.к. после нахождения совпадения эта запись исключается из поиска. В это случае стоимость такого соединения очень растет и очень редко используется oracle.

Для сортировки выборок используется разновидность внешней сортировки

вся выборка бьется на части, которые могут полностью войти в отведенную память. Каждый кусок быстро сортируется в памяти. После этого N отсортированных кусков последовательно читаются с диска и собираются в одну отсортированную выборку. За один проход сливается 2 выборки, т.е. если таблица большая, а памяти мало, то потребуется очень много проходов с чтением/записью выборок с диска.
Про алгоритм сортировки слиянием подробней можно почитать тут

Кардинальности set операторов

union[all] - кардинальности складываются
Про Union стоит отдельно заметить, что oracle неявно делает distinct, после чего объединяет выборки. Но это никак не сказывается на кардинальность.
Так что желательно использовать DISTINCT в minus/union, план от этого не меняется, oracle и так это делает, но в этом случае правильно оценивается стоимость и кардинальность

minus - берется меньшая кардинальность

intersect - берется разница кардинальностей.

Определение последовательности соединения таблиц

Стартовой таблицей выбирается таблица с наименьшей кардинальностью (не стоимостью) после фильтрации.
если таблиц не очень много, то перебираются все варианты (факториал перестановок), если таблиц больше max_permutation, то используется жадный алгоритм поиска субоптимального плана. Если стоимость получается большой, то oracle дополнительно пробует менять стартовые таблицы.
Все это можно наблюдать в трассировке 10053.