Оптимизация хранения данных в bigdata

• ORC: формат файла
  • Параметры по умолчанию
  • Максимальная доля уникальных значений для создания справочника
  • Количество строк в stride
• Партицирование
• Кластеризация
  • Время вставки
  • Select по ключу кластеризации
  • Отличие Hive кластеризации от Spark
• Сортировка
  • Размер данных
  • Время вставки
  • Select по первому ключу сортировки
  • Select по второму ключу сортировки
  • Select по ключу без сортировки
  • Sort Merge Bucket Join
• ORC: Bloom filter
  • Время вставки
  • Размер данных
  • Select по ключу bloom filter
  • Увеличение False positive Bloom filter
• Ускорение вставки в кластеризованную таблицу с динамическим партицированием
• Сравнение результатов
• Сравнение ORC с Parquet
  • Скорость полного чтения
  • Скорость чтения с фильтром по полю CLUSTERED
  • Скорость чтения с фильтром по полю с Bloom filter
  • Распространенность форматов
  • Итоговое сравнение
• Hive: Predicate pushdown
  • Join predicate pushdown
  • Partition pruning
• Hive: BroadCast Join
• Skew Join
  • Проявление
  • Исправление через Union и Broadcast
  • Исправление через Salting
  • Исправление встроенными средства Hive
  • Исправление в Spark
• Hive 3: Materialized view
• Hive LLAP
• Iceberg
  • Схема формата данных
  • Конкурентный доступ
  • Улучшение партицирования
  • Версионирование
  • Компакция и распределение

LSM дерево: быстрый доступ по ключу в условиях интенсивной вставки

В условиях интенсивной вставки для быстрого доступа к данным обычные btree индексы не подходят.
Во многих базах (Bigtable, HBase, LevelDB, MongoDB, SQLite4, Tarantool, RocksDB, WiredTiger, Apache Cassandra, и InfluxDB ) используется LSM-дерево (Log-structured merge-tree — журнально-структурированное дерево со слиянием)
LSM дерево служит для хранения ключ-значения.
В данной статье рассмотрим двухуровневое дерево. Первый уровень целиком находится в памяти, вторая половина на диске.
Вставка идет всегда в первую часть в памяти, а поиск из всех частей. Когда размер данных в памяти превышает определенный порог, то она записывается на диск. После чего блоки на диске объединяются в один.
Рассмотрим алгоритм по частям:

1. Все записи в дереве маркируются порядковым номером glsn , при каждой вставке этот счетчик увеличивается

Структура для хранения ключа-значения и порядкового номера:

//запись с ключ-значение
class SSItem {
 Integer key;
 String value;
 //+ идентификатор последовательности вставки
 Integer lsn;
 
 SSItem(Integer key, String value, Integer lsn) {
  this.key = key;
  this.value = value;
  this.lsn = lsn;
 }

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

class MemSSTable { 
 
 //из-за хэша нет поиска по диапазону
 HashMap<Integer, SSItem> itms = new HashMap<Integer, SSItem>();
 

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

 void SaveToDisk() throws FileNotFoundException, UnsupportedEncodingException {
  indx.path = "sstable_" + indx.max_lsn + ".dat";
  PrintWriter writer = new PrintWriter(indx.path, "UTF-8");
  Integer pad = 0;
  //последовательно пишем 10 байт с длиной значения и само значение
  for(Entry<Integer, SSItem> entry : itms.entrySet()) {
   SSItem itm = entry.getValue();
   String val = itm.get();
   writer.print( val );
   //регистрируем в индексе смещения в файле
   indx.keys.put(itm.key, pad);
   pad = pad + val.length();
  }
  writer.close();
  
  LSMTree.indexes.add(indx);
 } //SaveToDisk

4. Получается, что половина всех данных у нас хранится в хэше в памяти, а остальное в виде файлов на диске.
Чтобы не перебирать все файлы на диске создается дополнительная индексная структура, которая будет хранить метаинформацию о файлах в памяти:

//индекс над таблицей с даными
class SSTableIndex {
 //метаданные:
 //минимальный и максимальный ключи в таблице
 Integer min_key;
 Integer max_key;
 //минимальный и максимальный порядковый lsn
 Integer min_lsn;
 Integer max_lsn;
 
 //если таблица на диске, то путь до файла
 String path;
 
 //ключ - смещение ключа в файле
 HashMap<Integer, Integer> keys = new HashMap<Integer, Integer>();
 
 //добавить ключ в индекс
 void add(Integer k) {
  //также обновляем метаданные
  max_lsn = LSMTree.glsn;
  if(min_lsn == null) min_lsn = max_lsn;
  if(min_key == null || k < min_key) min_key = k;
  if(max_key == null || k > max_key) max_key = k;
  //добавление идет в память в хэш таблицу, на первом этапе смещения в файле нет
  keys.put(k, 0);
 }

5. Управляющий объект всего дерева хранит ссылку на таблицу с данными в памяти и на мета-индексы данных на диске:

public class LSMTree {
 
 static int glsn = 0;
 //максимальный размер, после которого таблица должна быть скинута на диск
 //для упрощения алгоритма = числу записей, а не размеру в байтах
 final static int max_sstable_size = 10; 
 
 //текущая таблица в памяти, куда вставляем данные
 MemSSTable MemTable;
 
 //все индексы, даже для таблиц на диске, хранятся в памяти
 static LinkedList<SSTableIndex> indexes = new LinkedList<SSTableIndex>();

6. Когда все объекты описаны, давайте посмотрим как происходит добавление нового элемента.
Добавление всегда идет в таблицу в памяти, что гарантирует быструю вставку:

public class LSMTree {
 //....
 
