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

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

• Order by сортировка
• BTree индекс
• Hash Join
• Bloom filter
• Lru cache
• Hash агрегация и приблизительный DISTINCT

Следующий аспект бд - хэширование данных
Раньше я уже описывал 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 таблица цепочками.

1. Добавление элемента в хэш таблицу:
* Создаем объект и заполняем случайными парами: ключ хэширования - столбец хэширования в таблице, значение - rowid ссылка на таблице

OraHash h = new OraHash(13);
//записываем 50 случайных пар
for(int i = 0; i < 50; i++) {
   h.put(ThreadLocalRandom.current().nextInt(0, 50) , "r." + i);
}

* OraHash - является расширенной версией обычного хэш массива Hash
* В конструктор OraHash передаем размер доступной памяти под хэширование (hash_area_size) и создаем битовый массив массив (bitmap) произвольного размера (желательно больше размера хэш таблицы)
* Для установки флага битовой карты используется функция хэширования getBitmapHash - остаток от деления по числу элементов в битовой карте

//Oracle реализация хэш массива
class OraHash extends Hash {
 
  //битовая карта - принадлежность элемента к хэш массиву без запроса к самой таблице
  private boolean bitmap[];

  //кол-во элементов в битовом массиве
  public static int bitmap_size = 30;

  //размер памяти под хэширование
  public static int hash_area_size;

  //размер свободной памяти под хэширование
  public static int free_hash_area_size;

  //создание хэш массива, с выделением памяти размером _hash_area_size
    public OraHash(int _hash_area_size) {
      
      //инициализруем хэш массив размеро 0,8 от доступной памяти
      super((int) ( _hash_area_size * 0.8 ));
      
      hash_area_size = _hash_area_size;
      free_hash_area_size = hash_area_size;
      
      //инициализируем битовый массив
      bitmap = new boolean[bitmap_size];
      Arrays.fill(bitmap, false);
    } //OraHash
    
    //хэширование ключа для битовой карты
    public static int getBitmapHash(int key) {
      //остаток от деления по числу элементов в битовой карте
      return (key % bitmap_size);
    } //getHash
    
    //поместить пару ключ-значение в хэш массив
    public void put(int key, Value value) {
      //помещаем в хэш массив
      super.put(key, value);
      
      //проставляем флаг занятости в битовой карте
      bitmap[getBitmapHash(key)] = true;
    } //put
    
    ...

* OraHash вызывает родительский класс Hash
Размер хэш таблицы задается равным 0.8 от доступной памяти
Полная формула количества хэш групп = 0.8 x hash_area_size / (db_block_size * hash_multiblock_io_count)
* Ключ хэшируется функцией getHash - остаток от деления на число секций
* Если секций пуста, то создается новый список для элементов HashEntryHolder
* Если список HashEntryHolder уже есть, то ищем в списке уникальных значений HashEntry
  ** Если его нет, то создаем новый HashEntry
  ** Иначе добавляем элемент в список дублей ValueList внутри уникального списка HashEntry

//хэш массив
class Hash {
    
    //хэширование ключа
    public static int getHash(int key) {
     //остаток от деления на число секций
     return (key % TABLE_SIZE);
    } //getHash
 
    //поместим пару ключ-значение в хэш массив
    public void put(int key, Value value) {
      //получаем номер хэш секции
      int hash = getHash(key);
      
      //если секция пустая
      if (holder[hash] == null) {
        //инициализируем объектом секции
        holder[hash] = new HashEntryHolder(key, value, hash);
        //увеличиваем счетчик занятых секций
        hash_cnt++;
        
        //увеличиваем оставшиеся значения: общее число, уникальное число и число в памяти
        uniq_cnt++;
        holder[hash].addCnt();
      } else {
        //нужная секция уже есть
        HashEntry entry = holder[hash].table;
        
        //обходим список уникальных значений для поиска нашего ключа
        while (entry.next != null && entry.key != key) {
            entry = entry.next;
        }
        
        //если есть, то добавляем значение в список повторяющися значений
        if (entry.key == key) {
            entry.add(value);
        } else {
          //иначе создаем новое уникальное значение
          entry.next = new HashEntry(key, value);
          //увеличиваем счетчики
          uniq_cnt++;
        }
        holder[hash].addCnt();
      }
        
      cnt++;
    } //put
    
