вторник, 27 декабря 2016 г.

Oracle: Lru буферный кэш

Список статей о внутреннем устройстве Oracle:

Следующий аспект больших бд, у которых все данные не способны поместиться в памяти - кеширование частоиспользуемых данных в памяти.

В Oracle для кэширования используется модифицированный алгоритм LRU.

Lru (least recent used) кэш — буфер в памяти для быстрого доступа к часто используемым элементам.
Lru кэш представляет из себя двусвязный список (2Linked List), вначале которого наиболее часто используемые элементы, а в конце - редко.
Для ускорения произвольного доступа над списком создается хэш массив (Hash Map) ссылок на элементы двусвязанного списка:

Раньше я уже описывал lru кэш со стороны разработчика бд: Ядро oracle, сегодня копнем немного глубже, с кодом lru кэша на java.


Двусвязный список с дополнительным счетчиком обращений для хранения LRU:
//двухсвязный список
class Node<Value> {
 //ключ списка
 int key;
 
 //абстрактное значение
 Value value;
 
 //счетчик обращений к элементу
 int cnt;
 
 //указатель на предыдущий элемент
 Node prev;
 
 //указатель на следующий элемент
 Node next;
 
 //элемент был перемещен из конца списка в начало
 boolean swaped;
 
 public Node(int key, Value value){
  this.key = key;
  this.value = value;
  this.cnt = 1;
  this.swaped = false;
 }

При обращении к элементу списка увеличиваем счетчик обращений "cnt":
 //получить значение из списка
 public Value getValue() {
  //увеличиваем счетчик обращений
  cnt++;
  //сбрасываем признак смещений, если элемент был прочитан
  this.swaped = false;
  
  return value;
 }
 
 //установить значение
 public void setValue(Value val) {
  this.value = val;
  //также увеличиваем счетчик
  cnt++;
  //сбрасываем признак смещений, если элемент был перезаписан
  this.swaped = false;
 } //setValue
} //Node

Класс Lru дополняется хэш массивом "map" в котором для ускорения доступа количество хэш секций (capacity) >= числу элемнтов в списке;
И стандартные указатель на начало "head" и конец "end" списка.
Дополнительное изменение в Oracle - указатель на середину списка "cold", где начинаются холодные данные.
public class Lru<Value> {
 
 //доступной число элементов в кэше
 int capacity;
 
 //хэш массив элементов для быстрого доступа
 HashMap<Integer, Node> map;
 
 //указатель на начало (горячие элементы)
 Node head = null;
 
 //указатель на середину (начало холодных элементов)
 Node cold = null;
 
 //указатель на конец (самый редкоиспользуемый)
 Node end = null;
 
 //число элементов в кэше
 int cnt;
 
 
 //конкструктор с числом элементов в кэше
 public Lru (int capacity) {
  this.capacity = capacity;
  
  //хэш массив создаем с нужным числом секций = загруженности
  map = new HashMap<Integer, Node>(capacity);
 }

Для получения элемента используется хэш массив, без последовательного просмотра всего списка:
 //получить элемент из кэша
 public Value get(int key) {
  //быстрое извлечение их хэш массива
  if(map.containsKey(key)) {
   //и инкремент счетчика обращений
   return (Value) map.get(key).getValue();
  }
  
  return null;
 } //get

Если элементов в списке меньше размер буфера, то используется обычный алгоритм LRU - новые элементы добавляются в начало списка, а старые вытесняются вправо, пока не дойдут до конца списка.
 //места достаточно, добавляем вначало
 protected void addHead(Node n) {
  
  //первый элемент
  if(this.head == null) {
   //устанавливаем начало и конец = элементу
   this.head = n;
   this.end = n;
  } else {
   
   //вставляем вначало
   
   //следующий для нового элемента = начало списка
   n.next = this.head;
   
   //предыдущий для начала списка = новый элемент
   this.head.prev = n;     
   this.head = n;
   
   //второй элемент
   if(this.end.prev == null) {
    //предыдущий для конца = новый элемент
    this.end.prev = n;
   }
  }    
  
  //устанавливаем середину
  if(cnt == capacity / 2) {
   this.cold = n;
  }
  
  //счетчик элементов + 1
  cnt++;
 } //addHead

У этого подхода есть существенный минус: редкоиспользуемый элемент может случайно вытеснить из списка популярный блок, который не вызывался небольшой период времени, за который он успел сместиться до конца.
Для решения этой проблемы Oracle применяет 2 подхода:
1. Если в конце элемент со счетчиком обращений = 1, то он открепляется от списка, а новый блок помещается в среднюю точку cold.
Для этого ссылки соседей открепляются друг от друга и перенацеливаются на новый блок, который становится новой серединой.
 //удаляем конца списка
 private void delEnd() {
  //из хэш массива
  map.remove(this.end.key);
  
  //и делаем концом списка = предыдущий элемент
  this.end = this.end.prev;
  this.end.next = null;
 } //delEnd
 
 //вконце малопопулярный блок
 protected void addColdUnPop(Node n) {
  //удаляем конец
  delEnd();
  
  //у старой середины изменяем счетчик на 1
  if(this.cold.swaped) {
   //если смещенный элемент не был ни разу считан 
   //и дошел до середины, 
   //то сбрасываем счетчик в 1
   this.cold.cnt = 1;
   this.cold.swaped = false;
  }
  
  //новый блок в середину = cold
  
  //проставляем ссылки у нового элемента
  n.prev = this.cold.prev;
  n.next = this.cold;
  
  //и разрываем связи и соседей
  n.prev.next = n;
  n.next.prev = n;
  this.cold = n;
 } //addColdUnPop

2. Если в конце популярный элемент со счетчиком > 1 , тогда последний блок открепляется, счетчик обращений делится на 2 и этот блок перемещается в начало списка.
Такой элемент помечается флагом swaped = true, который сбрасывается при любом последующем обращении к элементу.
Это предотвращает случайное вытеснение популярного блока из памяти.
Середина списка также смещается влево, одновременно делая число обращений = 1 у новой элемента-середины, если к ней никто не обращался за время смещения от начала до середины (swaped = true).
Новый блок помещается в центр списка cold.
 //вконце популярный блок
 protected void addColdPop(int key, Value value) {
  //делим счетчик на пополам
  this.end.cnt = this.end.cnt / 2;  
  
  //открепляем конец
  Node n = this.end;
  
  //удаляем конец
  delEnd();
  
  //конец перемещаем в начало
  n.prev = null;
  n.next = this.head;
  this.head.prev = n;     
  this.head = n;
  
  //помечаем, что элемент был перемещен из конца в начало
  this.head.swaped = true;
  
  //смещаем середину на 1 влево
  if(this.cold.swaped) {
   //если смещенный элемент не был ни разу считан 
   //и дошел до середины, 
   //то сбрасываем счетчик в 1
   this.cold.cnt = 1;
   this.cold.swaped = false;
  }
  this.cold = this.cold.prev;
  
  //рекурсивно пытаемся вставить вконец
  //TODO: если все популярные? то вставка будет идти очень долго
  this.set(key, value);
 } //addColdPop


События ожиданий связанные с наполнением буферного кэша:
* Buffer busy waits / read by other session - сессия пытается считать блок, который сейчас читается в кэш или модифицируется в кэше другой сессией.

Полный исходный код можно посмотреть тут: https://github.com/pihel/java/blob/master/cache/lru.java

среда, 14 декабря 2016 г.

Oracle: вероятностный Bloom filter

Список статей о внутреннем устройстве Oracle:

Более редкая разновидность хэширования данных и вероятностной фильтрации данных - bloom filter
Раньше я уже описывал bloom filter в параллельных запросах со стороны разработчика бд: Oracle: оптимизация параллельных запросов, сегодня копнем немного глубже, с кодом bloom filter на java.


Bloom filter — это вероятностная структура данных, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.
Фильтр Блума может использовать любой объём памяти, заранее заданный пользователем, причём чем он больше, тем меньше вероятность ложного срабатывания.

Пример фильтра Блума с 18 бит в карте и 3 функциям хэширования, хранящего множество {x, y, z}. Цветные стрелки указывают на места в битовом массиве, соответствующие каждому элементу множества. Этот фильтр Блума определит, что элемент w не входит в множество, так как один из соответствующих ему битов равен нулю.

Основное предназначение - предфильтрация данных в источнике до передачи их в базу данных.
Принцип применения блум фильтра при join:
1. Левая таблица читается с диска и фильтруется (plan line = 3)
2. На основе левой таблицы создается битовая карта блум фильтра (:BF0000 plan line = 2)
3. Блум фильтр передается в источник правой таблицы (:BF0000 plan line = 4)
4. Строки правой таблицы фильтруются через блум фильтр (:BF0000 plan line = 5 - storage(SYS_OP_BLOOM_FILTER(:BF0000,"R"."L_ID")))
5. В бд передается уже частично отфильтрованная правая таблица
6. Выполняется join (plan line = 1)
create table l as select level as id, 'name_' || level as title, rpad('*', level) as pad from dual connect by level <= 50;
create table r as select rownum as id, mod(rownum, 50) as l_id, rpad('*', 20) as pad 
from (select * from dual connect by level <= 1000 ) join (select * from dual connect by level <= 1000 ) on 1=1;

begin
DBMS_STATS.GATHER_TABLE_STATS(USER, 'L');
DBMS_STATS.GATHER_TABLE_STATS(USER, 'R');
end;

explain plan for
select * 
from l
join r on l.id = r.l_id
WHERE l.title = 'name_5';

select * from table(dbms_xplan.display(format=>'ALLSTATS ALL ADVANCED'));

Plan hash value: 3967001914
 
----------------------------------------------------------------------------------------
| Id  | Operation                   | Name    | E-Rows |E-Bytes| Cost (%CPU)| E-Time   |
----------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |         |  20000 |  1308K|   184  (20)| 00:00:01 |
|*  1 |  HASH JOIN                  |         |  20000 |  1308K|   184  (20)| 00:00:01 |
|   2 |   JOIN FILTER CREATE        | :BF0000 |      1 |    38 |     2   (0)| 00:00:01 |
|*  3 |    TABLE ACCESS STORAGE FULL| L       |      1 |    38 |     2   (0)| 00:00:01 |
|   4 |   JOIN FILTER USE           | :BF0000 |   1000K|    27M|   171  (15)| 00:00:01 |
|*  5 |    TABLE ACCESS STORAGE FULL| R       |   1000K|    27M|   171  (15)| 00:00:01 |
----------------------------------------------------------------------------------------
 
Query Block Name / Object Alias (identified by operation id):
-------------------------------------------------------------
 