 //добавить запись
 public void add(Integer k, String v) {
  MemTable.add(k, v);
 }

Подробней логика добавления в таблицу в памяти:
* Увеличиваем глобальный счетчик элементов LSMTree.glsn
* Если число элментов превысило порог, то таблица скидывается на диск и очищается
В реальности это конечно не число элементов, а объем в байтах.
* Создается новый элемент SSItem
* И доблавляется в хэш массив
Причем, если элемент до этого уже существовал, то он перезаписывается.
В реальности хранятся все записи, чтобы была возможность поддержки транзакционности.
* Кроме этого в индексе обновляются метаданные indx.add

class MemSSTable { 
 //.....
 
 //добавить новый элемент
 void add(Integer k, String v) {
  //увеличиваем глобальный счетчик операций glsn
  LSMTree.glsn++;
  
  //если размер превышает, 
  if(itms.size() >= LSMTree.max_sstable_size) {
   try {
    //то сохраняем таблицу на диск
    //в реальных движках используется упреждающая фоновая запись
    //когда папять заполнена на N% (n<100), то данные скидываются на диск заранее, чтобы избежать фриза при сбросе памяти и записи на диск
    SaveToDisk();
   } catch (FileNotFoundException | UnsupportedEncodingException e) {
    e.printStackTrace();
    return;
   }
   //очищаем данные под новые значения
   indx = new SSTableIndex();
   itms = new HashMap<Integer, SSItem>();
  }
  
  //обновляем медаданные в индексе
  indx.add(k);
  
  SSItem itm = new SSItem(k, v, indx.max_lsn);
  
  //в моей реализации, при повторе ключ перезаписывается
  //т.е. транзакционность и многоверсионность тут не поддерживается
  itms.put(k,  itm);
  
 } //add

Если после вставки нового элемента старые данные оказались на диске, то в метаданных индекса прописывается ссылка на точное смещение в файле:

class SSTableIndex {
 //...
 
 //если таблица на диске, то путь до файла
 String path;
 
 //ключ - смещение
 HashMap<Integer, Integer> keys = new HashMap<Integer, Integer>();

7. С вставкой разобрались, теперь обратная операция - поиск элемента в дереве:
* Сперва мы проверяем наличие ключа в хэш таблице в памяти. Если элемент нашелся, то на этом все.
* Если элемента нет, то мы пробегамся по всем метаиндексам в поиске нашего ключа.
* проверяем, что ключ входит в диапазон indx.min_key - indx.max_key индекса
* И для полной точности проверяем наличие ключа в хэше ключей indx.keys.containsKey
* Если элемент нашелся, то это еще не конец, цикл продолжается, пока мы не переберем все индексы.
Т.к. ключ может добавляться несколько раз в разные промежутки времени.
* Из всех совпадений выбираем индекс с максимальным счетчиком вставки - это последнее изменение ключа

public class LSMTree {
 //.....
 
 //получить значение по ключу
 String getKey(Integer key) {
  //сперва смотрим в памяти
  String val = MemTable.getKey(key);
  
  if(val == null) {
   SSTableIndex indx_with_max_lsn = null;
   //потом таблицу по индексам, которая содержит наш ключ
   //если содержится в нескольких, то берем с максимальным lsn, т.к. это последнее изменение
   for (SSTableIndex indx : indexes) {
    Integer max_lsn = 0;
    if(key >= indx.min_key && key <= indx.max_key && max_lsn < indx.max_lsn ) {
     if(indx.keys.containsKey(key)) {
      max_lsn = indx.max_lsn;
      indx_with_max_lsn = indx;
     }
    }
   }
   //читаем из таблицы с диска
   if(indx_with_max_lsn != null) {
    try {
     return indx_with_max_lsn.getByPath(key);
    } catch (IOException e) {
     e.printStackTrace();
    }
   }
  }
  
  return val;
 }

* Определим нужный индекс обращаемся по нему к таблице на диске:
** Открываем нужный файл
В реальности, скорей всего, файы постоянно держатся открытыми для экономии времени.
** Следуя смещенями из индекса переходим к нужной точке файла file.seek
** И считываем значение file.read

class SSTableIndex {
 //...
 
 //получить значение ключа из открытого файла
 String getByPath(Integer key, RandomAccessFile file) throws IOException {
  //получаем смещение в файле для ключа из индекса
  Integer offset = keys.get(key);
  
  //смещаемся в файле
  file.seek(offset);
  
  //резервируем 10 байт под переменную с длинной значения
  byte[] lenb = new byte[10];
  file.read(lenb, 0, 10);
  
  Integer len = Integer.parseInt(new String(lenb, StandardCharsets.UTF_8));
 
  file.seek(offset + 10);
  
  //считываем значение
  byte[] valb = new byte[len];
  file.read(valb, 0, len);
  
  return new String(valb, StandardCharsets.UTF_8);
 } //getByPath
 
 //получить значение ключа с диска
 String getByPath(Integer key) throws IOException {
  if(!keys.containsKey(key)) return null;
  
  RandomAccessFile file = new RandomAccessFile(path, "r");
  
  String val = getByPath(key, file);
  
  file.close();

  return val;
 }

8. Т.к. ключ может вставляться неограниченное число раз, то со временем он может находится в нескольких файлах на диске одновременно.
Также, если бы LSM дерево поддерживало транзакционность, то в файлах также хранились бы разные версии одного ключа (изменения или удаления).
Для оптимизации последующего поиска применяется операция слияния нескольких файлов в один:
* Сортируем индексы по убыванию lsn
* Последовательно считываем элементы из первого индекса и записываем в новый
* Если элемент уже присутствует в объединенном индексе, то он пропускается
* Создается новый единственный файл и индекс со всеми ключами и значениями
* Старые файлы и индексы удаляются

public class LSMTree {
 //....
 