    ...

* При добавлении элемента происходит дополнительная проверка на доступность памяти в hash_area для нового элемента: HashEntryHolder.addCnt()
Если места нет, то элемент пишется на диск:

//обертка хэш секции, для возможности хранения дополнительных параметров
class HashEntryHolder {
 //инкремент числа элементов
 public void addCnt() {
  cnt++;
  
  //если элемент еще влезает в выделенную память
  if(OraHash.free_hash_area_size > 0) { 
   //уменьшаем размер доступной памяти
   OraHash.free_hash_area_size--;
   //увеличиваем счетчик числа элементов в памяти
   cnt_mem++;
  }
 } //addCnt
  
  ...

* В результате вставки получается хэш таблица (вывод функции dump). Хэширующая функция - остаток от деления на 10:

[0] (cnt: 6, mem: 1) = { [40: <r.9>], [0: <r.14>], [30: <r.33, r.28, r.18>], [20: <r.25>], } 
[1] (cnt: 2, mem: 1) = { [41: <r.10>], [21: <r.15>], } 
[2] (cnt: 5, mem: 1) = { [2: <r.13, r.0>], [12: <r.45, r.16>], [32: <r.20>], } 
[3] (cnt: 8, mem: 5) = { [43: <r.36, r.12, r.4>], [13: <r.42, r.6>], [3: <r.8, r.7>], [23: <r.17>], } 
[4] (cnt: 6, mem: 2) = { [24: <r.5, r.3>], [34: <r.24>], [44: <r.40, r.39>], [4: <r.43>], } 
[5] (cnt: 5, mem: 0) = { [5: <r.31, r.19>], [25: <r.32, r.30>], [35: <r.48>], } 
[6] (cnt: 5, mem: 1) = { [16: <r.11>], [46: <r.26>], [36: <r.37>], [26: <r.49, r.41>], } 
[7] (cnt: 5, mem: 1) = { [27: <r.1>], [47: <r.35, r.23, r.21>], [7: <r.46>], } 
[8] (cnt: 5, mem: 1) = { [48: <r.2>], [18: <r.22>], [28: <r.44, r.27>], [8: <r.38>], } 
[9] (cnt: 3, mem: 0) = { [49: <r.29>], [9: <r.34>], [39: <r.47>], } 

2. Реорганизация хэш таблицы:
По таблице видно, что ни одна секция не находится целиком в памяти, хотя каждая по отдельности меньше выделенной памяти (13)
Для решения этой проблемы секции в таблице реорганизуются, чтобы максимальное число секций оказалось в памяти:

//Oracle реализация хэш массива
class OraHash extends Hash {
  //реорганизация хэш секций в памяти, с целью поместить как можно больше целых секций в памяти
  public void reorg() {
    
    //1 цикл - ищем секцию максимально размещенную в памяти
    int hash_max = -1;
    int elems_in_mem = 0;
    for(int i = 0; i < this.holder.length; i++) {
      if( this.holder[i] != null && //есть секция
          this.holder[i].cnt_mem > elems_in_mem && //элементов в памяти секции больше, чем в предыдущем кандидате 
          this.holder[i].cnt_mem < this.holder[i].cnt &&  //не все элементы в памяти
          !this.holder[i].is_reorg && //секция еще не была просмотрена
          this.holder[i].cnt <= hash_area_size //число элементов меньше выделенной памяти
          ) {
        elems_in_mem = this.holder[i].cnt_mem;
        hash_max = i; //новый кандидат для реоганизации
      }
    }
    //кандидат для реорганизации не нашелся
    if(hash_max < 0) return;
    
    //System.out.println ( "max free mem hash = " + hash_max);
    
    //помечаем секцию реорганизованной
    this.holder[hash_max].is_reorg = true;
    
    
    //2 цикл - выгружаем другие секции из памяти и загружаем элементы в память целевой секции
    for(int i = 0; i < this.holder.length; i++) {
      if( i != hash_max && //просматриваемая секция не кандидат
          this.holder[i] != null &&  //секция существует
          this.holder[i].cnt_mem > 0) { //у секции есть элементы в памяти
        
        //определяем число элементов целевой секции на диске
        int elems_in_disk = this.holder[hash_max].cnt - this.holder[hash_max].cnt_mem;
        
        if(elems_in_disk <= 0) break;
        
        //если число элементов на диске, больше доступного числа элементов в памяти у донора
        if(elems_in_disk > this.holder[i].cnt_mem) {
          //то максимум что можно забрать = число элементов в памяти донора
          elems_in_disk = this.holder[i].cnt_mem;
        }
        
        //выгружаем элементы из памяти донора
      this.holder[i].cnt_mem = this.holder[i].cnt_mem - elems_in_disk;
      
      //загружаем элементы в память у целевой секции
      this.holder[hash_max].cnt_mem = this.holder[hash_max].cnt_mem + elems_in_disk;
      
      } //if
    }
    
    //рекурсивно повторяем для других секции, возможно есть еще секции которые можно разместить целиком в памяти
    reorg();
    
  } //reorg
  
