Список статей о внутреннем устройстве Oracle:
- Oracle: реализация order by сортировки
- Oracle: реализация btree индекса
- Hash Join
- Bloom filter
- Lru cache
- Hash агрегация и приблизительный DISTINCT
Начну с операции order by.
При выполнении сортировки, данные сначала помечаются в приватную область памяти pga, называемую "sorting work area". Если данные не помещаются целиком, то массив разбивается на части и сохраняются на диск в TEMP пространство процесса, после чего части сортируются по отдельности в памяти, а потом сливаются в один отсортированный набор (внешняя сортировка слиянием).
До 10 версии Oracle "sort area size" была жестко фиксирована из-за этого нельзя было применять сортировки расходующие дополнительную память. Скорей всего это была сортировка вставками, имеющая стоимость O(N*N) (http://www.hellodba.com/reader.php?ID=185&lang=EN). Алгоритм сортировки вставками на java можно посмотреть здесь: https://github.com/pihel/java/blob/master/oracle_sort/OracleSort.java#L238 .
Одним из основных нововведений Oracle 10gR2 - гибкий размер pga и увеличение области сортировки (pga target), что позволило применять сортировки с дополнительным потреблением памяти.
Переключение новая/старая сортировка осуществляется скрытым параметром "_new_sort" - по умолчанию = true
Новая реализация order включает в себя смесь 3 сортировок: быстрая сортировка (qsort) + поразрядная сортировка (radix sort) + сортировка слиянием (merge sort). Что дает сложность от N*K до N*Log2(N), где K - размер ключа, а N - размер массива.
Общий алгоритм представляет из себя:
1. Используя алгоритм из сортировки слиянием разбиваем входящий массив (MergeSort.sort) на части с размером меньше "sort area size" ( OracleSort.isSortArr )
package oracle_sort;
import java.util.*;
import org.junit.runner.JUnitCore;
import org.junit.runner.Result;
/*
Сортировка слиянием:
* Сложность: N*Log2(N)
* Доп. память: O(N)
* Общий смысл:
** рекурсивно разбиваем массив на 2 части, пока размер элемента не дойдет до N (тут =1 )
** сливаем массивы в один последовательным проходом (в худшем случае N+M), сравнивая элементы
*/
class MergeSort {
//проверка достаточности разбиения
@SuppressWarnings("rawtypes")
protected boolean isSortArr(Comparable[] arr) {
if(arr.length <= 1) return true;
return false;
}
//разбитие массива на 2 равные части
@SuppressWarnings("rawtypes")
public void sort(Comparable[] arr) {
//если массив достаточно разбит, то прерываем рекурсию
if(isSortArr(arr)) return;
//левая половина
Comparable[] left = new Comparable[arr.length / 2];
System.arraycopy(arr, 0, left, 0, left.length);
sort(left);
//swop to disk
//правая половина
Comparable[] right = new Comparable[arr.length - left.length];
System.arraycopy(arr, left.length, right, 0, right.length);
sort(right);
//слияние
merge(left, right, arr);
} //sort
} //MergeSort
/*
* Комбинированная сортировка: слиянием + быстрая + поразрядная
*
* */
public class OracleSort extends MergeSort {
//размер памяти под сортировку
int sort_area_size = 1;
//размер ключа
int avg_key_size = 0;
final double log10_2 = Math.log(2);
OracleSort(int _sort_area_size, int _avg_key_size) {
sort_area_size = _sort_area_size;
avg_key_size = _avg_key_size;
} //OracleSort
protected boolean isSortArr(Comparable[] arr) {
if(arr.length < 2) return true;
//если после разбиения массива размер меньше размера под сортировку
if(arr.length <= sort_area_size) {
//если Integer и размер ключа меньше log2(Т), то делаем поразрядную сортировку
if( arr[0].getClass() == Integer.class && avg_key_size > 0 && avg_key_size < ( Math.log(arr.length) / log10_2 ) ) {
Integer[] _arr = new Integer[arr.length]; //как привести Comparable к Integer?
System.arraycopy(arr, 0, _arr, 0, arr.length);
Sorts.radixSortUInt(_arr);
System.arraycopy(_arr, 0, arr, 0, arr.length);
_arr = null;
} else {
//иначе быструю сортировку
Sorts.QSort(arr, 0, arr.length-1);
}
return true;
}
return false;
} //isSortArr
}
2. Подмассивы размером меньше "sort area size" сортируются одним из алгоритмов внутри памяти.
В зависимости от размера ключа сортировки (avg_key_size) выбирается или поразрядная сортировка (radix sort) или быстрая (qsort): OracleSort.isSortArr
2.1. Быстрая сортировка имеет среднюю сложность O (N * Log2(N)) и хорошо использует процессорный кэш, но сильно зависит выбора среднего элемента. Для этого используется статистика на столбце таблицы: максимальное и минимальное значение в нем.
/*
Быстрая сортировка:
* Сложность: N*Log2(N)
* Доп. память: нет
* Минусы:
* - Сильно зависит от выбора средней точки, при неправильно выборе (крайний элемент) сложность = N*N
* - На большом наборе данных из-за рекурсии может вызвать переполнение стека
* Общий смысл:
** находим элемент в центре массива со средним значением
** движемся с краев к центру, меняя значения местами, если влевой части значение больше середины или вправой больше
** при доходе до середины, запускам рекурсивно для левой и правой части
*/
public static <T extends Comparable<T>> void QSort(T[] arr, int l, int r) {
int i = l;
int j = r;
//средний элемент = левая граница + (правая граница - левая граница) / 2
T c = arr[l + ( r - l ) / 2];
// идем к центу, пока края не встретятся
while(i < j) {
//идем с левого края к центру, пока середина больше текущего значения (ищем элемент больше середины)
while(arr[i].compareTo(c) < 0) {
i++;
}
//с правого края к центру, пока середина меньше текущего значения (ищем элемент меньше середины)
while(arr[j].compareTo(c) > 0) {
j--;
}
//если левый индекс меньше правого индекса, то меняем местами и смещаемся
if(i <= j) {
T t = arr[j];
arr[j] = arr[i];
arr[i] = t;
i++;
j--;
}
}
//рекурсивно запускаемся для левой и правой части
if(l < j) {
QSort(arr, l, j);
}
if(r > i) {
QSort(arr, i, r);
}
} //QSort
2.2. Если размер ключа сортировки на основе статистики "avg_key_size" (K) меньше Log2 от размера массива N, то поразрядная сортировка более эффективна, т.к. имеет сложность = O (K*N)
Ниже пример реализации для массива Integer:
/*
Поразрядная сортировка:
* Сложность: N*K
** где K число разрядов в сортиуемом элементе
* Доп. память: O(N)
* Минусы/Плюсы:
* -/+ быстрей, если k < log2(n) и дольше в других случаях
* - разный размер хэш массива для разных типов данных
* Особенность:
* Порядок сортировки зависит от направления: для цифр нужно справа-навлево, для строк: слева-направо
* Общий смысл:
* Идем по рязрядам числа справа-налево и помещаем элементы в массив по значению текущего разряда
** т.е. элементы сначала упорядычиваются по последнему элементу
** потом переупорядычиваваются по второму и т.д. пока полностью не упорядочим массив
*/
public static <T extends Integer> void radixSortUInt(T[] arr) {
//хэш массив из 10 элементов для 10-ричного числа
final int RADIX = 10;
List<T>[] bucket = new ArrayList[RADIX];
for (int i = 0; i < bucket.length; i++) {
//список чисел, содержащих нужно число в разряде
bucket[i] = new ArrayList<T>();
}
//признак, что все разряды перебраны
boolean maxLength = false;
//значение в разряде
int rank_val = -1;
//номер разряда
int placement = 1;
//пока не перебраны все разряды
while (!maxLength) {
maxLength = true;
//для каждого элемента массива
for (int i = 0; i < arr.length; i++) {
//добавляем элемент в массив по значению в разряде
rank_val = arr[i] / placement;
bucket[rank_val % RADIX].add(arr[i]);
//если в разряде не пусто, то ставим флаг повторения цикла
if (maxLength && rank_val > 0) {
maxLength = false;
}
}
//разворачиваем двухуровневый массив обратно в последовательный
int a = 0;
for (int b = 0; b < RADIX; b++) {
for (int i = 0; i < bucket[b].size(); i++) {
arr[a++] = bucket[b].get(i);
}
bucket[b].clear();
}
//переходим к следующему разряду
placement *= RADIX;
}
} //radixSortUInt
3. Отсортированные части объединяются за один проход в отсортированный массив используя алгоритм слияния:
//слияние 2 упорядоченных массивов в один
@SuppressWarnings({ "rawtypes", "unchecked" })
private void merge(Comparable[] left, Comparable[] right, Comparable[] arr) {
int iFirst = 0;
int iSecond = 0;
int iMerged = 0;
//бежим, пока не дойдем до конца одного из массивов
while (iFirst < left.length && iSecond < right.length) {
//если элемент в левом массиве больше, чем в правом
if (left[iFirst].compareTo(right[iSecond]) < 0) {
//то добавляем элемент из левого
arr[iMerged] = left[iFirst];
//и двигаемся в левом на 1
iFirst++;
} else {
//иначе добавляем элемент из правого
arr[iMerged] = right[iSecond];
//двигаемся в правом на 1
iSecond++;
}
//в любом случае увеличиваем результирующий массив
iMerged++;
}
//оставшиеся элементы - больше последнего (максимального) элемента одного из массивов. Докопируем оставшиеся элементы.
System.arraycopy(left, iFirst, arr, iMerged, left.length - iFirst);
System.arraycopy(right, iSecond, arr, iMerged, right.length - iSecond);
} //merge
Полную версию oracle order by можно посмотреть здесь: https://github.com/pihel/java/blob/master/oracle_sort/OracleSort.java#L463 , включая юнит тесты: https://github.com/pihel/java/blob/master/oracle_sort/OracleSortTest.java#L65