 //объединить несколько таблиц на диске в 1 большую
 void merge() throws IOException {
  Integer min_key = null;
  Integer max_key = null;
  Integer min_lsn = null;
  Integer max_lsn = null;
  
  //сортируем таблицы по убыванию lsn
  //чтобы вначале были самые свежие ключи
  Collections.sort(indexes, new Comparator<SSTableIndex>() {
   @Override
   public int compare(SSTableIndex o1, SSTableIndex o2) {
    if(o1.max_lsn > o2.max_lsn) {
     return -1;
    } else if(o1.max_lsn < o2.max_lsn) {
     return 1;
    }
    return 0;
   }
  });
  
  SSTableIndex merge_indx = new SSTableIndex();
  
  Integer pad = 0;
  merge_indx.path = "sstable_merge.dat";
  PrintWriter writer = new PrintWriter(merge_indx.path, "UTF-8");
  
  //пробегаемся по всем индексам, чтобы слить в 1
  for (SSTableIndex indx : indexes) {
   if(min_lsn == null || indx.min_lsn < min_lsn) min_lsn = indx.min_lsn;
   if(min_key == null || indx.min_key < min_key) min_key = indx.min_key;
   if(max_key == null || indx.max_key > max_key) max_key = indx.max_key;
   if(max_lsn == null || indx.max_lsn > max_lsn) max_lsn = indx.max_lsn;
   
   RandomAccessFile file = new RandomAccessFile(indx.path, "r");
   
   //т.к. данные в таблицах не упорядочены, это приводит к рандомным чтениям с диска
   //в реальности делают упорядочнный по ключу массив, чтобы делать быстрые последовательные чтения
   for(Entry<Integer, Integer> entry : indx.keys.entrySet()) {
    //оставляем запись только с максимальным lsn
    Integer key = entry.getKey();
    if(!merge_indx.keys.containsKey(key)) {
     String val = indx.getByPath(key, file);
     
     SSItem itm = new SSItem(key, val, 0);
     String itmval = itm.get();
     
     writer.print( itmval );
     merge_indx.keys.put(key, pad);
     pad = pad + itmval.length();     
    }
   }
   //записываем и удаляем старые файлы
   file.close();
   //delete
   File fd = new File(indx.path);
   fd.delete();
  }  
  
  merge_indx.min_lsn = min_lsn;
  merge_indx.min_key = min_key;
  merge_indx.max_key = max_key;
  merge_indx.max_lsn = max_lsn;
  
  writer.close();
  
  //переименовываем к обычному имени
  File fd = new File(merge_indx.path);
  merge_indx.path = "sstable_" + merge_indx.max_lsn + ".dat";
  File fdn = new File(merge_indx.path);
  fd.renameTo(fdn);
  
  indexes = new LinkedList<SSTableIndex>();
  indexes.add(merge_indx);
  
 } //merge

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


Полный код класса LSM дерева можно посмотреть на github

Мониторинг нагрузки и особенности индексирования Sap Hana

Предоставления для мониторинга нагрузки на субд sap hana:

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

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

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

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

Том Кайт: Oracle для профессионалов

Третье издание книги Тома Кайта: Oracle для профессионалов, включающее особенности Oracle 12.

1-9. 1-9 главы - внутренняя работа субд oracle
10. Глава 10 - таблицы
11. Глава 11 - индексы
12. Глава 12 - типы данных
13. Глава 13 - секционирование
14. Глава 14 - параллельное выполнение
15. Глава 15 - загрузка и выгрузка данных

Некоторые особенности индексного поиска в Oracle

1. Зачем создавать индексы на ссылочных полях (FK – foreign key) ?

* Очевидно для оптимизации процессов соединения таблиц.
* Но есть и другое, не менее важное, предназначение:
Если таблица фактов в схеме «звезда» ссылается (FK) на таблицу измерений, и на ссылочном поле нет индекса, то DML (Insert / Update / Delete ) операция над таблицей измерений заблокирует таблицу фактов на изменение целиком.
Если на ссылочном поле есть индекс, то произойдет блокировка только нужных строк из таблицы фактов, тех которые затрагивает изменение в таблице измерений.
Пример: таблица с данными продаж (факты) и таблица кассовых мест (измерения), с некоторой периодичностью происходит изменение списка кассовых мест, то на ссылочном поле кассовое место / таблица продаж, желательно создать индекс.
Если этого не сделать, то данные в продажах будут заблокированы до commit / rollback обновления списка кассовых мест.

2. Compressed index

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

compressed N

где N – кол-во колонок. Пример: индекс по 3 полям, первые 2 из которых малоселективны (online, status)
Индекс без сжатия

Online,0,AAAPvCAAFAAAAFaAAa
Online,0,AAAPvCAAFAAAAFaAAg
Online,0,AAAPvCAAFAAAAFaAAl
Online,2,AAAPvCAAFAAAAFaAAm
Online,3,AAAPvCAAFAAAAFaAAq
Online,3,AAAPvCAAFAAAAFaAAt

Индекс со сжатием

Online,0
AAAPvCAAFAAAAFaAAa
AAAPvCAAFAAAAFaAAg
AAAPvCAAFAAAAFaAAl
Online,2
AAAPvCAAFAAAAFaAAm
Online,3
AAAPvCAAFAAAAFaAAq
AAAPvCAAFAAAAFaAAt

В этом случае группа одинаковых данных N первых колонок будут сжаты в одну запись в индексе, а ROWID самих записей будут помещены в вспомогательную структуру. Уменьшение числа листов индекса соответственно ускорит доступ к данным.
Хочу заметить, что данный способ применим только для низко селективных столбцов. Если данные достаточно уникальны, то создание доп. структур на хранение записей только создаст дополнительные накладные расходы!
Так же стоит заметить, что без compressed первый столбцы индекса наоборот должны содержать наиболее селективные данные, чтобы Oracle за меньшее кол-во операций мог дойти до уникальных данных.

3. Advanced compress - oracle 12

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

Пример:
0. Обычный индекс
1. Индекс с компрессией 1 - занимает 3200 блоков
2. Индекс с компрессией 2 - занимает 2816 блоков
3. ADVANCED LOW - занимает 2816 блоков, т.е. Oracle самостоятельно подобрал уровень компрессии = 2
4. ADVANCED LOW - но в начале плохосжимаемый селективный столбец. Oracle не применяет компрессии, выходит теже 3584 блоков.
Т.е. за порядком столбцов все также надо следить, можно только не делать analyze index, чтобы узнать оптимальный уровень компрессии.

drop table t$t purge;
  
create table t$t as select 1 c1, round( dbms_random.VALUE(1, 10)) c2, level as c3
from dual connect by level < 1000000;
  
create index idx_t$t_0      on t$t(c1, c2, c3, 1);
create index idx_t$t_1      on t$t(c1, c2, c3, 2)  COMPRESS 1;
create index idx_t$t_2      on t$t(c1, c2, c3, 3)  COMPRESS 2;
create index idx_t$t_low    on t$t(c1, c2, c3, 4)  COMPRESS ADVANCED LOW;
create index idx_t$t_c3_low on t$t(c3, c1, c2, 5)  COMPRESS ADVANCED LOW;

 
select segment_type, segment_name, bytes, blocks from SYS.USER_SEGMENTS where segment_name like '%T$T%';

SEGMENT_TYPE       SEGMENT_NAME             BYTES     BLOCKS
------------------ ----------------------- ---------- ----------
TABLE              T$T                      18874368       2304
INDEX              IDX_T$T_0                29360128       3584
INDEX              IDX_T$T_1                26214400       3200
INDEX              IDX_T$T_2                23068672       2816
INDEX              IDX_T$T_LOW              23068672       2816
INDEX              IDX_T$T_C3_LOW           29360128       3584