  ...

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

[0] (cnt: 6, mem: 0) = { [40: <r.9>], [0: <r.14>], [30: <r.33, r.28, r.18>], [20: <r.25>], } 
[1] (cnt: 2, mem: 0) = { [41: <r.10>], [21: <r.15>], } 
[2] (cnt: 5, mem: 0) = { [2: <r.13, r.0>], [12: <r.45, r.16>], [32: <r.20>], } 
[3] (cnt: 8, mem: 0, reorg) = { [43: <r.36, r.12, r.4>], [13: <r.42, r.6>], [3: <r.8, r.7>], [23: <r.17>], } 
[4] (cnt: 6, mem: 0, reorg) = { [24: <r.5, r.3>], [34: <r.24>], [44: <r.40, r.39>], [4: <r.43>], } 
[5] (cnt: 5, mem: 0) = { [5: <r.31, r.19>], [25: <r.32, r.30>], [35: <r.48>], } 
[6] (cnt: 5, mem: 3, reorg) = { [16: <r.11>], [46: <r.26>], [36: <r.37>], [26: <r.49, r.41>], } 
[7] (cnt: 5, mem: 5, reorg) = { [27: <r.1>], [47: <r.35, r.23, r.21>], [7: <r.46>], } 
[8] (cnt: 5, mem: 5, reorg) = { [48: <r.2>], [18: <r.22>], [28: <r.44, r.27>], [8: <r.38>], } 
[9] (cnt: 3, mem: 0) = { [49: <r.29>], [9: <r.34>], [39: <r.47>], } 

3. Поиск элемента в хэш таблице:
* В первую очередь тестируем элемент на наличии в битовом массиве, без обращения к хэш таблице bitmap[getBitmapHash(key)

//Oracle реализация хэш массива
class OraHash extends Hash {
    //получить список значений по ключу
    public ValueList get(int key) {
     
     //быстрая дополнительная проверка по битовой карте, без обращения к хэш таблице
     int hash = getBitmapHash(key);
     
     if(!bitmap[getBitmapHash(key)]) return null;
     
     return super.get(key);
    } //get
    ...

* Если элемент найден в битовом массиве и хэш секция находится в памяти, то ищем элемент в хэш массиве.
Если элементов с таким значеним несколько, то возвращается список этих элементов ValueList:

//хэш массив
class Hash {
 
    //получить список значений по ключу
    public ValueList get(int key) {
     //получаем номер хэш секции
      int hash = getHash(key);
      
      //хэш секции нет - элемент не найден
      if (holder[hash] == null) {
        return null;
      } else {
        //получаем уникальный список значение в секции
          HashEntry entry = holder[hash].table;
          
          //последовательно обходим список, пока не найдем наш ключ
          while (entry != null && entry.key != key) {
            entry = entry.next;
          }
          //если не нашлось, то это коллизия - возвращаем пусто
          if (entry == null) {
            return null;
          } else {
            //нашлось - возвращаем список повторяющихся значений
            return entry.value;
          }
      }
    } //get
    ...

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

Т.е. если в память помещается только одна любая секция из левой таблицы, то для полного хэширования понадобится:
* 1 раз считать левую таблицу, чтобы ее прохэшировать и записать хэш - 1 секция на диск (2 I/O)
* 1 раз считать правую таблицу, чтобы также ее прохэшировать и записать на диск (2 I/O)
* Последовательно по 1 секции еще раз считать левую таблицу по 1 секции в память (1 I/O)
* Последовательно по 1 секции правой таблицы проверить наличие данных в левой (1 I/O)
Т.е. в итоге получается 6 считываний + записей левой+правой таблицы, против 2 считываний (I), если хэш таблица левой таблицы целиком помещается в память.
Итоговая стоимость соединения в 1 проход максимум в 3 раза больше, чем соединение таблиц в памяти.
Если в память помещается более 1 секции, то стоимость также уменьшается пропорционально, т.к. нужно меньшее число считываний+записей с диска.

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

Полную реализацию Oracle Hash можно посмотреть на github