- Общие понятия: селективность, кардинальность, стоимость.
- Стоимость табличного доступа и системная статистика
- Стоимость индексного доступа.
- Гистограммы.
- Проблемы расчета селективности: Секционированные таблицы, значения поумолчанию, текстовые ключи, bind переменные и зависимые/коррелируемые столбцы.
- Селективность соединения таблиц
- Стоимость соединения таблиц: Nested Loops, Hash Join, Merge join
- Стоимость внешней сортировки.
- Кардинальности set операторов.
- Определение последовательности соединения таблиц.
Общие понятия
Селективность = (макс значение - мин значение отобранных данных)/(макс значение - мин значение всех данных)
в общем случае = отобранный интервал / весь интервал
Весь интервал определяется на основе статистики таблицы, это столбец 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.
>> столбец destiny - разряженность: обратный показатель от кол-ва уникальных значений = 1/num_distinct
ОтветитьУдалитьDensity