 6 rows selected 

Скрипт определения индексов для сжатия со списком колонок.
Формула определения необходимости сжатия колонки: произведение кол-ва уникальных значений в текущей и предыдущих колонках < 200 (значение случайное)
Индексы сортируются по значению: кол-во строк в индексе / произведение кол-ва уникальных значений в текущей и предыдущих колонках * кол-во колонок для сжатия
Таким образом вначале будут индексы, которым сильней необходимо сжатие

with t as (
  select /*+ MATERIALIZE */ I.TABLE_NAME, i.index_name, I.NUM_ROWS, C.COLUMN_POSITION, C.COLUMN_NAME, s.NUM_DISTINCT,
    CASE WHEN
     -- EXP (SUM (LN ( col )) ==  MULTPL(col)
     EXP (SUM (LN (s.NUM_DISTINCT)) OVER(PARTITION BY I.TABLE_NAME, i.index_name ORDER BY C.COLUMN_POSITION))  <= 200
    THEN 
      1
    END as NEED_COMPRESS
  from dba_indexes i 
  join DBA_IND_COLUMNS c on C.INDEX_OWNER = i.OWNER AND C.INDEX_NAME = i.index_name AND C.TABLE_NAME = I.TABLE_NAME
  join DBA_TAB_COL_STATISTICS s on S.OWNER = i.OWNER AND S.TABLE_NAME = I.TABLE_NAME AND S.COLUMN_NAME = C.COLUMN_NAME
  WHERE i.OWNER = :OWN AND i.COMPRESSION = 'DISABLED' AND i.INDEX_TYPE = 'NORMAL'
  AND i.LEAF_BLOCKS > 0
  order by I.TABLE_NAME, i.index_name, C.COLUMN_POSITION
)
select TABLE_NAME, index_name, NUM_ROWS, NUM_DISTINCT, COMPR_COLS, COMPR_FACTOR
from (
  select TABLE_NAME, index_name, MAX(NUM_ROWS) as NUM_ROWS, 
    ROUND( EXP (SUM (LN (CASE WHEN NEED_COMPRESS = 1 THEN NUM_DISTINCT END))) ) as NUM_DISTINCT,
    LISTAGG(CASE WHEN NEED_COMPRESS = 1 THEN COLUMN_NAME END, ', ') WITHIN GROUP (ORDER BY COLUMN_POSITION) as COMPR_COLS,
    ROUND( MAX(NUM_ROWS) / SUM(CASE WHEN NEED_COMPRESS = 1 THEN NUM_DISTINCT END) ) * COUNT(DISTINCT CASE WHEN NEED_COMPRESS = 1 THEN COLUMN_POSITION END) as COMPR_FACTOR,
    COUNT(DISTINCT CASE WHEN NEED_COMPRESS = 1 THEN COLUMN_POSITION END) as COLUMN_COUNT
  from t
  WHERE NEED_COMPRESS > 0
  GROUP BY TABLE_NAME, index_name
)
order by COMPR_FACTOR DESC nulls last, TABLE_NAME, index_name
FETCH FIRST 500 ROWS ONLY;

Предварительный результат сжатия индекса можно определить средствами Oracle:

analyze index "IDX" validate structure;
select * from index_stats;

Последние 2 столбца index_stats дадут информацию о желательном уровне сжатия и % уменьшения индекса после компрессии.

4. reverse index

Обычный btree index, но данные этого индекса развернуты наоборот.
Такой индекс хорошо подходит для последовательно генерируемых данных, к примеру для первичного ключа, создаваемого по sequence.
Если использовать обычный индекс то данные будут писаться последовательно в блоки, что может увеличить конкуренцию за диск при вставке или выборке.
Пример:
Первичный ключ:
* Обычный индекс: 12345, 12346, 12347
Данные пишутся на диск последовательно.
* Реверсивный индекс: 54321, 64321, 74321
Видно, что reverse данные хорошо будут раскиданы по диску.
Что должно уменьшить число событий «buffer busy» и «read by other session»

5. Skip scan

Уникальная фича Oracle, которой нет почти ни у одной субд. Возможность поиска по правой части индекса.
Skip scan индекса может быть применен, если первые (левые или лидирующие) столбцы малоселективны. Тогда Oracle может создать логические подиндексы для каждой записи левой части индекса.
Пример:
Индекс по полям: GENDER, EMAIL – GENDER малоселективная левая часть индекса, EMAIL высокоселективная правая часть.
При запросе вида

SELECT * FROM T WHERE EMAIL = ?

Будет использоваться Skip scan, и запрос на внутреннем уровне будет преобразован к виду:

select * from T where gender = 'F' AND EMAIL = ?
union all
select * from T WHERE gender = 'M' AND EMAIL = ?

Если первый столбец достаточно селективен, что встречается чаще (см. п.2), то Skip scan использоваться не будет.

6. Способы доступа к индексу.

a. index scan - последовательное чтение по связанному списку. Данные в этом случае будут отсортированы по индексу.
b. index fast full scan - многоблочно читается сегмент целиком и выбираются блоки индекса. Может быть применено только если not null фильт или колонка. В этом случае данные получаются неотсортированными по индексу.
c. index range scan - сканирование по диапазону. Может использоваться только одно условие отличное от =


7. Характеристики индексов.

a. clustering factor index - как записи в индексе соответствуют (упорядочены) данным в таблице
* в идеале clustering factor = числу блоков, т.е. при чтении из индекса не надо прыгать по разным блокам
* если clustering factor = числу строк, то при запросе из индекса будет много переходов в разные блоки, что приведет к огромному числу чтений


Дополнительная информация по внутреннему устройству индекса в статье Oracle: реализация btree индекса

8. Оптимизация доступа по индексу при Nested Loops.

** Обычный NL без оптимизации (Oracle 9)
Наиболее долгая операция при поиске по индексу, это рандомный доступ (scaterred) к таблице по rowid из последовательного индекса (sequencial).
В случае hdd большую часть времени будет выполняться позиционирование головки винта, чем собственно чтение данных.

----------------------------------------------
| Operation                 |  Name    |  Rows |
------------------------------------------------
| SELECT STATEMENT          |          |   225 |
|  NESTED LOOPS             |          |   225 |
|   TABLE ACCESS BY INDEX RO|T2        |    15 |
|    INDEX FULL SCAN        |T2_I1     |    15 |
|   TABLE ACCESS BY INDEX RO|T1        |     3K| 
|    INDEX RANGE SCAN       |T1_I1     |     3K|
------------------------------------------------

** Prefetching (Oracle 10) - читает в буферный кэш смежные данные, в надежде, что они пригодятся
Чем хуже фактор кластеризации (на основе статистики), тем больше блоков читается за раз (multy block read)

-----------------------------------------------------------------
| Id  | Operation                     | Name  | Starts | E-Rows |
-----------------------------------------------------------------
|   0 | SELECT STATEMENT              |       |      0 |        |
|   1 |  TABLE ACCESS BY INDEX ROWID  | T1    |      1 |     15 |
|   2 |   NESTED LOOPS                |       |      1 |    225 | --225 строк, но всего 15 запросов из T1_I1 (блоки читаются не по одному, а по mbrc за раз)
|*  3 |    TABLE ACCESS BY INDEX ROWID| T2    |      1 |     15 |
|   4 |     INDEX FULL SCAN           | T2_I1 |      1 |   3000 |
|*  5 |    INDEX RANGE SCAN           | T1_I1 |     15 |     15 |
-----------------------------------------------------------------

** batching (Oracle 11-12) - накапливается rowid и читает их потом скопом и многопоточно (multy block read)
Чем хуже фактор кластеризации (на основе реальных запросов из индекса-таблицы), тем больше блоков читается за раз (mbrc)

-----------------------------------------------------------------
| Id  | Operation                     | Name  | Starts | E-Rows |
-----------------------------------------------------------------
|   0 | SELECT STATEMENT              |       |      1 |        |
|   1 |  NESTED LOOPS                 |       |      1 |    225 | --накапиливается несколько rowid
|   2 |   NESTED LOOPS                |       |      1 |    225 |
|*  3 |    TABLE ACCESS BY INDEX ROWID| T2    |      1 |     15 |  -- выполняется параллельный селект
|   4 |     INDEX FULL SCAN           | T2_I1 |      1 |   3000 |
|*  5 |    INDEX RANGE SCAN           | T1_I1 |     15 |     15 |
|   6 |   TABLE ACCESS BY INDEX ROWID | T1    |    225 |     15 |  -- выполняется параллельный селект
-----------------------------------------------------------------

Batching на HDD диске может дать 10 кратное ускорение, а на SSD до 2 раз.

9. Bitmap, bitmap join index.

https://docs.oracle.com/database/121/DWHSG/schemas.htm#DWHSG9042
+ Содержит NULL
+ Лучше использовать на столбцах с небольшим числом уникальных значений
Т.к. размер растет от числа значений:
* по X будут все возможные значений в колонке
* по Y сами строки
+ Главное преимущество: возможность комбинирования нескольких индексов при AND, OR, NOT
- при вставке блокируется часть со вставляемым значением целиком

Bitmap join индекс содержит значения пересечения левой и правой таблицы:

CREATE BITMAP INDEX sales_cust_gender_bjix
ON sales(customers.cust_gender)
FROM sales, customers
WHERE sales.cust_id = customers.cust_id;

Sales.rowid: gender(M) gender(F)
Sales.rowid1 0         0
Sales.rowid2 0         1
Sales.rowid3 1         0
...

10. Bitmap и Star Transformation

Оптимизация, при котором join заменяется на AND комбинацию bitmap индексов:

SELECT ch.channel_class, c.cust_city, t.calendar_quarter_desc,
   SUM(s.amount_sold) sales_amount
FROM sales s, times t, customers c, channels ch
WHERE s.time_id = t.time_id
AND   s.cust_id = c.cust_id
AND   s.channel_id = ch.channel_id
AND   c.cust_state_province = 'CA'
AND   ch.channel_desc in ('Internet','Catalog')
AND   t.calendar_quarter_desc IN ('1999-Q1','1999-Q2')
GROUP BY ch.channel_class, c.cust_city, t.calendar_quarter_desc;

Запрос будет преобразован к виду:

SELECT ... FROM sales
WHERE time_id IN
  (SELECT time_id FROM times 
   WHERE calendar_quarter_desc IN('1999-Q1','1999-Q2'))
   AND cust_id IN
  (SELECT cust_id FROM customers WHERE cust_state_province='CA')
   AND channel_id IN
  (SELECT channel_id FROM channels WHERE channel_desc IN('Internet','Catalog'));

При этом должны быть индексы на полях: sales.time_id, sales.cust_id, sales.channel_id.
Они будут объединены через BITMAP AND в один и будут использоваться для фильтрации sales:

SELECT STATEMENT
 SORT GROUP BY
  HASH JOIN
   TABLE ACCESS FULL                          CHANNELS
   HASH JOIN
    TABLE ACCESS FULL                         CUSTOMERS
    HASH JOIN
     TABLE ACCESS FULL                        TIMES
     PARTITION RANGE ITERATOR
      TABLE ACCESS BY LOCAL INDEX ROWID       SALES
       BITMAP CONVERSION TO ROWIDS
        BITMAP AND
         BITMAP MERGE
          BITMAP KEY ITERATION
           BUFFER SORT
            TABLE ACCESS FULL                 CUSTOMERS
           BITMAP INDEX RANGE SCAN            SALES_CUST_BIX
         BITMAP MERGE
          BITMAP KEY ITERATION
           BUFFER SORT
            TABLE ACCESS FULL                 CHANNELS
           BITMAP INDEX RANGE SCAN            SALES_CHANNEL_BIX
         BITMAP MERGE
          BITMAP KEY ITERATION
           BUFFER SORT
            TABLE ACCESS FULL                 TIMES
           BITMAP INDEX RANGE SCAN            SALES_TIME_BIX

Если у нас bitmap join индекс, то еще лучше, не будет операции выборки из таблицы:

           BUFFER SORT
            TABLE ACCESS FULL                 CUSTOMERS
           BITMAP INDEX RANGE SCAN            SALES_CUST_BIX

будет одно объединение индексов:

         BITMAP AND
         BITMAP INDEX SINGLE VALUE            SALES_C_STATE_BJIX
         BITMAP MERGE

Oracle: быстрая вставка данных в таблицу

Уменьшение времени пакетной (для olap/dwh) вставки данных:
Отличительная особенность olap: вставка одна, но очень большая.

1. Делаем таблицу не логируемой.
Что уменьшит затраты на вставку в redo log.

ALTER TABLE T NOLOGGING

* Может не сработать, если в базе включено FORCE_LOGGING = YES

2. Добавляем /*+ append */ в insert операцию
* Данные добавляются в конец таблицы, вместо попытки поиска пустых мест.
* Данные пишутся напрямую в data файлы, минуя буферный кэш.

Стоит заметить один нюанс при вставке с хинтом append из разных сессий в одну таблицу. Так делать нельзя, т.к. direct path вставка блокирует все остальные сессий к этой таблице: http://docs.oracle.com/cd/B19306_01/server.102/b14231/tables.htm#sthref2260 . Только одна сессия может одновременно осуществлять direct path вставку в одну таблицу. Т.к. чтобы обойти буферный кэш, сначала нужно скинуть все грязные данные из кэша на диск.

3. Отключаем constraint, trigger на таблице и явно вставляем значения в default колонки.
Замечу, что если надо ускорить вставку, то надо отключать FK на самой таблице, а если удаление, то FK на других таблицах, которые указывают на нашу.

4. Распараллеливаем запрос хинтом /*+ PARALLEL (8) */
Не забываем включать параллельность для DML, чтобы параллелился и insert, а не только select.

ALTER SESSION ENABLE PARALLEL DML;

5. Если распаралеллить вставку нельзя, к примеру из-за доступа по dblink.
Можно физически распаралелить вставку через несколько одновременных вставок кусками части данных из источника.
Сделать это можно через dbms_parallel.
Очень хорошо подходит для одновременного копирования нескольких таблиц или если таблица партиционирована.
При вставке в одну таблицу незабываем про ограничения хинта append из п.2

6. Удаляем index и foreign key с внешних таблиц.
Пришлось именно удалять, т.к.
* DISABLE можно делать только у функциональных индексов
* UNUSABLE можно сделать на всех индексах, но DML запросы все равно будут валиться на UNIQUE index
http://docs.oracle.com/cd/B13789_01/server.101/b10755/initparams197.htm
Ничего страшного в этом нет, восстановление индексов заняло 5 минут по 10 млн записей, что все равно лучше 4 часов вставки.
Удаляем все, включая Prmary Key. Но тут не забываем, что каскадно удалятся и все FK. Их надо будет потом восстановить, ну или PK придется пожертвовать и оставить.

ALTER TABLE T DROP CONSTRAINT PK CASCADE

7. Делаем кэшируемым Sequence.
Если в insert используется sequence, то делаем его кэшируемым.
С "CACHE 50000" мне удалось сократить время вставки 10 млн записей с 50 минут до 5. Это в 10 раз!
При кэширумом sequence последовательность заранее подготавливает числа и хранит в памяти, а это значит, что накладных расходов обмена становится меньше.

8. IOT таблица
Если на таблице один индекс, который покрывает большую часть столбцов, то ее можно конвертировать в IOT таблицу. Так мы уменьшаем число обслуживаемых объектов до 1. Что уменьшает число буферных чтений с 3 (2 чтения индекса + 1 чтения таблицы) при любых DML/select до 2 (2 чтения индекса).

Уменьшение времени распределенной/многопользовательской (oltp) вставки данных:
отличительной особенности вставок в oltp является то, что их очень много, каждая из них создает микроскопическую нагрузку, но все вместе могут создать большое кол-во событий ожиданий (busy wait). Рассмотрим отдельно как обойти эти ожидания:

1. увеличение числа списка свободных блоков (free_list при создании таблицы)
 + уменьшение конкуренции за поиск свободных блоков за счет распараллеливания вставки
 - раздувание таблицы, т.к. когда заканчивается free_list1, то он не будет использовать свободные блоки из free_list2, а выделит новые поверх HWM
 - увеличивает фактор кластеризации индексов, т.к. данные физически раскидываются по разным местам таблицы, а не идут последовательно

2. сделать индекс реверсивным, если нет возможности отключить при вставке
 + уменьшение конкуренции за вставку данных в индекс, т.к. последовательные реверсивные данные будут использовать разные блоки индекса
 - увеличение фактора кластеризации из-за разброса данных
 - нельзя будет использовать range scan (сканирование по диапазону) индекса, т.к. в индексе уже не сами данные, а их инвертированные значения
Стоит заметить о факторе класетризации: чаще всего в oltp системе он не очень важен, т.к. доступ к данным идет по конкретному значению к одному конкретному блоку. Т.е. здесь нет скачков по разным блокам, как при сканировании по диапазону.

3. использование хинта append_values
 + запись данных не будет использовать free_list, а будет просто писаться поверх HWM
 - разрастание таблицы

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

5. Выполнение вставки используя prepared statement
что позволит исключить парсинг SQL перед его выполнением.

6. Вставка строк блоками (executeBatch)
Что позволит снизить задержки на network lookup - время на установку соединения и передачу данных по сети.

7. 7п. из пакетной вставки - кэшируемый индекс

8. остальные способы из пакетной вставки, если они применимы в текущей ситуации


Если знаете еще способы ускорить insert - пишите в комментариях.

В продолжении: быстрая вставка данных в партиционированные таблицы http://blog.skahin.ru/2015/06/oracle.html

SQLite: две особенности этой базы

Хочу рассказать про 2 отличия SQLite от других БД, решение которых придется долго искать, если вы только начинаете работать с ней.

1. Приведение к верхнему регистру UPPER юникод строк UTF8.
Необходимость в этом у меня появилась при регистронезависимом поиске по подстроке LIKE и как оказалось поумолчанию эта функций в SQLite нет и предлагается самим ее реализовать.
В интернете множество вариантов решения через настройку SQLite и доустановку дополнительных пакетов. Но мне такой способ не подходил, т.к. на шаред хостинге это не сделать.

К счастью SQLite позволяет делать собственные пользовательские функции, чем мы и воспользуемся.
Далее код на php для создания собственной функции UPPER - UPPER_UTF8.

createFunction('UPPER_UTF8', 'upper_ru', 1);
//array('SQLITE_DB', 'upper_ru') - если используете в составе класса 'SQLITE_DB'

?>

После этих нехитрых манупуляций в составе SQLite появится новая функция UPPER_UTF8 и с помощью ее можно будет делать регистронезависимые запросы:

SELECT 
  t.* 
FROM
  table t
WHERE
  UPPER_UTF8(t.col) LIKE UPPER_UTF8('%кАкойТо Запрос%')

2. Правильное создание индексов для поиска по диапазону в БД SQLite.
Если вы хотите осуществить быстрый поиск по таблице, то во всех субд для этого необходимо создать индекс. Но в SQLite еще нужно соблюсти правильную последовательность.
Так если вы создаете индекс по нескольким полям, то столбец диапозона должен обязательно идти последним.

Далее 2 примера, сначала неправильный:

--таблица
CREATE TABLE "cashes" (
    "id" INTEGER PRIMARY KEY  NOT NULL,
    "date" DATE NOT NULL,
    "uid" INT(10) NOT NULL DEFAULT ('1'),
    "visible" TINYINT(4) NOT NULL DEFAULT ('1')
);

--индекс
CREATE INDEX "XIF_CASHES_DUV" on cashes (date DESC, uid ASC, visible ASC);

--вызов плана
EXPLAIN QUERY PLAN SELECT
      c.id, c.uid, c.date
     FROM cashes c
     WHERE
      c.date BETWEEN '2013-04-01' AND '2013-06-01'
      AND c.uid = 1 AND c.visible = 1
     ORDER BY
      c.date;

--план
SEARCH TABLE cashes AS c USING INDEX XIF_CASHES_USR (uid=?) (~2 rows)

А дальше, как нужно было правильно создавать индекс. Поле даты - поле диапозона, должно было идти последним:

--индекс
CREATE INDEX "XIF_CASHES_DUV" on cashes (uid ASC, visible ASC, date DESC);

--план запроса
SEARCH TABLE cashes AS c USING INDEX XIF_CASHES_DUV (uid=? AND visible=? AND date>? AND date<?) (~42 rows)

Причем если бы мы искали точное соответствие по дате, то сработали бы оба индекса, но при поиске по диапазону только последний.

Советы по оптимизации SQL запросов

Поделюсь опытом, который получил за несколько лет оптимизации sql запросов. Большая часть советов касается субд ORACLE.
Если кому статья покажется слишком очевидной, то считайте это заметкой чисто для себя, чтобы не забыть.

Другие статьи по оптимизации SQL

1. Ни каких подзапросов, только JOIN
Как я уже писал ранее, если выборка 1 к 1 или надо что-то просуммировать, то ни каких подзапросов, только join.
Стоит заметить, что в большинстве случаев оптимизатор сможет развернуть подзапрос в join, но это может случиться не всегда.

2. Выбор IN или EXISTS ?
На самом деле это сложный выбор и правильное решение можно получить только опытным путем.
Я дам только несколько советов:
* Если в основной выборке много строк, а в подзапросе мало, то ваш выбор IN. Т.к. в этом случае запрос в in выполнится один раз и сразу ограничит большую основную таблицу.
* Если в подзапросе сложный запрос, а в основной выборке относительно мало строк, то ваш выбор EXISTS. В этом случае сложный запрос выполнится не так часто.
* Если и там и там сложно, то это повод изменить логику на джойны.

3. Не забывайте про индексы
Совет для совсем новичков: вешайте индексы на столбцы по которым джойните таблицы.

4. По возможности не используйте OR.
Проведите тесты, возможно UNION выглядит не так элегантно, за то запрос может выполнится значительно быстрей. Причина в том, что в случае OR индексы почти не используются в join.

5. По возможности не используйте WITH в oracle.
Значительно облегчает жизнь, если запрос в with необходимо использовать несколько раз ( с хинтом materialize ) в основной выборке или если число строк в подзапросе не значительно.
Во всех других случаях необходимо использовать прямые подзапросы в from или взаранее подготовленную таблицу с нужными индексами и данными из WITH.
Причина плохой работы WITH в том, что при его джойне не используются ни какие индексы и если данных в нем много, то все встанет. Вторая причина в том, что оптимизатору сложно определить сколько данных нам вернет with и оптимизатор не может построить правильный план запроса.
В большинстве случаев WITH без +materialize все равно будет развернут в основной запрос.


6. Не делайте километровых запросов
Часто в web обратная проблема - это много мелких запросов в цикле и их советуют объединить в один большой. Но тут есть свои ограничения, если у вас запрос множество раз обернутый в from, то внутреннюю(ие) части надо вынести в отдельную выборку, заполнить временную таблицу, навесить индексы, а потом использовать ее в основной выборке. Скорость работы будет значительно выше (в первую очередь из-за сложности построения оптимального плана на большом числе сочетаний таблиц)

7. Используйте KEEP взамен корреляционных подзапросов.
В ORACLE есть очень полезные аналитические функции, которые упростят ваши запросы. Один из них - это KEEP.
KEEP позволит сделать вам сортировку или группировку основной выборки без дополнительно запроса.
Пример: отобрать контрагента для номенклатуры, который раньше остальных был к ней подвязан. У одной номенклатуры может быть несколько поставщиков.

SELECT n.ID, MIN(c.ID) KEEP (DENSE_RANK FIRST ORDER BY c.date ASC) as cnt_id
FROM nmcl n, cnt c
WHERE n.cnt_id = c.id
GROUP BY n.ID

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

8. Гуляние по выборке вверх-вниз
Менее популярная функция, но не менее полезная. Позволяет смещать текущую строку выборки на N элементов вверх или вниз. Бывает полезно, если необходимо сравнить показатели рядом стоящих строк.
Следующий пример отбирает продажи департаментов отсортированных по дате. К основной выборке добавляются столбцы со следующим и предыдущим значением выручки. Второй параметр - это на сколько строк сместиться, третьи - параметр по-умолчанию, если данные соседа не нашлись.

SELECT deptno, empno, sal,
LEAD(sal, 1, 0) OVER (PARTITION BY dept ORDER BY date) NEXT_LOWER_SAL,
LAG(sal, 1, 0) OVER (PARTITION BY dept ORDER BY date) PREV_HIGHER_SAL
FROM emp;
ORDER BY deptno, date DESC;

При обычном подходе бы пришлось это делать через логику приложения.

9. Direct Path Read
Установка этой настройки (настройкой или параллельным запросом) - чтение данных напрямую в PGA, минуя буферный кэш. Что укоряет последующие этапы запроса, т.к. не используется UNDO и защелки совместного доступа.

10. Direct IO
Использование прямой записи/чтения с диска без использования буфера файловой системы (файловая система конкретно для СУБД).
* В случае чтения преимущество в использовании буферного кэша БД, замен кэша ФС (кэш бд лучше заточен на работу с sql)
* В случае записи, прямая запись гарантирует, что данные не потеряются в буфере ФС в случае выключения электричества (для redolog всегда использует fsync, в не зависимости от типа ФС)

11. Оптимизация параллельных запросов
12. Оценка стоимости запроса и построение правильного плана
13. Оптимизация работы секционированных таблиц
14. Индексный поиск
15. Оптимизация запросов вставки
16. Ускорение pl/sql циклов
17. И другое...