Алгоритм внешней сортировки

Сортировка играет большую роль в выполнении запросов по двум причинам:

1 Многие запросы требуют упорядочения кортежей и такое требование поддерживается стандартом SQL.

2 Некоторые реляционные операции (объединение, например) выполняются более эффективно, если исходные отношения первоначально отсортированы.

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

Пусть М – число блоков, помещающихся в памяти. Сортировка смещением состоит из двух этапов.

1 Создание сортированных фрагментов.

i:=0;

repeat

Считать M блоков исходного отношения или остаток отношения, если он меньше М;

Отсортировать часть отношения, находящуюся в памяти;

Записать отсортированный фрагмент в файл Ri;

i:=i+1;

until обработано все отношение.

2 Смещение фрагментов. Пусть N – число файлов, полученных на первом этапе. Предположим, что N<M.

Считать первые блоки из всех файлов в память;

repeat

Расположить первые кортежи каждого блока в отсортированном порядке;

Записать отсортированные кортежи в выходной файл и удалить их из памяти.

If i – ый блок пуст and не конец файла Ri

Then считать следующий блок файла Ri в память;

until в памяти не осталось ни одного кортежа.

Обычно каждый кортеж не записывается на диск отдельно. Кортежи формируют блок в памяти, а затем этот блок записывается в файл. /*Поэтому N<M, а неN<=M */.

Реальные отношения могут иметь очень большие размеры, поэтому может сложиться ситуация, когда число файлов, получившихся на первом этапе, больше или равно числу доступных блоков памяти. В этом случае выполняют многошаговое смещение. На первом шаге обрабатывают фрагменты с первого по М-1. В результате этого получается первый фрагмент для второго шага смещения. Затем обрабатывают следующие М-1 файл, получая второй файл для второго шага смещения и так далее. Если файлов, полученных на первом шаге больше, чем М-1, то процесс продолжается, а если нет, то выполняется последнее смещение, результатом которого будет единственный файл.

Пример. Пусть в блок содержит одну запись, память может вмещать только три блока, то есть два обрабатываемых и один результирующий.

Рассмотрим эффективность внешней сортировки. На первом этапе все блоки отношения читаются и записываются на диск, то есть требуется 2br обращений к диску. После выполнения первого этапа получено br/M фрагментов. Количество фрагментов уменьшается по степени M-1. Таким образом, число смещений определяется как

logm-1(Br/M)

На каждом шаге смещения производится чтение и запись всех блоков, исключение составляет последнее смещение, так как блоки при этом только читаются, но не записываются на диск /*+1 в формуле */, Поэтому число обращений к диску на втором этапе сортировки будет

Br(2*logm-1*(Br/M)+1)