понедельник, 4 февраля 2030 г.

Скахин Алексей / pihel

Скахин Алексей, pihel Биография:
Родился в городе Вологда 9 марта 1987 года. В 2004 году завершил обучение в средней школе №12 города Вологда. В 2009 году окончил ВоГУ (бывший ВоГТУ) по специальности программное обеспечение. Тема дипломного проекта: "Синтез виртуальной среды с применением скалярных и аналитических функций возмущения и трехмерных массивов вокселей". С 2013 года проживаю в городе Санкт-Петербург.

В бывшем радиолюбитель: 3ий взрослый разряд по радиотелеграфии, радиолюбитель в кв диапазоне. Позывной ra1qkj.

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

Навыки:
1. PHP: занимаюсь с 2004 года
 а. Bitrix - интеграция, интернет магазины, информационные порталы, государственные порталы)
 b. Drupal - интеграция, разработка модулей
2. JS: JQuery, ExtJS
3. C++: библиотека QT, C++ Builder
4. VBS: автоматизация рутины (авто сборка ПО, создание копий приложений и т.д.)
5. СУБД: Oracle PlSql, MySql, MS SQL (OLTP и OLAP), SqLite
6. Linux: пользователь Fedora и Ubuntu
7. Управление версиями: SVN, GIT, MS VSS
8. Остальное: FastReport, Excel (ActiveX, XML), Open(Libre)Office (XML, UNO), SVG/VML (raphaeljs, extjs), Flex, ITIL

Места работы:
6. Лента: perfomance specialist: Sap, Oracle ( sql, pl/sql, abap ), 2016 - ...
5. Сигма: разработчик баз данных Oracle ( sql, pl/sql, Oracle BI, dwh ), 2015 - 2016
4. Tops Consulting: разработчик баз данных Oracle ( sql, pl/sql ), 2013 - 2015
3. Макси: разработка системы управления предприятием, программист (C++, Oracle, Pl/Sql) 2010-2013
2. Rstyle Softlab ОПР ДСУП: разработка системы управления предприятием, старший программист (rsl/vbs/fast report/ms sql) 2008-2010
1. ВНКЦ ЦЭМИ РАН: разработка внутренней информационной системы (php/js/mysql) 2007-2008 г.
0. Фриланс - web направление 2003-...

суббота, 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

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

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


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

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


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

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

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


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

вторник, 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.

Oracle 12.2: http://docs.oracle.com/database/122/index.html

1. история в sql+

2. Улучшение json support.

3. view DBA_STATEMENTS - описывает все sql запросы в pl/sql включая execute immediate

4. funct VALIDATE_CONVERSION - возможность конвертирования типа
Больше не нужно кастомная функция с перехватом всех exception.

5. Materialized Views: Real-Time Materialized Views -
query rewrite на неактуальной версии мат вьюхи + актуальном мат логе

6. Materialized Views: Statement-Level Refresh - ON STATEMENT
- обновление mat view при вызове вьюхе, а не при коммите на источнике

7. В listagg появилась функция обрезки (раньше валилось с ошибкой)
LISTAGG ( [ALL]  [,] [ON OVERFLOW TRUNCATE [truncate_literal] | ON OVERFLOW ERROR  [WITH | WITHOUT COUNT]])
WITHIN GROUP (ORDER BY )

8. можно делать партицированной таблицу в online без redefinition:
ALTER TABLE employees_convert MODIFY
  PARTITION BY RANGE (employee_id) INTERVAL (100)
  ( PARTITION P1 VALUES LESS THAN (100),
    PARTITION P2 VALUES LESS THAN (500)
   ) ONLINE
  UPDATE INDEXES

9. Можно теперь менять параметры таблицы и применять их в ONLINE без redefinition:
ALTER TABLE ... MOVE ... ONLINE

10. Можно делать модификации части партиции по условию:
ALTER TABLE orders_move_part
  MOVE PARTITION q1_2016 TABLESPACE open_orders COMPRESS ONLINE
  INCLUDING ROWS WHERE order_state = 'open';

10. Партицирование external table. Только для big data движков-источников

11. Поддержка constraint (fk/not null/uniq ...) для external table

12. дополнительная статистика по im-memory столбцам: число блоков в im-mem. Для external table - скорость mb/s чтения

13. новая разновидность MERGE JOIN для запросов без явного ключа соединения - "Band Joins"
http://docs.oracle.com/database/122/TGSQL/joins.htm#TGSQL94989

14. Гибридное сжатие данных при вставке без +append

15. Появилось сильное advanced index compression

16. Partitioning: Auto-List Partitioning - партицирование по distinct значению

17. DBA_MVREF_*_STATS - статистика по изменению matview: время, метод, размер и тд.

18. Process Management - предсоздание параллельных процессов. Параллельные запросы будут использовать уже готовые, а не создавать сами, что даст небольшое ускорение.

19. Partitioning: Read-Only Partitions - можно сделать readonly отдельную партицию

20. Возможность list партицирования по нескольким столбцам:
PARTITION BY LIST (state, channel)
(
  PARTITION q1_northwest_direct VALUES (('OR','D'), ('WA','D')),
  PARTITION q1_northwest_indirect VALUES (('OR','I'), ('WA','I')),
  PARTITION q1_ca_direct VALUES ('CA','D'),
  PARTITION rest VALUES (DEFAULT)
);

21. Scheduler: Resource Queues - установка лимита ресурсов или времени на job

22. ! Появилась вьюха V$INDEX_USAGE_INFO / DBA_INDEX_USAGE для мониторинга использования индексов

23. In-Memory Expressions - возможность сохранения/предрасчета? математических операций над in-mem столбцами
 * этоже используется в In-Memory Virtual Columns - материализация расчета в памяти

24. Automatic Data Optimization Support for In-Memory Column Store - расположение данных в памяти согласно частоты использования (heat map)

25. Join Groups - для столбцов соединения в in-mem можно указать их связь, тогда они будут иметь одинаковый тип сжатия, что позволит соединять столбцы не разжимая их.

26. Expression Tracking - in-mem оптимизатор более тщательно разбирает результат математической формулы или pl/sql команды до выполнения запроса, чтобы по результату сформировать верный план.

27. Oracle Multimedia PL/SQL API - появилось api для работы с видео/аудио/изображениями в blob

28. APPROX_COUNT_DISTINCT - приблизительные агрегатные функции для оценки


Другие изменения в Oracle 12 меньше 2 версии:
HYBRID HASH распределение в параллельных запросах: http://blog.skahin.ru/2016/01/oracle_29.html#skew
Advance index compress: http://blog.skahin.ru/2015/04/oracle.html
Zone map и attribute clustering: http://blog.skahin.ru/2016/01/oracle.html#clust
Expand sql: http://blog.skahin.ru/2016/01/oracle.html#sql2
Adaptive plan

понедельник, 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 на максимальный (т.к. отсутствие блока в кэше говорит об однозначно последней версии на диске)

четверг, 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 переменными

Эта заметка краткий пересказ статьи https://habrahabr.ru/company/postgrespro/blog/275755/

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 переменные.

пятница, 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 поток посылает данные другому
 ** RANGE - данные будут разбиты на диапазоны (часто при сортировке)
 ** HASH - диапазон данных на основе их хэша (hash join, group by)
 ** RANDOM - случайная отправка
 ** 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