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

Хотел бы начать цикл статей о внутреннем устройстве Oracle. Какие алгоритмы скрываются за казалось бы простыми операциями запросов.

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

Начну с операции order by.

При выполнении сортировки, данные сначала помечаются в приватную область памяти pga, называемую "sorting work area". Если данные не помещаются целиком, то массив разбивается на части и сохраняются на диск в TEMP пространство процесса, после чего части сортируются по отдельности в памяти, а потом сливаются в один отсортированный набор (внешняя сортировка слиянием).

До 10 версии Oracle "sort area size" была жестко фиксирована из-за этого нельзя было применять сортировки расходующие дополнительную память. Скорей всего это была сортировка вставками, имеющая стоимость O(N*N) (http://www.hellodba.com/reader.php?ID=185&lang=EN). Алгоритм сортировки вставками на java можно посмотреть здесь: https://github.com/pihel/java/blob/master/oracle_sort/OracleSort.java#L238 .

Одним из основных нововведений Oracle 10gR2 - гибкий размер pga и увеличение области сортировки (pga target), что позволило применять сортировки с дополнительным потреблением памяти.
Переключение новая/старая сортировка осуществляется скрытым параметром "_new_sort" - по умолчанию = true

Новая реализация order включает в себя смесь 3 сортировок: быстрая сортировка (qsort) + поразрядная сортировка (radix sort) + сортировка слиянием (merge sort). Что дает сложность от N*K до N*Log2(N), где K - размер ключа, а N - размер массива.

Общий алгоритм представляет из себя:

1. Используя алгоритм из сортировки слиянием разбиваем входящий массив (MergeSort.sort) на части с размером меньше "sort area size" ( OracleSort.isSortArr )

package oracle_sort;

import java.util.*;
import org.junit.runner.JUnitCore;
import org.junit.runner.Result;

/*
Сортировка слиянием: 
 * Сложность: N*Log2(N)
 * Доп. память: O(N)
 * Общий смысл:
  ** рекурсивно разбиваем массив на 2 части, пока размер элемента не дойдет до N (тут =1 )
  ** сливаем массивы в один последовательным проходом (в худшем случае N+M), сравнивая элементы
*/
class MergeSort {
 
 //проверка достаточности разбиения
 @SuppressWarnings("rawtypes") 
 protected boolean isSortArr(Comparable[] arr) {
  if(arr.length <= 1) return true;
  return false;
 }
 
 //разбитие массива на 2 равные части
 @SuppressWarnings("rawtypes") 
 public void sort(Comparable[] arr) {
  
     //если массив достаточно разбит, то прерываем рекурсию
     if(isSortArr(arr)) return;
  
     //левая половина
     Comparable[] left = new Comparable[arr.length / 2];  
     System.arraycopy(arr, 0, left, 0, left.length);
     sort(left);
     //swop to disk
     
     //правая половина
     Comparable[] right = new Comparable[arr.length - left.length];
     System.arraycopy(arr, left.length, right, 0, right.length);
     sort(right);
      
     //слияние
     merge(left, right, arr);
 } //sort
} //MergeSort


/*
 * Комбинированная сортировка: слиянием + быстрая + поразрядная
 * 
 * */
public class OracleSort extends MergeSort {
 //размер памяти под сортировку
 int sort_area_size = 1;
 //размер ключа
 int avg_key_size = 0;
 
 
 final double log10_2 = Math.log(2);
 
 OracleSort(int _sort_area_size, int _avg_key_size) {
  sort_area_size = _sort_area_size;
  avg_key_size = _avg_key_size;
 } //OracleSort
 
 protected boolean isSortArr(Comparable[] arr) {
  
  if(arr.length < 2) return true;
  
  //если после разбиения массива размер меньше размера под сортировку
  if(arr.length <= sort_area_size) {  
   
   //если Integer и размер ключа меньше log2(Т), то делаем поразрядную сортировку
   if( arr[0].getClass() == Integer.class && avg_key_size > 0 && avg_key_size < ( Math.log(arr.length) / log10_2 ) ) {
    
    Integer[] _arr = new Integer[arr.length]; //как привести Comparable к Integer?
    
    System.arraycopy(arr, 0, _arr, 0, arr.length);
    Sorts.radixSortUInt(_arr);
    System.arraycopy(_arr, 0, arr, 0, arr.length);
    _arr = null;
   } else {
    //иначе быструю сортировку
    Sorts.QSort(arr, 0, arr.length-1);
   }
   return true;
  }
  return false;
 } //isSortArr

}

2. Подмассивы размером меньше "sort area size" сортируются одним из алгоритмов внутри памяти.
В зависимости от размера ключа сортировки (avg_key_size) выбирается или поразрядная сортировка (radix sort) или быстрая (qsort): OracleSort.isSortArr

2.1. Быстрая сортировка имеет среднюю сложность O (N * Log2(N)) и хорошо использует процессорный кэш, но сильно зависит выбора среднего элемента. Для этого используется статистика на столбце таблицы: максимальное и минимальное значение в нем.

/*
  Быстрая сортировка: 
   * Сложность: N*Log2(N)
   * Доп. память: нет
   * Минусы:
   * - Сильно зависит от выбора средней точки, при неправильно выборе (крайний элемент) сложность = N*N
   * - На большом наборе данных из-за рекурсии может вызвать переполнение стека
   * Общий смысл:
    ** находим элемент в центре массива со средним значением
    ** движемся с краев к центру, меняя значения местами, если влевой части значение больше середины или вправой больше
    ** при доходе до середины, запускам рекурсивно для левой и правой части
  */
 public static <T extends Comparable<T>> void QSort(T[] arr, int l, int r) {
  int i = l;
  int j = r;
  //средний элемент = левая граница + (правая граница - левая граница) / 2
  T c = arr[l + ( r - l ) / 2];
  
  // идем к центу, пока края не встретятся
  while(i < j) {
   //идем с левого края к центру, пока середина больше текущего значения (ищем элемент больше середины)
   while(arr[i].compareTo(c) < 0) {
    i++;
   }
   //с правого края к центру, пока середина меньше текущего значения (ищем элемент меньше середины)
   while(arr[j].compareTo(c) > 0) {
    j--;
   }
   //если левый индекс меньше правого индекса, то меняем местами и смещаемся
   if(i <= j) {
    T t = arr[j];
    arr[j] = arr[i];
    arr[i] = t;
    i++;
    j--;
   }
  }
  //рекурсивно запускаемся для левой и правой части
  if(l < j) {
   QSort(arr, l, j);
  }
  if(r > i) {
   QSort(arr, i, r);
  }
 } //QSort

2.2. Если размер ключа сортировки на основе статистики "avg_key_size" (K) меньше Log2 от размера массива N, то поразрядная сортировка более эффективна, т.к. имеет сложность = O (K*N)

Ниже пример реализации для массива Integer:

/*
  Поразрядная сортировка: 
   * Сложность: N*K
    ** где K число разрядов в сортиуемом элементе
   * Доп. память: O(N)
   * Минусы/Плюсы:
    * -/+ быстрей, если k < log2(n) и дольше в других случаях
    * - разный размер хэш массива для разных типов данных
   * Особенность:
    * Порядок сортировки зависит от направления: для цифр нужно справа-навлево, для строк: слева-направо
   * Общий смысл:
    * Идем по рязрядам числа справа-налево и помещаем элементы в массив по значению текущего разряда
     ** т.е. элементы сначала упорядычиваются по последнему элементу
     ** потом переупорядычиваваются по второму и т.д. пока полностью не упорядочим массив
  */
 public static <T extends Integer> void radixSortUInt(T[] arr) {
  
  //хэш массив из 10 элементов для 10-ричного числа
  final int RADIX = 10;
  List<T>[] bucket = new ArrayList[RADIX];
  for (int i = 0; i < bucket.length; i++) {
   //список чисел, содержащих нужно число в разряде
   bucket[i] = new ArrayList<T>();
  }
  
  //признак, что все разряды перебраны
  boolean maxLength = false;
  //значение в разряде
  int rank_val = -1;
  //номер разряда
  int placement = 1;
  
  //пока не перебраны все разряды
  while (!maxLength) {
      maxLength = true;
      
      //для каждого элемента массива
      for (int i = 0; i < arr.length; i++) {
       //добавляем элемент в массив по значению в разряде
       rank_val = arr[i] / placement;
       bucket[rank_val % RADIX].add(arr[i]);
       
       //если в разряде не пусто, то ставим флаг повторения цикла
       if (maxLength && rank_val > 0) {
        maxLength = false;
       }
      }
      
      //разворачиваем двухуровневый массив обратно в последовательный
      int a = 0;
      for (int b = 0; b < RADIX; b++) {
       for (int i = 0; i < bucket[b].size(); i++) {
        arr[a++] = bucket[b].get(i);
       }
       bucket[b].clear();
      }
      //переходим к следующему разряду
      placement *= RADIX;
  }
    
 } //radixSortUInt

3. Отсортированные части объединяются за один проход в отсортированный массив используя алгоритм слияния:

 //слияние 2 упорядоченных массивов в один
 @SuppressWarnings({ "rawtypes", "unchecked" }) 
 private void merge(Comparable[] left, Comparable[] right, Comparable[] arr) {
  int iFirst = 0;        
     int iSecond = 0;         
     int iMerged = 0;
      
     //бежим, пока не дойдем до конца одного из массивов
     while (iFirst < left.length && iSecond < right.length) {
      //если элемент в левом массиве больше, чем в правом
         if (left[iFirst].compareTo(right[iSecond]) < 0) {
             //то добавляем элемент из левого
             arr[iMerged] = left[iFirst];
             //и двигаемся в левом на 1
             iFirst++;
         } else {
             //иначе добавляем элемент из правого
             arr[iMerged] = right[iSecond];
             //двигаемся в правом на 1
             iSecond++;
         }
         //в любом случае увеличиваем результирующий массив
         iMerged++;
     }
     
     //оставшиеся элементы - больше последнего (максимального) элемента одного из массивов. Докопируем оставшиеся элементы.
     System.arraycopy(left, iFirst, arr, iMerged, left.length - iFirst);
     System.arraycopy(right, iSecond, arr, iMerged, right.length - iSecond);
 } //merge

Полную версию oracle order by можно посмотреть здесь: https://github.com/pihel/java/blob/master/oracle_sort/OracleSort.java#L463 , включая юнит тесты: https://github.com/pihel/java/blob/master/oracle_sort/OracleSortTest.java#L65

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

Страницы

четверг, 21 марта 2024 г.

Популярные группы leetcode задач

понедельник, 24 октября 2016 г.

Oracle: реализация order by сортировки

Разделы

Реклама

Архив блога

В сети