- 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/