   1 - SEL$58A6D7F6
   3 - SEL$58A6D7F6 / L@SEL$1
   5 - SEL$58A6D7F6 / R@SEL$1
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - access("L"."ID"="R"."L_ID")
   3 - storage("L"."TITLE"='name_5')
       filter("L"."TITLE"='name_5')
   5 - storage(SYS_OP_BLOOM_FILTER(:BF0000,"R"."L_ID"))
       filter(SYS_OP_BLOOM_FILTER(:BF0000,"R"."L_ID"))

Детальное описание с кодом на java:
1. Блум фильтр состоит из массива бит произвольной длинны. В моем случае под битовый массив выделена переменная long в 64 бита:
package Hash;

import java.util.concurrent.ThreadLocalRandom;

public class BloomFilter {

  //long переменная в 64бита под битовый массив
  private long data;
  
  //битов в битовой карте = числу битов в long
  private int bit_array_size = Long.SIZE;

2. Определяется hash_num функций хэширования. На входе функции произвольная строка, на выходе номер бита в битовой карте для установки в 1.
  //примесь для случайного хэширования
  private int seed = ThreadLocalRandom.current().nextInt(1, bit_array_size);
  
  //хэшировани = номер бита в битовом массиве
  public long hashCode(String s, int hash_num) {
    long result = 1;
    
    //для каждого байта в строке
    for (int i = 0; i < s.length(); ++i) {
      //применяем хэш функцию под номером hash_num и обрезаем по маске
     
     //простая хэш функция = ascii значение буквы * примесь * номер функции * хэш от предыдущей функции & обрезка по маске
      //1 = (1 * 1 + 58)
      //1 = ( 0001 * 0001 + 11 0001 ) & 1111 1111 1111 1111 
      result = ((hash_num + seed) * result + s.charAt(i)) & this.hashMask;
    }

3. Устанавливаем биты в битовой карте для hash_nums хэш функций
  //установить index бит в битовой карте
  public void setBit(long index) {
   //= битовая карта OR 1 смещенное влево на index
   this.data = this.data | (1L << index );
  } //setbit
  
  //добавить элемент в блум фильтр
  public void add(String s) {
    //++ счетчик элементов
    cnt++;
    //для каждой хэш функции
    for(int i = 1; i <= hash_nums; i++) {
      //расчитаем номер индекса в битовой карте и установим его
      long index = hashCode(s, i);
      setBit(index);
    }
  } //add

4. Обратная операция - тестирование строки на вероятное наличие элемента в блум фильтре: хэшируем и проверяем бит в блум фильтре
  //получить значение бита на index месте
  public long getBit(long index) {
   //=битовая карта смещенная вправо на index мест (>>> пустые места справа заполняются 0)
   // & 01 - проверка только крайнего правого бита (все остальные игнорируются)
   return ( this.data >>> index ) & 1;
  } //getBit
  
  //проверка наличия элемента в блум фильтре
  public boolean test(String s) {
 //для каждой хэш функции
    for(int i = 1; i <= hash_nums; i++) {
      //определяем номер бита в битовой карте
      long index = hashCode(s, i);
      
      //если хотябы одна проверка не прошла - элемента нет
      if( getBit(index) == 0L ) return false;
    }
    
    //иначе элемент вероятно есть
    return true;
  } //test

Очевидно, чем больше битовая карта в блум фильтре, тем точней результат - меньше ложных срабатываний.
Зависимость определяется формулой:

, где n — предполагаемое количество элементов хранящихся в фильтре-множестве, p — вероятность ложного срабатывания, m - число бит в карте

  //вероятность ложного срабатывания
  public double getFalsePossb() {
   if(cnt == 0) return 0;
   return 1 / Math.pow(Math.E, bit_array_size * Math.log(2) * Math.log(2) / cnt );
  } //getFalsePossb

Вероятность ложного срабатывания от числа бит в карте и кол-ва элементов:


Также использование нескольких функции хэширования дает преимущество при достаточном размере блум фильтра:
  //оптимальное число функций хэширования
  public int getOptimalFncCnt() {
   if(cnt == 0) return 1;
   return (int)Math.ceil( bit_array_size / cnt * Math.log(2) );
  } //getOptimalFncCnt

График вероятности ложного срабатывания от размера массива и числа функций хэширования:

Практическое применение Bloom фильтра в Oracle:
* Partition pruning - усечение просматриваемых партиций
 На основе фильтра левой таблицы выбираются секции для сканирования из правой, что позволит не сканировать таблицу целиком.
* RAC - уменьшение сетевого трафика между кластерными нодами
 Для уменьшения сетевого взаимодействия между кластерными нодами, если левую таблицу читает 1 нода, а правую нода 2.
 Применение блум фильтра уменьшает размер пересылаемых данных правой таблицы из ноды 2 в ноду 1 до выполнения соединения.
* Exadata или Map reduce движок в качестве источника данных
 Массовая параллельная обработка внутри exadata проходит быстрей, чем аналогичная операция внутри бд Oracle.
 Из-за этого при наличии exadata Oracle стремится произвести максимальное число фильтрации в источнике до передачи в базу.
* In Memory хранилище данных
 Аналогично exadata, inmemory движок может производить фильтрацию внутри себя и это будет быстрей, чем выполнять join на полном наборе данных.
 При наличии таких данных Oracle стремится произвести максимум фильтрации до передачи данных в бд.
* Parallel - параллельные запросы
 Взаимодействие параллеьлных поток происходит через координатор и если 1 поток читает левую таблицу, а 2 поток - правую, то выгодней и быстрей отфильтровать правую таблицу блум фильтром и передать в первый поток уже отфильтрованные данные.
* Гетерогенные запросы через дблинк (возможно)
 Сетевое взаимодействие очень дорогое по сравнению с работой с памятью и даже диском. Из-за этого было бы выгодно отфильтровать правую таблицу на удаленной бд до ее передачи в нашу.

Полную реализацию блум фильтра можно видеть здесь: https://github.com/pihel/java/blob/master/Hash/BloomFilter.java

суббота, 3 декабря 2016 г.

Oracle: реализация hash соединения

Список статей о внутреннем устройстве Oracle:

Следующий аспект бд - хэширование данных
Раньше я уже описывал hash join со стороны разработчика бд: Основы стоимостной оптимизации join, сегодня копнем немного глубже, с кодом hash join на java.


Хэширование - преобразование массива входных данных произвольной длины в выходную битовую строку фиксированной длины, выполняемое определённым алгоритмом.
Преимуществом массива фиксированной длины является константное время доступа к его элементам из-за размещения ограниченного набора в процессорном кэше.
Самая большая проблема - это выбор хэширующей функции, которая давала бы минимум коллизий (одинаковых значений хэш функции для разных ключей массива).
Идеальная хэширующая функция не должна давать коллизий, но в реальности такую функцию сложно получить.
В моем случае алгоритмом хэширование я выбрал остаток от деления. Число в знаменателе даст нам такое же число элементов в хэш массиве.
Для разрешения проблемы коллизий используется 2 подхода, оба из них в зависимости от числа коллизий для доступа к нужному элементу дают от 1 до N обращений:

1. Открытая адресация
Коллизии размещаются в томже хэш массиве, но смещаются вправо, пока не найдется свободное место.

Пример:
Массив из элементов: 1, 11, 2, 3
Хэширующая функция: остаток от деления на 10
Результирующий хэш массив:
[1] = 1 (остаток от деления 1 на 10 = 1, т.к. ключ 1 был пустой, то он и занимается)
[2] = 11 (остаток от деления 11 на 10 = 1, это коллизия для предыдущего элемента. Т.к. ключ 1 занят, то берется следующий пустой справа = 2)
[3] = 2 (остаток от деления = 2, т.к. элемент занят, то берется следующий = 3)
[4] = 3 (и т.д.)

Реализацию на java можно посмотреть здесь.

2. Метод цепочек
Хэш таблица содержит список коллизий. Число элементов хэш таблицы фиксировано = числу различных вариантов хэширующей функции.
Пример на том же массиве и той же хэширующей функции:
[1] = 1 -> 11
[2] = 2
[3] = 3
[4] = 4

3. Метод красно-черного дерева
В случае большого числа коллизий, когда все элементы попадают в одну хэш секцию, для хранения данных секции целесообразно использовать красно-черное дерево, замен списка во 2 методе. В этом случае поиск элемента будет осуществляться за логарифмическое время, вместо линейного в списке.

Плюсы и минусы подходов:
Сравниваемое свойство Цепочки Открытая адресация
Разрешение коллизий Используются дополнительные списки Хранится в самом хэш массиве
Использование памяти Дополнительная память для указателей в списке.
В случае неудачной хэш функции, если все элементы легли в один элемент массива (хэш секцию), то размер памяти будет почти в 2 раза больше, т.к. необходимая память под указатели будет равна памяти под ключи.
Нет доп. расходов
Зависимость производительности от заполненности таблицы Прямо пропорционально значению = число элементов / кол-во хэш секции таблицы число элементов / ( кол-во хэш секции таблицы - число элементов )
Возможность записи числа элементов больше размера хэш таблицы Да, за счет записи коллизий в список Нет, т.к. колллизии храняться в томже массиве
Простота удаления Да, удаляется элемент из списка Нет, пустое место нужно помечать удаленным, а не очищать физически. Т.к. при вставке ищутся пусты места справа, что может сломать последовательность
Использование кэша процессора Нет (переходы по ссылке) Да (Все данные рядом)

Детали реализации Oracle:
Хэширование цепочками наиболее понятное, но оно же дает худшую производительность, т.к. не использует кэш процессора из-за постоянных переходов по ссылке.
По этому все нагруженные реализации используют Hash таблицы с открытой адресацией, где все данные лежат рядом и используют кэш сопроцессора.


Слева графически представлен механизм поиска в хэш таблице Oracle.

Изменения в реализации хэш таблиц Oracle:
* Хэш таблица над таблицей бд может быть сколь угодно большой и она может не поместиться в памяти
* битовая карта над данными в хэш таблице, если соответствующий бит таблицы установлен, то элемент есть в хэш таблице, иначе строку можно даже не искать.


Когда Oracle выбирает соединение хэшированием:
В основе выбора способ лежит стоимостная оценка:
Стоимость соединения вложенными циклами (NL) = стоимость получения T1 + кардинальность Т1 * Стоимость одного обращения к Т2
Стоимость соединения хэшированием (hash) = стоимость получения Т1 + стоимость получения Т2 + стоимость хэширования и сравнения.

Исходя из этих формул можно сделать вывод, что hash соединение выгодней, когда :
* Нужно считать большой объем данных для соединения или на правой таблице таблице нет индекса.
Многоблочное считывание при hash join выгодней, чем последовательное одноблочное сканирование индекса правой таблицы.
* Параллельное выполнение запросов - хэширование и поиск в хэш таблице хорошо распараллеливается, поиск по связанному списку индекса практически не параллелится.

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


Рассмотрим подробней вариант, однопроходного поиска в хэш таблице, т.е. когда объема памяти достаточно, чтобы целиком разместить хэш секцию.
Для простоты будет использоваться Hash таблица цепочками.

вторник, 15 ноября 2016 г.

Oracle: реализация btree индекса

Список статей о внутреннем устройстве Oracle:

Следующий важный аспект бд - индексирование данных в таблицах.
Раньше я уже описывал индексирование со стороны разработчика бд: http://blog.skahin.ru/2015/04/oracle.html, сегодня копнем немного глубже, с кодом btree индекса на java.


B+Tree - Дерево поиска. С точки зрения внешнего логического представления, сбалансированное, сильно ветвистое дерево во внешней памяти.
Дерево ( BPTree ) состоит из корня ( root ), внутренних узлов ( INode ) и листьев ( LNode ), корень может быть либо листом, либо узлом с двумя и более потомками.

Сбалансированность означает, что длина любых двух путей от корня до листьев совпадает.
Ветвистость дерева — это свойство каждого узла дерева ссылаться на большое число узлов-потомков ( Node[] children ).

С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, то есть каждому узлу дерева соответствует блок внешней памяти (блок / страница). Внутренние и листовые страницы обычно имеют разную структуру.
При этом данные хранятся только в последовательно связанных листьях ( LNode.next ), а в ветвях только ссылки на листья дерева ( INode.children ).



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

Перейдем к особенностям реализации Oracle:

1. Т.к. бд хранит и считывает данные в блоках/страницах, то размер листа/ветви = размеру блока. ( rows_block )

2. Вставка
При достижении максимального числа элементов в блоке ( rows_block ) , лист должен разбиться на 2 части ( BPTree.Insert, LNode.Insert , INode.Insert ), а копия среднего элемента перейти на ветвь выше ( Split ) рекурсивно (максимальное число ветвлений = 24. В Oracle этот параметр называется blevel (BPTree.getBLevel) = height - 1 )
В Oracle реализован особенный алгоритм: если вставка элемента идет в крайний правый блок индекса (Node.last), то разделение идет в соотношении 90/10.
Это значительно снижает размер индекса при вставке последовательных данных, т.к. данные в блоках получаются плотно упакованы.
Такая ситуация часто бывает на первичном ключе, генерируемый последовательностью.
Если вставка идет в середину индекса, то алгоритм стандартный - блок сплитится в соотношении 50/50, что приводит к появлению пустых мест и физическому разрастанию индекса на диске.

Пример индекса с числом элементов в блоке = 3:

 * Вставка последовательных данных: {1, 2, 3, 4, 5, 6, 7, 8, 9}
переполняющий элемент сразу идет в правый новый блок, не разделяя левый на 2 части:
1
2
3
 . > 4
4
5
6
 . > 7
7
8
9
( > - ветвь, . - высота ветви -- вывод функции dump )
Всего 3 листовых блока и высота дерева = 2

 * Вставка данных в обратном порядке:
Массив из 3 элементов постоянно разбивается на 2 части:
1
2
3
 . > 4
4
 . > 5
5
 .  . > 6
6
 . > 7
7
 .  . > 8
8
 . > 9
9

Хороший визуализатор b+tree дерева можно видеть тут

Тут ситуация хуже, индекс сильно разряжен: 7 листовых блоков и высота дерева = 3.
Индекс будет почти в 2 раза больше весить на диске и для обращений к нему нужно будет делать 3 чтения с диска, вместо 2 при последовательной.

Стоит заметить, что последовательная вставка в индекс это не всегда хорошо.
Если вставка преобладает перед чтением, то insert в разные части индекса лучше, чем последовательная в один блок. Т.к. это обеспечивает большую конкуренцию за общий ресурс и в итоге приведет к buffer busy wait. Специально для перемешивания данных используются реверсивные индексы (http://blog.skahin.ru/2015/04/oracle.html).

3. Поиск элемента
* начинаем с корня дерева (считываем его с диска) ( BPTree.indexScan )
* в блоке ветви бинарным поиском ищем элемент = искомому или первый больше его, если искомого нет в ветви (INode.getLoc)
* если нашли, то спускаемся налево, иначе если искомый элемент больше максимального в блоке ветви, то двигаемся направо (считывание с диска) (inner.children[idx])
* рекурсивно повторяем N раз = высота дерева - 1, пока не дойдем до листа (считывание с диска) (LNode leaf)
* в упорядоченном массиве блока листа бинарным поиском (считывание с диска) (leaf.getLoc)
Итого элемент будет найден за число считываний с диска = высоте дерева. Затраты CPU = высота дерева * log2(число строк в блоке)

3. При удалении данных из индекса, в целях ускорения, элемент физически не удаляется, а лишь помечается удаленным. Тем самым индекс не становится меньше весом.
Для устранения эффектов из п. 2 и 3 индекс необходимо периодически ребилдить rebuild

4. Операции min/max поиска также осуществляются за константное время = высоте дерева (операция index min/max scan) ( BPtree.getMin / BPtree.getMax )

5. Т.к. данные упорядоченные, то поиск нужного элемента внутри блока происходит с помощью бинарного поиска (LNode.getLoc).
Так что если сравнивать время доступа к таблице в 1 блок и к индексу в 1 блок: оба варианта дают 1 физическое чтение с диска, но поиск по индексу будет быстрей, т.к. для поиска элемента в упорядоченном массиве индекса log2(N) операций, а в неупорядоченной таблице - это всегда линейный поиск со стоимостью = N

6. Упорядоченность данных также позволяет искать данные по диапазону (BPTree.rangeScan):
* Находим стартовый элемент (Node.getLoc)
* Двигаемся по блоку вправо (while(leaf != null))
* Если дошли до конца блока, то переходим по ссылке на следующий ( leaf = leaf.next )
* доходим до элемента большего правой границы диапазона ( leaf.keys[i].compareTo(to_key) > 0 )

Это операция последовательного чтения массива, к сожалению, она никак не может быть распараллелена.

Также если в индексе после столбца, по которому идет сканирование по диапазаону, есть еще столбец, то он не сможет быть использован для доступа к нужному блоку индекса для старта, только для дофильтрации диапазона. Такой метод не уменьшит число физических чтений блоков индекса с диска.

7. null Значения
Oracle в отличии от других бд не хранит в индексе полностью пустые значения. Это значит что при поиске "idx_cold is null" не будет использоваться.
Это ограничение можно обойти, если создать индекс из 2 полей: нужного и любого другого. В качестве второго поля можно исопльзовать даже константу.
К примеру:
create index idx on tbl(col, 1);

В этом случае все значения колонки col, включая null, будут храниться в индексе и будет работать "col is null" сканирование.

8. index scip scan
9. Сжатые индексы
Не релизовывалось в данном классе.
Описание см. http://blog.skahin.ru/2015/04/oracle.html

10. Структура блока из 2 столбцов.
[ Flag Byte | Lock Byte | Length Byte 1 | Col1 | Length Byte 2  | Col 2 | Length Byte | rowid ]

Т.е. фактической разницы между индексом из 1 или 2 и более столбцов особо разницы нет.

12. Фактор кластеризации - соответствие последовательности элементов в индексе элементам в таблице. (BPtree.getClusterFactor)


Наилучший вариант, когда данные в таблице отсортированы на техже столбцах, что в индексе ( не важно прмямую или обратную). Тогда фактор кластеризации будет равен числу блоков в таблице.
Если же наоборот, то для чтения каждого элемента в индексе нужно считывать новый блок таблицы с диска, тогда фактор кластеризации = числу строк таблицы.

13. Index full scan - полное сканирование индекса (BPtree.fullScan)

14. Index Desc Scan - сканирование в обратном порядке
Индекс строится в прямом порядке и имеет ссылку в листовом блоке только на следующий.
То в случае запроса:
select * from tbl where idx_col between 7 and 9 order by idx_col desc;

Индекс также фильтруется как в п. 6, но обращения к таблице по rowid идет в обратном порядке, т.е. данные повторно не сортируются (order by idx_col desc), т.к. строки уже возвращаются из индекса в обратном порядке.


Исходный код B+дерева на java:
package BPTree;

import java.util.concurrent.ThreadLocalRandom;

public class BPTree<Key extends Comparable, Value> {
 //https://en.wikibooks.org/wiki/Algorithm_Implementation/Trees/B%2B_tree

 //корень дерева
 private Node root;
 //кол-во строк в блоке
 private final int rows_block;
 //высота дерева
 private int height = 1;
 //кол-во строк в индексе
 private int cnt = 0;

 public BPTree(int n) {
  rows_block = n;
  root = new LNode();
  
  //первый блок и последний
  root.last = true;
 } //BPTree

 public void insert(Key key, Value value) {
  Split result = root.insert(key, value);
  
  if (result != null) {
   //разделяем корень на 2 части
   //создаем новый корень с сылками на лево и право
   INode _root = new INode();
   _root.num = 1;
   _root.keys[0] = result.key;   
   _root.children[0] = result.left;
   _root.children[1] = result.right;
   
   //уровень текущей ветки = высота предыдущей + 1
   _root.level = result.level + 1;
   root = _root;
   
   //повышаем счетчик высоты дерева
   height++;
  }
 } //insert

 //index scan
 public Value indexScan(Key key) {
  Node node = root;
  //спускаемся по внутренним веткам, пока не дойдем до листа
  while (node instanceof BPTree.INode) {
   INode inner = (INode) node;
   int idx = inner.getLoc(key);
   node = inner.children[idx];
  }

  //спустились до листа
  LNode leaf = (LNode) node;
  int idx = leaf.getLoc(key);
  
  //нашли ключ элемента в блоке
  //если последний элемент, то дополнительно проверим значение
  if (idx < leaf.num && leaf.keys[idx].equals(key)) {
   return leaf.values[idx];
  } else {
   return null;
  }
 } //indexScan
 
 //index min scan
 public Value getMin() {
  Node node = root;
  //спускаемся по внутренним веткам налево, пока не дойдем до листа
  while (node instanceof BPTree.INode) {
   INode inner = (INode) node;
   node = inner.children[0];
  }
  if( node.num == 0 ) return null;

  //спустились до листа
  LNode leaf = (LNode) node;
  return leaf.values[0];
 } //getMin
 
 //index max scan
 public Value getMax() {
  Node node = root;
  //спускаемся по внутренним веткам направо, пока не дойдем до листа
  while (node instanceof BPTree.INode) {
   INode inner = (INode) node;
   node = inner.children [inner.num];
  }
  if( node.num == 0 ) return null;

  //спустились до листа
  LNode leaf = (LNode) node;
  return leaf.values[leaf.num - 1];
 } //getMax
 
 //index range scan - поиск по диапазону
 public Value[] rangeScan(Key from_key, Key to_key) {
  Node node = root;
  //спускаемся по внутренним веткам, пока не дойдем до листа
  while (node instanceof BPTree.INode) {
   INode inner = (INode) node;
   int idx = inner.getLoc(from_key);
   node = inner.children[idx];
  }

  //спустились до листа
  LNode leaf = (LNode) node;
  int idx = leaf.getLoc(from_key);
  
  //нашли ключ элемента в блоке
  if (idx < leaf.num && leaf.keys[idx].compareTo(from_key) >= 0) {
   Value[] arr = (Value[]) new Object[cnt];
   
   //двигаемся вправо, пока не найдем правую границу
   int cnt_arr = 0;
   do {
    //стартуем с найденного элемента
    for(int i = idx; i < leaf.num; i++) {
     if(leaf.keys[i].compareTo(to_key) > 0) {
      
      //возвращаем только нужное число элементов
      Value[] _arr = (Value[]) new Object[cnt_arr];
      System.arraycopy(arr, 0, _arr, 0, cnt_arr);
      arr = null;
      return _arr;
     }
     
     arr[cnt_arr] = leaf.values[i];
     cnt_arr++;
    }
    //последующие блоки читаем с 0
    idx = 0;
    
    leaf = leaf.next;
   } while(leaf != null);
   
   Value[] _arr = (Value[]) new Object[cnt_arr];
   System.arraycopy(arr, 0, _arr, 0, cnt_arr);
   arr = null;
   return _arr;
  }
  
  return null;
 } //rangeScan
 
 //index full scan
 public Value[] fullScan() {
  Node node = root;
  //спускаемся по внутренним веткам направо, пока не дойдем до листа
  while (node instanceof BPTree.INode) {
   INode inner = (INode) node;
   node = inner.children [0];
  }
  if( node.num == 0 ) return null;
  
  Value[] arr = (Value[]) new Object[cnt];
  //спустились до листа
  LNode leaf = (LNode) node;
  
  //последовательно идем по листам слева направо
  int cnt_arr = 0;
  do  {
   System.arraycopy(leaf.values, 0, arr, cnt_arr, leaf.num);
   
   cnt_arr = cnt_arr + leaf.num;   
   leaf = leaf.next;
  } while(leaf != null);
  
  return arr;
 } //fullScan
 
 
 //blevel - высота дерева -1
 public int getBLevel() {
  return height - 1;
 } //getBLevel
 
 public int getCnt() {
  return cnt;
 } //getCnt
 
 //фактор кластеризации
 //идеально = число строк / число строк в блоке
 //плохо = число строк
 public int getClusterFactor() {
  int cluster_factor = 0;
  int prev_block = 0;
  int cur_block = 0;
  
  Object arr[] = new Integer[cnt];
  arr = fullScan();
  
  for(int i = 0; i < arr.length; i++) {
   
   int k_rowid = (Integer)arr[i];
   
   cur_block = k_rowid / rows_block;
   
   if(prev_block != cur_block) {
    cluster_factor++;
   }
   prev_block = cur_block;
  }
  
  return cluster_factor;
 } //getClusterFactor

 public void dump() {
  System.out.println("blevel = " + getBLevel());
  System.out.println("cnt = " + getCnt());
  System.out.println("min[k] = " + getMin());
  System.out.println("max[k] = " + getMax());
  System.out.println("--------------------");
  root.dump();
  System.out.println("--------------------");
 }

 //абстрактный класс блока: лист или ветвь
 abstract class Node {
  //кол-во элементов в блоке
  protected int num;
  
  //элементы в блоке
  protected Key[] keys;
  
  //высота ветви/листа
  int level;
  
  //последний блок ветви/листа
  boolean last = false;

  //поиск индекса элемента в массиве блока
  public int getLoc(Key key, boolean is_node) {
   //двоичный поиск в порядоченном массиве O=Log2N
   
   int lo = 0;
   int hi = num - 1;
   //пока левая и правая границы не встретятся
   while (lo <= hi) {
    //находим середину
       int mid = lo + (hi - lo) / 2;
       
       //если элемент меньше середины
       if (key.compareTo(keys[mid]) < 0) {
        //если текущий элемент больше, а следующий меньше, то возвращаем текущий
        if(mid == 0) return 0;
        if(mid > 0 && key.compareTo(keys[mid - 1]) > 0) return mid;
        
        //то верхняя граница - 1 = середина
        hi = mid - 1;
       } else if (key.compareTo(keys[mid]) > 0) {
        //если текущий элемент меньше, а следующий больше, то возвращаем следующий
        if(mid == num) return mid;
        if(mid < num - 1 && key.compareTo(keys[mid + 1]) < 0) return mid + 1;
        
        //если больше, то нижняя граница = середина + 1
        lo = mid + 1;
       } else {
        //иначе нашли
        
        //для ветви возвращаем следующий за найденным элемент, т.к. ссылка идет налево
        if(is_node) return mid + 1;
        
        //для листы чисто найденный элемент
        return mid;
       }
   }
   
   return num;
  } //getLoc

  // возвращает null, если блок не нужно разделять, иначе информация о разделении
  abstract public Split insert(Key key, Value value);

  abstract public void dump();
 } //Node

 
 //листовой блок дерева
 class LNode extends Node {
  //ссылки на реальные значения - строки таблицы
  final Value[] values = (Value[]) new Object[rows_block];
  
  //ссылка на следующий блок
  LNode next;
  
  
  public LNode() {
   keys = (Key[]) new Comparable[rows_block];
   level = 0;
  } //LNode
  
  public int getLoc(Key key) {
   return getLoc(key, false);
  } //getLoc

  //вставка элемента в листовой блок
  public Split insert(Key key, Value value) {
   // находим место для вставки
   int i = getLoc(key);
   
   
   //место вставки последний элемент, блок необходимо разбить на 2 части
   if (this.num == rows_block) {
    /*
     * Пример 50/50:
     * 
         3
     1 2   3 4 5
     ---
     mid = 5/2 = 2
     snum = 4 - 2 = 2      -- уходит направо
     mid=2                 --уходит налево
     keys[mid]=mid[3] = 3  --средний элемент, уходит наверх
     * */
    
    
    //делим блок на 90/10 поумолчанию
    int mid = rows_block;
    
    //если вставка идет не в конец
    if(!this.last || i < mid) {
     //то делим блок 50/50
     mid = (rows_block + 1) / 2;
    }
    //mid = (rows_block + 1) / 2;
    
    //кол-во элементов в правой части
    int sNum = this.num - mid;
    
    //новый правый листовой блок
    LNode sibling = new LNode();
    sibling.num = sNum;
    
    //перемещаем в него половину элементов
    System.arraycopy(this.keys, mid, sibling.keys, 0, sNum);
    System.arraycopy(this.values, mid, sibling.values, 0, sNum);
    
    //делим ровно на полам, все элементы разойдутся налево или направо
    this.num = mid;
    
    //если сплитится последний блок, то помечаем последним правый
    if(this.last) {
     this.last = false;
     sibling.last = true;
    }
    
    //позиция в левом блоке
    if (i < mid) {
     this.insertNonfull(key, value, i);
    } else {
     //или в правой
     sibling.insertNonfull(key, value, i - mid);
    }
    //информируем блок ветви о разделении: {значение разделения, левый блок, правый блок, 0 уровень листа}
    //элемент разделения берем из правой части
    Split result = new Split(sibling.keys[0], this, sibling, level);
    
    //связываем текущий блок со следующим
    sibling.next = this.next;
    this.next = sibling;    
    
    return result;
   } else {
    //блок не полон, вставляем элемент в i мето
    this.insertNonfull(key, value, i);    
    return null;
   }
  }

  //вставка элемента в неполный листовой блок
  private void insertNonfull(Key key, Value value, int idx) {
   //смещаем все элементы массивов правее idx на 1 элемент
   System.arraycopy(keys, idx, keys, idx + 1, num - idx);
   System.arraycopy(values, idx, values, idx + 1, num - idx);

   //в освободившееся место вставляем элемент
   keys[idx] = key;
   values[idx] = value;
   
   //число элементов в блоке
   num++;
   
   //всего элементов в индексе
   cnt++;
  }

  public void dump() {
   if(last) {
    System.out.println("(last):");
   }
   for (int i = 0; i < num; i++) {
    System.out.println(keys[i]);
   }
  }
 } //LNode

 //класс блока ветви
 class INode extends Node {
  final Node[] children = new BPTree.Node[rows_block + 1];
  
  public INode() {
   keys = (Key[]) new Comparable[rows_block];
  } //INode

  //поиск индекса для вставки в блоке-ветви
  public int getLoc(Key key) {
   return getLoc(key, true);
  } //getLoc

  //вставка элемента в ветвь
  public Split insert(Key key, Value value) {
   /*
    * Упрощенный вариант сплита, когда разделение идет сверху вниз,
    * что может привести к преждевременному росту дерева и как следствие дисковых чтений в бд.
    * В реальности разделение должно идти снизу вверх - это минимизирует рост дерева.
    * 
    * */

   //число элементов в блоке достигло предела - разделяем
   if (this.num == rows_block) {
    /*
     * Пример:
     * 
       2
     1   3 4 (3 max)
     
         3
     1 2   4 5 (4 max)
     
     ---
     mid = 5/2 = 2
     snum = 4 - 2 = 2        -- уходит направо
     mid-1=1                 --уходит налево
     keys[mid-1]=mid[1] = 2  --средний элемент, уходит наверх
     * */
    
    //середина
    int mid = (rows_block + 1) / 2;
    
    //создаем блок справа
    int sNum = this.num - mid;
    INode sibling = new INode();
    sibling.num = sNum;
    sibling.level = this.level;
    
    //копируем в него половину значений
    System.arraycopy(this.keys, mid, sibling.keys, 0, sNum);
    //копируем дочерние элементы +1(?)
    System.arraycopy(this.children, mid, sibling.children, 0, sNum + 1);

    //в левой части будет -1 элемент, он уходит на верхний уровень
    this.num = mid - 1;

    //передаем информацию о разделении выше: {средний элемент, левая, правая ветвь}
    Split result = new Split(this.keys[mid - 1], this, sibling, this.level);

    //если элемент меньше середины, то вставляем в левую чать
    if (key.compareTo(result.key) < 0) {
     this.insertNonfull(key, value);
    } else {
     //иначе в правую
     sibling.insertNonfull(key, value);
    }
    
    //информируем вышестоящуюю ветвь о разделении, может ее тоже надо будет разделить
    return result;

   } else {
    //место под разбиение нижних еще есть - вставляем
    this.insertNonfull(key, value);
    return null;
   }
  } //insert

  private void insertNonfull(Key key, Value value) {
   //ищем индекс для вставки
   int idx = getLoc(key);
   
   //рекурсивный вызов для нижележайшей ветви
   Split result = children[idx].insert(key, value);

   //нижний блок пришлось разбить на 2 части
   if (result != null) {
    //вставка в крайнее правое место
    if (idx == num) {
     keys[idx] = result.key;
     // на нашем уровен становится 2 элемета-ветви
     //текущий будет ссылаться на левую чать разделенной дочерней части
     //а новый элемент снизу - на правую
     children[idx] = result.left;
     children[idx + 1] = result.right;
     num++;
    } else {
     //вставка в середину массива
     //смещаем все элементы вправа на 1 позицию
     System.arraycopy(keys, idx, keys, idx + 1, num - idx);
     System.arraycopy(children, idx, children, idx + 1, num - idx + 1);

     //аналогично
     children[idx] = result.left;
     children[idx + 1] = result.right;
     keys[idx] = result.key;
     num++;
    }
   } // result != null
  } //insertNonfull


  public void dump() {
   for (int i = 0; i < num; i++) {
    children[i].dump();
    for(int j = 0; j < level; j++) System.out.print(" . ");
    
    System.out.println("> " + keys[i] + " ("+num+")");
   }
   children[num].dump();
  }
 } //INode

 //структура с информацией о разделении: значение разделения, левая и правая часть и уровень ветви
 class Split {
  public final Key key;
  public final Node left;
  public final Node right;
  public final int level;

  public Split(Key k, Node l, Node r, int h) {
   key = k;
   left = l;
   right = r;
   level = h;
  }
 } //Split
 
 public static void main(String[] args) {
  int rows_on_block = 3;
  BPTree t = new BPTree(rows_on_block);
  
  /*for(int i = 0; i <= 99; i++) {
   t.insert(i, i);
  }*/
  
  /*for(int i = 99; i >= 0; i--) {
   t.insert(i, i);
  }*/
  
  for(int i = 99; i >= 0; i--) {
   t.insert(ThreadLocalRandom.current().nextInt(0, 100), i);
  }
  
  //      0  1  2  3  4  5  6  7  8   9   10  11  12 13
  /*Integer arr_tst[] = {2, 6, 3, 5, 1, 7, 8, 0, 27, 17, 99, 13, 1, 7};
  for(int i = 0; i < arr_tst.length; i++) {
   t.insert(arr_tst[i], i);
  }*/
  
  t.dump();
  
  System.out.println("indexScan (5) = " + t.indexScan(5));
  System.out.println("indexScan (6) = " + t.indexScan(6));
  System.out.println("indexScan (4) = " + t.indexScan(4));
  System.out.println("indexScan (1) = " + t.indexScan(1));
  System.out.println("indexScan (99) = " + t.indexScan(99));
  System.out.println("indexScan (100) = " + t.indexScan(100));
  
  
  Object arr[] = new Integer[t.getCnt()];
  arr = t.fullScan();
  System.out.print("fullScan = ");  
  for(int i = 0; i < arr.length; i++) {
   System.out.print((Integer)arr[i] + ", ");
  }
  System.out.println(" ");
  
  System.out.println("cluster_factor = " + t.getClusterFactor());
  
  arr = t.rangeScan(2, 7);
  System.out.print("rangeScan(2,7) = ");
  for(int i = 0; i < arr.length; i++) {
   System.out.print((Integer)arr[i] + ", ");
  }
  
 } //main
} //BPTree


Полный код класса и юнит тесты можно посмотреть здесь: https://github.com/pihel/java/blob/master/BPTree/

среда, 9 ноября 2016 г.

Oracle 12: новые возможности для разработчика

9 ноября 2016 вышла документация по Oracle 12.2. В связи с этим опишу основные изменения в этой и предыдущих версиях Oracle 12.

понедельник, 24 октября 2016 г.

Oracle: реализация order by сортировки

Хотел бы начать цикл статей о внутреннем устройстве Oracle. Какие алгоритмы скрываются за казалось бы простыми операциями запросов.

Список статей о внутреннем устройстве Oracle:


Начну с операции order by.

При выполнении сортировки, данные сначала помечаются в приватную область памяти pga, называемую "sorting work area". Если данные не помещаются целиком, то массив разбивается на части и сохраняются на диск в TEMP пространство процесса, после чего части сортируются по отдельности в памяти, а потом сливаются в один отсортированный набор (внешняя сортировка слиянием).

До 10 версии Oracle "sort area size" была жестко фиксирована из-за этого нельзя было применять сортировки расходующие дополнительную память. Скорей всего это была сортировка вставками, имеющая стоимость O(N*N) (http://www.hellodba.com/reader.php?ID=185&lang=EN). Алгоритм сортировки вставками на java можно посмотреть здесь: https://github.com/pihel/java/blob/master/oracle_sort/OracleSort.java#L238 .

Одним из основных нововведений Oracle 10gR2 - гибкий размер pga и увеличение области сортировки (pga target), что позволило применять сортировки с дополнительным потреблением памяти.
Переключение новая/старая сортировка осуществляется скрытым параметром "_new_sort" - по умолчанию = true

Новая реализация order включает в себя смесь 3 сортировок: быстрая сортировка (qsort) + поразрядная сортировка (radix sort) + сортировка слиянием (merge sort). Что дает сложность от N*K до N*Log2(N), где K - размер ключа, а N - размер массива.

Общий алгоритм представляет из себя:

1. Используя алгоритм из сортировки слиянием разбиваем входящий массив (MergeSort.sort) на части с размером меньше "sort area size" ( OracleSort.isSortArr )
package oracle_sort;

import java.util.*;
import org.junit.runner.JUnitCore;
import org.junit.runner.Result;

/*
Сортировка слиянием: 
 * Сложность: N*Log2(N)
 * Доп. память: O(N)
 * Общий смысл:
  ** рекурсивно разбиваем массив на 2 части, пока размер элемента не дойдет до N (тут =1 )
  ** сливаем массивы в один последовательным проходом (в худшем случае N+M), сравнивая элементы
*/
class MergeSort {
 
 //проверка достаточности разбиения
 @SuppressWarnings("rawtypes") 
 protected boolean isSortArr(Comparable[] arr) {
  if(arr.length <= 1) return true;
  return false;
 }
 
 //разбитие массива на 2 равные части
 @SuppressWarnings("rawtypes") 
 public void sort(Comparable[] arr) {
  
     //если массив достаточно разбит, то прерываем рекурсию
     if(isSortArr(arr)) return;
  
     //левая половина
     Comparable[] left = new Comparable[arr.length / 2];  
     System.arraycopy(arr, 0, left, 0, left.length);
     sort(left);
     //swop to disk
     
     //правая половина
     Comparable[] right = new Comparable[arr.length - left.length];
     System.arraycopy(arr, left.length, right, 0, right.length);
     sort(right);
      
     //слияние
     merge(left, right, arr);
 } //sort
} //MergeSort


/*
 * Комбинированная сортировка: слиянием + быстрая + поразрядная
 * 
 * */
public class OracleSort extends MergeSort {
 //размер памяти под сортировку
 int sort_area_size = 1;
 //размер ключа
 int avg_key_size = 0;
 
 
 final double log10_2 = Math.log(2);
 
 OracleSort(int _sort_area_size, int _avg_key_size) {
  sort_area_size = _sort_area_size;
  avg_key_size = _avg_key_size;
 } //OracleSort
 
 protected boolean isSortArr(Comparable[] arr) {
  
  if(arr.length < 2) return true;
  
  //если после разбиения массива размер меньше размера под сортировку
  if(arr.length <= sort_area_size) {  
   
   //если Integer и размер ключа меньше log2(Т), то делаем поразрядную сортировку
   if( arr[0].getClass() == Integer.class && avg_key_size > 0 && avg_key_size < ( Math.log(arr.length) / log10_2 ) ) {
    
    Integer[] _arr = new Integer[arr.length]; //как привести Comparable к Integer?
    
    System.arraycopy(arr, 0, _arr, 0, arr.length);
    Sorts.radixSortUInt(_arr);
    System.arraycopy(_arr, 0, arr, 0, arr.length);
    _arr = null;
   } else {
    //иначе быструю сортировку
    Sorts.QSort(arr, 0, arr.length-1);
   }
   return true;
  }
  return false;
 } //isSortArr

}

2. Подмассивы размером меньше "sort area size" сортируются одним из алгоритмов внутри памяти.
В зависимости от размера ключа сортировки (avg_key_size) выбирается или поразрядная сортировка (radix sort) или быстрая (qsort): OracleSort.isSortArr

2.1. Быстрая сортировка имеет среднюю сложность O (N * Log2(N)) и хорошо использует процессорный кэш, но сильно зависит выбора среднего элемента. Для этого используется статистика на столбце таблицы: максимальное и минимальное значение в нем.
/*
  Быстрая сортировка: 
   * Сложность: N*Log2(N)
   * Доп. память: нет
   * Минусы:
   * - Сильно зависит от выбора средней точки, при неправильно выборе (крайний элемент) сложность = N*N
   * - На большом наборе данных из-за рекурсии может вызвать переполнение стека
   * Общий смысл:
    ** находим элемент в центре массива со средним значением
    ** движемся с краев к центру, меняя значения местами, если влевой части значение больше середины или вправой больше
    ** при доходе до середины, запускам рекурсивно для левой и правой части
  */
 public static <T extends Comparable<T>> void QSort(T[] arr, int l, int r) {
  int i = l;
  int j = r;
  //средний элемент = левая граница + (правая граница - левая граница) / 2
  T c = arr[l + ( r - l ) / 2];
  
  // идем к центу, пока края не встретятся
  while(i < j) {
   //идем с левого края к центру, пока середина больше текущего значения (ищем элемент больше середины)
   while(arr[i].compareTo(c) < 0) {
    i++;
   }
   //с правого края к центру, пока середина меньше текущего значения (ищем элемент меньше середины)
   while(arr[j].compareTo(c) > 0) {
    j--;
   }
   //если левый индекс меньше правого индекса, то меняем местами и смещаемся
   if(i <= j) {
    T t = arr[j];
    arr[j] = arr[i];
    arr[i] = t;
    i++;
    j--;
   }
  }
  //рекурсивно запускаемся для левой и правой части
  if(l < j) {
   QSort(arr, l, j);
  }
  if(r > i) {
   QSort(arr, i, r);
  }
 } //QSort

2.2. Если размер ключа сортировки на основе статистики "avg_key_size" (K) меньше Log2 от размера массива N, то поразрядная сортировка более эффективна, т.к. имеет сложность = O (K*N)

Ниже пример реализации для массива Integer:
/*
  Поразрядная сортировка: 
   * Сложность: N*K
    ** где K число разрядов в сортиуемом элементе
   * Доп. память: O(N)
   * Минусы/Плюсы:
    * -/+ быстрей, если k < log2(n) и дольше в других случаях
    * - разный размер хэш массива для разных типов данных
   * Особенность:
    * Порядок сортировки зависит от направления: для цифр нужно справа-навлево, для строк: слева-направо
   * Общий смысл:
    * Идем по рязрядам числа справа-налево и помещаем элементы в массив по значению текущего разряда
     ** т.е. элементы сначала упорядычиваются по последнему элементу
     ** потом переупорядычиваваются по второму и т.д. пока полностью не упорядочим массив
  */
 public static <T extends Integer> void radixSortUInt(T[] arr) {
  
  //хэш массив из 10 элементов для 10-ричного числа
  final int RADIX = 10;
  List<T>[] bucket = new ArrayList[RADIX];
  for (int i = 0; i < bucket.length; i++) {
   //список чисел, содержащих нужно число в разряде
   bucket[i] = new ArrayList<T>();
  }
  
  //признак, что все разряды перебраны
  boolean maxLength = false;
  //значение в разряде
  int rank_val = -1;
  //номер разряда
  int placement = 1;
  
  //пока не перебраны все разряды
  while (!maxLength) {
      maxLength = true;
      
      //для каждого элемента массива
      for (int i = 0; i < arr.length; i++) {
       //добавляем элемент в массив по значению в разряде
       rank_val = arr[i] / placement;
       bucket[rank_val % RADIX].add(arr[i]);
       
       //если в разряде не пусто, то ставим флаг повторения цикла
       if (maxLength && rank_val > 0) {
        maxLength = false;
       }
      }
      
      //разворачиваем двухуровневый массив обратно в последовательный
      int a = 0;
      for (int b = 0; b < RADIX; b++) {
       for (int i = 0; i < bucket[b].size(); i++) {
        arr[a++] = bucket[b].get(i);
       }
       bucket[b].clear();
      }
      //переходим к следующему разряду
      placement *= RADIX;
  }
    
 } //radixSortUInt

3. Отсортированные части объединяются за один проход в отсортированный массив используя алгоритм слияния:
 //слияние 2 упорядоченных массивов в один
 @SuppressWarnings({ "rawtypes", "unchecked" }) 
 private void merge(Comparable[] left, Comparable[] right, Comparable[] arr) {
  int iFirst = 0;        
     int iSecond = 0;         
     int iMerged = 0;
      
     //бежим, пока не дойдем до конца одного из массивов
     while (iFirst < left.length && iSecond < right.length) {
      //если элемент в левом массиве больше, чем в правом
         if (left[iFirst].compareTo(right[iSecond]) < 0) {
             //то добавляем элемент из левого
             arr[iMerged] = left[iFirst];
             //и двигаемся в левом на 1
             iFirst++;
         } else {
             //иначе добавляем элемент из правого
             arr[iMerged] = right[iSecond];
             //двигаемся в правом на 1
             iSecond++;
         }
         //в любом случае увеличиваем результирующий массив
         iMerged++;
     }
     
     //оставшиеся элементы - больше последнего (максимального) элемента одного из массивов. Докопируем оставшиеся элементы.
     System.arraycopy(left, iFirst, arr, iMerged, left.length - iFirst);
     System.arraycopy(right, iSecond, arr, iMerged, right.length - iSecond);
 } //merge

Полную версию oracle order by можно посмотреть здесь: https://github.com/pihel/java/blob/master/oracle_sort/OracleSort.java#L463 , включая юнит тесты: https://github.com/pihel/java/blob/master/oracle_sort/OracleSortTest.java#L65

четверг, 14 апреля 2016 г.

Ядро oracle

на основе одноименной книги Дж. Льюиса

1. Согласованное чтение
2. Восстановление данных
3. Принцип кэширования блоков в память при чтении
4. Парсинг запросов
5. RAC - кластер экземпляров oracle
6. Блокировки и защелки


1. согласованное чтение
общий принцип:

a. транзакция 1 изменяет данные:
 * в буферный кэш скидывается грязный блок
  ** в блоке данных записывается список недавних транзакий ITL (включая сейчас выполняющуюся)
  ** если транзакция сейчас выполняется, то также проставляется признак блокировки строки в блоке
 * процесс lgwr пишет:
  ** в redo журнал повтора - новое значение, новый scn, список ITL
  ** в undo журнал отката - старое значение и старый scn
 * процесс dbwr пишет:
  ** асинхронно с задержкой записывает данные в блок базы
   *** сразу после commit записывается не более 30% данных
   *** остальная часть записывается отложенно при следующем select из строк этой таблицы.
   Детектировать можно через события "db block change, consisten gets - examination"
   Т.е. не стоит удивляться, что первый select после большого update будет выполняться очень долго.

b. транзакция 2 читает данные:
 * считываются данные из буферного кэша или напрямую с диска
 * просматривается список ITL на наличие незавершенных транзакций
 * в любом случае (не зависимо от ITL) сверяется SCN транзакции и SCN блока (ITL незавершенной транзакции)
  ** если SCN блока/ITL оказывается больше запрашиваемого, то данные берутся из сегментов отката UNDO через ссылку из ITL
   *** поиск по ITL может продолжиться и дальше рекурсивно, если SCN запроса опять меньше SCN из undo
   *** если данные в undo не находятся, то это является причиной ошибки "snapshot too old"
 * в случае недавнего обновления блока, строка может оказаться помеченной как сейчас обновляемая и со старым SCN в списке ITL выполняется операция отложенная очистка:
  ** берутся данные из UNDO сегмента, смотрится, что транзакция подтверждена
  ** сбрасывается флаг блокировки в строке блока и ITL (что повторно генерирует redo логи при select таблицы)
  ** в случае отсутствия блока в буферном кэше и чтения с диска дополнительно изменяется номер SCN на максимальный (т.к. отсутствие блока в кэше говорит об однозначно последней версии на диске)

Примечание: как многоверсионность сделана в Postgree:
Устаревшие строки (после delete/update) хранятся в том же месте, где основная таблица.
Определение версии используются дополнительные идентификаторы в самой строке.
При update выполняются действия:
* Создается строка с новыми данными
* От старой строки создается указатель на новую
* У старой строки проставляется:
 ** xmin - идентификатор транзакции от старой версии строки
 ** xmax - идентификатор транзакции от новой версии строки

Т.е. при select читаются строки у которых нет новой версии (xmax), т.е. актуальные сейчас строки. Если в этот момент идет модификация, то старые строки будут существовать до полного окончания, а после будут очищены фоновым vacuum.

+ быстрое чтение, без обращения к стороннему логу
- любое изменение генерирует новую строку, из-за чего нужно перестраивать все индексы на таблице, даже если изменялось поле не из индексов
- большой поток изменений в репликации

четверг, 24 марта 2016 г.

Oracle: распределение (Distrib) данных в параллельных запросах

Эта заметка осмысление статьи http://oracle-randolf.blogspot.ru/2012/12/hash-join-buffered.html по неочевидной операции HASH JOIN BUFFERED в параллельных запросах.

Основная мысль, которую надо понять при работе с параллельными запроса: "At most one data distribution can be active at the same time" - только одно распределение данных ( PQ Distrib / PX SEND ) может работать одновременно.

Это является причиной появления операций HASH JOIN BUFFERED или BUFFER SORT в параллельных планах, именно они сбивают с мысли человека привыкшего к последовательным не параллельным запросам.
Может сложиться ошибочное мнение о том что при выполнении HASH JOIN закончился hash area size и oracle свопит промежуточные данные на диск/память или делается какаято сортировка, чтобы потом выполнить merge join.

В реальности, как я уже сказал ранее, на параллельные запросы накладывается дополнительное условие: только одно распределение данных ( PQ Distrib / PX SEND ) может работать в один момент.
Это вынуждает складировать промежуточные данные других потоков до конца выполнения распределения, что является причиной появления буферных операций HASH JOIN BUFFERED и BUFFER SORT.

Рассмотрим на примере:

Создадим 2 таблицы:
create table t2
compress
as
select
        rownum as id
      , mod(rownum, 1000) + 1 as fk
      , rpad('x', 100) as filler
from
        dual
connect by
        level <= 1000000
;
exec dbms_stats.gather_table_stats(null, 't2')

-- Create a copy of T2
create table t4
compress as
select * from t2;

insert /*+ append */ into t4
select
        1000000 + rownum as id
      , 1000 + mod(rownum, 1000) + 1 as fk
      , rpad('x', 100) as filler
from
        dual
connect by
        level <= 1000000
;

commit;

exec dbms_stats.gather_table_stats(null, 't4')

alter table t2 parallel 2;

alter table t4 parallel 2;

Oracle может выполнить hash join 3 разными способами.

Способ 1 с HASH JOIN BUFFERED:
explain plan for
select * from (
select  /*+ no_merge use_hash(a b) no_cpu_costing leading(a b) pq_distribute(b, hash, hash) */
        a.filler as a_filler, b.filler as b_filler
from
        t2 a
      , t4 b
where
        a.fk = b.fk
)
where rownum > 1;
select * from table(dbms_xplan.display(format=>'ALLSTATS ALL ADVANCED'));

-----------------------------------------------------------------------------------------------------
| Id  | Operation                  | Name     | E-Rows |E-Bytes| Cost  |    TQ  |IN-OUT| PQ Distrib |
-----------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT           |          |   1000M|    96G| 56606 |        |      |            |
|   1 |  COUNT                     |          |        |       |       |        |      |            |
|*  2 |   FILTER                   |          |        |       |       |        |      |            |
|   3 |    PX COORDINATOR          |          |        |       |       |        |      |            |
|   4 |     PX SEND QC (RANDOM)    | :TQ10002 |   1000M|    96G| 56606 |  Q1,02 | P->S | QC (RAND)  |
|   5 |      VIEW                  |          |   1000M|    96G| 56606 |  Q1,02 | PCWP |            |
|*  6 |       HASH JOIN BUFFERED   |          |   1000M|   195G| 56606 |  Q1,02 | PCWP |            |
|   7 |        PX RECEIVE          |          |   1000K|   100M|   175 |  Q1,02 | PCWP |            |
|   8 |         PX SEND HASH       | :TQ10000 |   1000K|   100M|   175 |  Q1,00 | P->P | HASH       |
|   9 |          PX BLOCK ITERATOR |          |   1000K|   100M|   175 |  Q1,00 | PCWC |            |
|  10 |           TABLE ACCESS FULL| T2       |   1000K|   100M|   175 |  Q1,00 | PCWP |            |
|  11 |        PX RECEIVE          |          |   2000K|   200M|   359 |  Q1,02 | PCWP |            |
|  12 |         PX SEND HASH       | :TQ10001 |   2000K|   200M|   359 |  Q1,01 | P->P | HASH       |
|  13 |          PX BLOCK ITERATOR |          |   2000K|   200M|   359 |  Q1,01 | PCWC |            |
|  14 |           TABLE ACCESS FULL| T4       |   2000K|   200M|   359 |  Q1,01 | PCWP |            |
-----------------------------------------------------------------------------------------------------
Хинты заданы, чтобы точно гарантировать последовательность работы.
Через хинт pq_distribute(b, hash, hash) мы задаем способ обмена данными между потоками - в данном случае hash.

Используя мониторинг становится ясна последовательность выполнения (Timeline):
HASH JOIN BUFFERED
1. PX SEND HASH :TQ10000 - левая таблица целиком хэшируется и отправляется в :TQ10002
2. PX SEND HASH :TQ10001 - правая таблица также целиком хэшируется и отправляется в :TQ10000.
Так же до этапа HASH JOIN происходит откидывание несоответствующих хэшей правой таблицы (Randolf подтверждает это трассировкой и рассчетами на основании количества строк в правой hash таблице)
Дополнительная затраченная память отображается в столбце Memory.
3. PX SEND QC (RANDOM) :TQ10002 - происходит соединение таблиц используя хэши левой и правой таблицы + параллельная отправка промежуточных данных на следующий этап.

Такая последовательность действий обеспечивает нам 1 рабочий PX SEND одновременно.


Способ 2: HASH JOIN альтернативный план, когда хэш правой таблицы передается постепенно и не буферизуется.
Чтобы получить его, достаточно добавить агрегирующую функцию (count/min/max) - что заблокирут передачу промежуточных данных на уровень выше.
explain plan for
select count(*) from (
select  /*+ no_merge use_hash(a b) no_cpu_costing leading(a b) pq_distribute(b, hash, hash) */
        a.filler as a_filler, b.filler as b_filler
from
        t2 a
      , t4 b
where
        a.fk = b.fk
);
select * from table(dbms_xplan.display(format=>'ALLSTATS ALL ADVANCED'));

-----------------------------------------------------------------------------------------------------
| Id  | Operation                  | Name     | E-Rows |E-Bytes| Cost  |    TQ  |IN-OUT| PQ Distrib |
-----------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT           |          |      1 |       | 56043 |        |      |            |
|   1 |  SORT AGGREGATE            |          |      1 |       |       |        |      |            |
|   2 |   PX COORDINATOR           |          |        |       |       |        |      |            |
|   3 |    PX SEND QC (RANDOM)     | :TQ10002 |      1 |       |       |  Q1,02 | P->S | QC (RAND)  |
|   4 |     SORT AGGREGATE         |          |      1 |       |       |  Q1,02 | PCWP |            |
|   5 |      VIEW                  |          |   1000M|       | 56043 |  Q1,02 | PCWP |            |
|*  6 |       HASH JOIN            |          |   1000M|  7629M| 56043 |  Q1,02 | PCWP |            |
|   7 |        PX RECEIVE          |          |   1000K|  3906K|   175 |  Q1,02 | PCWP |            |
|   8 |         PX SEND HASH       | :TQ10000 |   1000K|  3906K|   175 |  Q1,00 | P->P | HASH       |
|   9 |          PX BLOCK ITERATOR |          |   1000K|  3906K|   175 |  Q1,00 | PCWC |            |
|  10 |           TABLE ACCESS FULL| T2       |   1000K|  3906K|   175 |  Q1,00 | PCWP |            |
|  11 |        PX RECEIVE          |          |   2000K|  7812K|   359 |  Q1,02 | PCWP |            |
|  12 |         PX SEND HASH       | :TQ10001 |   2000K|  7812K|   359 |  Q1,01 | P->P | HASH       |
|  13 |          PX BLOCK ITERATOR |          |   2000K|  7812K|   359 |  Q1,01 | PCWC |            |
|  14 |           TABLE ACCESS FULL| T4       |   2000K|  7812K|   359 |  Q1,01 | PCWP |            |
-----------------------------------------------------------------------------------------------------
hash join
1. PX SEND HASH :TQ10000 - левая таблица целиком хэшируется и отправляется в :TQ10002
2. PX SEND HASH :TQ10001 - правая таблица построчно хэшируется и отправляется в :TQ10000.
Эта операция не требует дополнительных затрат памяти.
3. HASH JOIN - происходит построчное соединение таблиц используя хэши левой и правой таблицы.
4. PX SEND QC (RANDOM) :TQ10002 - отправка результата дальше, выполняется после полного выполнения этапа 2, т.е. после полного выполнения HASH JOIN этапа 3.

Способ 3: BUFFER SORT альтернативный план, в целом похожий на HASH JOIN BUFFERED
select * from (
select  /*+ no_merge use_hash(a b) no_cpu_costing leading(a b) pq_distribute(b, none, broadcast) */
        a.filler as a_filler, b.filler as b_filler
from
        t2 a
      , t4 b
where
        a.fk = b.fk
)
where rownum > 1;

select * from table(dbms_xplan.display(format=>'ALLSTATS ALL ADVANCED'));

------------------------------------------------------------------------------------------------------
| Id  | Operation                   | Name     | E-Rows |E-Bytes| Cost  |    TQ  |IN-OUT| PQ Distrib |
------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |          |   1000M|    96G| 56606 |        |      |            |
|   1 |  COUNT                      |          |        |       |       |        |      |            |
|*  2 |   FILTER                    |          |        |       |       |        |      |            |
|   3 |    PX COORDINATOR           |          |        |       |       |        |      |            |
|   4 |     PX SEND QC (RANDOM)     | :TQ10001 |   1000M|    96G| 56606 |  Q1,01 | P->S | QC (RAND)  |
|   5 |      VIEW                   |          |   1000M|    96G| 56606 |  Q1,01 | PCWP |            |
|*  6 |       HASH JOIN             |          |   1000M|   195G| 56606 |  Q1,01 | PCWP |            |
|   7 |        PX BLOCK ITERATOR    |          |   1000K|   100M|   175 |  Q1,01 | PCWC |            |
|   8 |         TABLE ACCESS FULL   | T2       |   1000K|   100M|   175 |  Q1,01 | PCWP |            |
|   9 |        BUFFER SORT          |          |        |       |       |  Q1,01 | PCWC |            |
|  10 |         PX RECEIVE          |          |   2000K|   200M|   359 |  Q1,01 | PCWP |            |
|  11 |          PX SEND BROADCAST  | :TQ10000 |   2000K|   200M|   359 |  Q1,00 | P->P | BROADCAST  |
|  12 |           PX BLOCK ITERATOR |          |   2000K|   200M|   359 |  Q1,00 | PCWC |            |
|  13 |            TABLE ACCESS FULL| T4       |   2000K|   200M|   359 |  Q1,00 | PCWP |            |
------------------------------------------------------------------------------------------------------
Меняем метод рассылки данных на BROADCAST - копирование данных во все потоки.
В этом случае хэши правой таблицы не создаются, вместо этого данные помещаются в BUFFER SORT и используются при выполнении HASH JOIN
buffer sort
1. PX SEND BROADCAST :TQ10000 - правая таблица целиком пересылается в BUFFER SORT
Надо заметить, что BUFFER SORT в этом случае ничего не сортирует, а только буферизирует данны.
Объем потребленной памяти = размер правой таблицы * параллелизм (из-за broadcast во все потоки).
2. HASH JOIN - происходит полное соединение таблиц.
4. PX SEND QC (RANDOM) :TQ10001 - отправка результата дальше по мере готовности.

Объем памяти в BUFFER SORT не растет во время выполнения, что подтверждает предположение - правая таблица целиком помещается в буфер сразу на первом этапе.
buffer sort 106sec


Вывод: обычный hash join лучше, когда памяти мало, т.к. нет операций с temp/памятью.
Если памяти достаточно, то hash join buffered предпочтительней, т.к. oracle может сразу перейти к следующему этапу запроса и получить большую степерь параллелизма.

воскресенье, 14 февраля 2016 г.

Oracle: адаптивные технологии оптимизации запросов


Оптимизация запросов со связанными bind переменными


1. При первом разборе происходит полный разбор запроса (hard parse)
План запроса помещается в глобальный кэш БД с определенным sql_id
2. При повторном выполнении происходит частичный разбор (soft parse)
Происходит только синтаксический разбор, проверки прав доступа и проверки bind переменных. Что для разных вариаций sql_id создает дочерние child_sql_id

Из-за такого механизма работы Oracle вытекает частая проблема oltp систем, где существует огромное число маленьких запросов, отличающихся друг от друга только фильтрами или параметрами. Это приводит к быстрому вытеснению планов из кэша и их последующему повторному hard parse.
В итоге может оказаться, что большую часть времени БД занимается разбором запросов, а не собственно их выполнением.
Отсюда вывод: по возможности используйте bind переменные в вариациях одного запроса, замен константных фильтров, т.к. это даст нам только один план запроса (child_sql_id) при разных значениях переменных на равномерно распределенном столбце.

Я не зря сказал ранее "на равномерно распределенном столбце", т.к. с bind переменными есть проблема: по умолчанию Oracle не знает какие данные будут переданы в запрос и из-за этого может сгенерить неверный план запроса.

Посмотрим на примере по умолчанию. Создадим таблицу с неравномерно распределенным столбцом "n" (9 строк со значением = 1, и 1млн-9 строк со значением 2):
create table t as
select level as id, case when level < 10 then 1 else 2 end as n
from dual
connect by level < 1000000;

create index t_i on t(n);

begin
  dbms_stats.gather_table_stats(user,'T',method_opt=>'for columns n size 1');
end;
Столбец не имеет гистограмм, но есть статистика по уникальным значениям. Построим план запроса с bind переменной = 1:
explain plan for select * from t where n = :n;
select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   500K|  3906K|   508   (2)| 00:00:07 |
|*  1 |  TABLE ACCESS FULL| T    |   500K|  3906K|   508   (2)| 00:00:07 |
--------------------------------------------------------------------------
 
Predicate Information (identified by operation id):
---------------------------------------------------
 
   1 - filter("N"=TO_NUMBER(:N))
Oracle закономерно ожидает в результате половину таблицу и выбирает full scan, хотя мы то знаем, что тут был бы лучше Index scan.

К счастью с 11 версии Oracle может заглядывать в значения bind переменных и подбирать под них нужные планы.
Для этого соберем гистограмму с 2 вершинами и повторим эксперимент:
begin
  dbms_stats.gather_table_stats(user,'T',method_opt=>'for columns n size 2');
end;

var n number;
exec :n := 1
select count(*) from t where n = :n;
select * from table(dbms_xplan.display_cursor(format=>'allstats last'));

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
SQL_ID  4qjwcfhq4s9vt, child number 2
-------------------------------------
select count(*) from t where n = :n

Plan hash value: 4142320527

-------------------------------------------
| Id  | Operation         | Name | E-Rows |
-------------------------------------------
|   0 | SELECT STATEMENT  |      |        |
|   1 |  SORT AGGREGATE   |      |      1 |
|*  2 |   INDEX RANGE SCAN| T_I  |    185 |
-------------------------------------------
Oracle сгенерировал новый child_sql_id под новое значение bind переменной и выбрал правильный доступ по индексу.

Данный план был закеширован в глобальную память и если прямо сейчас выполнить заново с параметром 2, то мы получим тотже план (child number 2).

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


exec :n := 2
select count(*) from t where n = :n;
select * from table(dbms_xplan.display_cursor(format=>'allstats last'));

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
SQL_ID  4qjwcfhq4s9vt, child number 2
-------------------------------------
select count(*) from t where n = :n

Plan hash value: 4142320527

-------------------------------------------
| Id  | Operation         | Name | E-Rows |
-------------------------------------------
|   0 | SELECT STATEMENT  |      |        |
|   1 |  SORT AGGREGATE   |      |      1 |
|*  2 |   INDEX RANGE SCAN| T_I  |    185 |
-------------------------------------------

но oracle пометит этот запрос на пересмотр, т.к. план совсем не сошелся с реальными данными и при последующем применении сгенерирует новый child_sql_id (child number 3) под нашу bind переменную:
exec :n := 2
select count(*) from t where n = :n;
select * from table(dbms_xplan.display_cursor(format=>'allstats last'));

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
SQL_ID  4qjwcfhq4s9vt, child number 3
-------------------------------------
select count(*) from t where n = :n

Plan hash value: 2966233522

--------------------------------------------
| Id  | Operation          | Name | E-Rows |
--------------------------------------------
|   0 | SELECT STATEMENT   |      |        |
|   1 |  SORT AGGREGATE    |      |      1 |
|*  2 |   TABLE ACCESS FULL| T    |    999K|
--------------------------------------------

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

   2 - filter("N"=:N)

Из всего этого можно сделать вывод, что вопреки частому заблуждению, Oracle умеет генерировать правильные планы по bind переменным, но делает это не сразу, а при повторном вызове и при наличии гистограммы.
Второе: реальный план запроса с bind переменными можно узнать только во время или после выполнения запроса, т.к. "explain plan" не подсматривает в bind переменные.

Cardinality feedback


Ora Blog
Oracle мониторит и исправляет следующии "estimated rows" оценки на основе реальных "actual rows"
* Single table cardinality (after filter predicates are applied)
* Index cardinality (after index filters are applied)
* Cardinality produced by a group by or distinct operator

Dynamic Sampling


Ora Blog
Применимо для запросов со сложными предикатами фильтрации, которые дают существенную ошибку оптимизатора.
Включение dynamic sampling в зависимости от параметра пробирует от 32 блоков таблицы на предикаты фильтрации и определяем реальный лучший план.

Oracle 12: Адаптивные планы


Смена плана во время выполнения запроса. На основе кол-ва данных полученных из шагов запроса генерируется оптимальный план следующего шага.
Адаптивность может сменить:
* Тип соединения NL <-> HJ
* тип parallel distribution
* Bitmap Index Pruning

пятница, 29 января 2016 г.

Oracle: оптимизация параллельных запросов

Один из простых способов ускорения запросов - это их расспараллеливание.
Это делается достаточно просто через:
* Хинт
/*+ parallel(N) */

* Через установки сессий:
alter session enable parallel dml; --для insert
ALTER SESSION FORCE PARALLEL QUERY PARALLEL N;

 - N число потоков

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

Для начала разберемся с терминологией - посмотрим на параллельный план с join 2 таблиц:
create table t_1
compress
as
select  /*+ use_nl(a b) */
        rownum as id
      , rpad('x', 100) as filler
from
        (select /*+ cardinality(1e5) */ * from dual
connect by
        level <= 1e5) a, (select /*+ cardinality(20) */ * from dual connect by level <= 20) b
;

create table t_2
compress
as
select
        rownum as id
      , case when rownum <= 5e5 then mod(rownum, 2e6) + 1 else 1 end as fk_id_skew
      , rownum as fk_id_uniform
      , rpad('x', 100) as filler
from
        (select /*+ cardinality(1e5) */ * from dual
connect by
        level <= 1e5) a, (select /*+ cardinality(20) */ * from dual connect by level <= 20) b
;

--соберем статистику
begin
  dbms_stats.gather_table_stats(user, 't_1');
  dbms_stats.gather_table_stats(user, 't_2');
end;
/
- Запрос 1

Таблица T2 имеет особенность: fk_id_skew неравномерно заполнен и имеет перекос в сторону 1 - она встречается значительно чаще других.
select COUNT(*) cnt, fk_id_skew  from t_2 GROUP BY fk_id_skew ORDER BY cnt desc;

       CNT FK_ID_SKEW
---------- ----------
   1500000          1
         1         22
         1         30
         1         34
....
- Запрос 2

Итак, выполнил простой запрос:
select count(t_2_filler) from (
select  /*+ monitor
            no_parallel
            leading(t_1 t_2)
            use_hash(t_2)
            no_swap_join_inputs(t_2)
        */
        t_1.id as t_1_id
      , t_1.filler as t_1_filler
      , t_2.id as t_2_id
      , t_2.filler as t_2_filler
from    t_1
      , t_2
where
        t_2.fk_id_uniform = t_1.id
and     regexp_replace(t_2.filler, '^\s+([[:alnum:]]+)\s+$', lpad('\1', 10), 1, 1, 'c') >= regexp_replace(t_1.filler, '^\s+([[:alnum:]]+)\s+$', lpad('\1', 10), 1, 1, 'c')
);
- Запрос 3

* regexp_replace в этом запросе нужен, чтобы данные отбирались не мгновенно и были видны в статистике затраты CPU.
* Хинты вставлены, чтобы запрос в плане выглядел также как написан тут.

Время выполнения выполнения запроса = 49сек.

Добавим хинт parallel(8) замен no_parallel.
Время выполнения = , что в 6 раз быстрей.
Разберем для понимания план запроса:
SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY(format=>'PARALLEL'));

-------------------------------------------------------------------------------------------------------------------
| Id  | Operation                 | Name     | Rows  | Bytes | Cost (%CPU)| Time     |    TQ  |IN-OUT| PQ Distrib |
-------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT          |          |     1 |   213 |   619   (2)| 00:00:08 |        |      |            |
|   1 |  SORT AGGREGATE           |          |     1 |   213 |            |          |        |      |            |
|   2 |   PX COORDINATOR          |          |       |       |            |          |        |      |            |
|   3 |    PX SEND QC (RANDOM)    | :TQ10002 |     1 |   213 |            |          |  Q1,02 | P->S | QC (RAND)  |
|   4 |     SORT AGGREGATE        |          |     1 |   213 |            |          |  Q1,02 | PCWP |            |
|*  5 |      HASH JOIN            |          |   100K|    20M|   619   (2)| 00:00:08 |  Q1,02 | PCWP |            |
|   6 |       PX RECEIVE          |          |  2000K|   202M|   245   (2)| 00:00:03 |  Q1,02 | PCWP |            |
|   7 |        PX SEND HASH       | :TQ10000 |  2000K|   202M|   245   (2)| 00:00:03 |  Q1,00 | P->P | HASH       |
|   8 |         PX BLOCK ITERATOR |          |  2000K|   202M|   245   (2)| 00:00:03 |  Q1,00 | PCWC |            |
|   9 |          TABLE ACCESS FULL| T_1      |  2000K|   202M|   245   (2)| 00:00:03 |  Q1,00 | PCWP |            |
|  10 |       PX RECEIVE          |          |  2000K|   204M|   371   (1)| 00:00:05 |  Q1,02 | PCWP |            |
|  11 |        PX SEND HASH       | :TQ10001 |  2000K|   204M|   371   (1)| 00:00:05 |  Q1,01 | P->P | HASH       |
|  12 |         PX BLOCK ITERATOR |          |  2000K|   204M|   371   (1)| 00:00:05 |  Q1,01 | PCWC |            |
|  13 |          TABLE ACCESS FULL| T_2      |  2000K|   204M|   371   (1)| 00:00:05 |  Q1,01 | PCWP |            |
-------------------------------------------------------------------------------------------------------------------
- План 1

Основопологающие фазы:
* PX BLOCK ITERATOR - чтение таблицы частями в несколько потоков
* PX SEND - 1 поток посылает данные другому. Важно знать, что только один producer (PX SEND) может быть активен в одно время, что накладывает ограничения на параллельный план выполнения, подробней: Вторая часть по распределению данных в параллельных запросах
 ** RANGE - данные будут разбиты на диапазоны (часто при сортировке)
 ** HASH - диапазон данных на основе их хэша (hash join, group by)
 ** RANDOM - случайная отправка
 ** BROADCAST - отправка таблицы во все потоки (часто на маленькой таблице, совместно с последующей ROUND ROBIN правой таблицы. Может быть проблемой производительности, если левая таблица значительно больше, чем указано в статистике, т.к. данные дублируются во все потоки)
 ** ROUND ROBIN - данные отправляются в потоки по кругу

Про способы распределения данных по потокам нужно поговорить отдельно:

Стоит заметить, что данные бьются по значениям в столбцах строк, а не просто по строкам.
Это нужно, чтобы один и тотже диапозон данных из разных таблиц попал в один поток для join.
Если бы Oracle делал не так, то в 1 поток могли бы попасть совершенно разные данные и join нельзя было бы совершить.
На это стоит обратить внимание, т.к. это может являться и причиной замедлений выполнения параллельного запроса при сильном перекосе данных (О причинах замделенния параллельных запросов дальше)

 ** P->P - данные из одной параллельной группы передаются в другую параллельную группу
 ** P->S - параллельность в последовательное выполнение (узкое место или конец запроса - вторая из основных причин замедления параллельного запроса)
 ** PCWP - параллельность с родителем: сканируем таблицу и сразу делаем join с другой
 ** PCWC - наоборот: передаем фильтр из внешнего потока и применяем при сканировании
* PX RECEIVE - получение данных из одного параллельного потока в другой
* PX SEND QC - отправка данных координатору
* PX COORDINATOR - приемник всех параллельных запросов
* TQ - Номер потока

Мы рассмотрели идеальный случай распараллеленого запроса. Остановимся подробней на причинах замеделений:
1. Событие "P->S - параллельность в последовательное выполнение"
2. PX SEND skew - Перекос данных
и ускорения:
3. Bloom filter
4. Partition wise