Классика баз данных - статьи
Как пример улучшения алгоритмов здесь
Как пример улучшения алгоритмов здесь кратко описывается эволюция алгоритма операции соединения.
Напомним, что операция соединения комбинирует два отношения A и B таким образом, что в результате получается отношение C, содержащее все пары кортежей из A и B с совпадающими значениями заданных атрибутов. Обычный способ вычисления соединения состоит в сортировке обоих отношений A и B с получением двух новых отношений, упорядоченных по значениям атрибута соединения. Эти два новых отношения затем сравниваются в отсортированном порядке, и соответствующие кортежи вставляются в поток вывода. Такой алгоритм называется сортировкой-слиянием (sort-merge).
Возможны различные оптимизации соединения сортировкой-слиянием, но поскольку стоимость сортировки равна nlog(n), то и стоимость выполнения соединения сортировкой-слиянием равняется nlog(n). Алгоритм сортировки-слияния хорошо работает в среде параллельных потоках данных, если нет перекоса данных. Если имеется перекос данных, то некоторые разделы сортировки могут оказаться гораздо больше других. Это в свою очередь приводит к перекосам в выполнении и ограничивает ускорение и масштабируемость. При централизованном выполнении соединений сортировкой-слиянием проблемы с перекосом не возникают.
Соединение с хэшированием (hash-join) является альтернативой соединению методом сортировки-слияния. Стоимость выполнения соединения этим методом возрастает линейно, а не как nlog(n), и метод более устойчив к перекосам данных. Соединение с хэшированием предпочтительнее, чем сортировка-слияние, если только входные потоки уже не отсортированы. Соединение с хэшированием работает следующим образом. Каждое из отношений A и B сначала разделяется на основе хэширования по атрибуту соединения. Хэш-раздел отношения A размещается в памяти. Просматривается соответствующий раздел отношения B, и каждый кортеж сравнивается со всеми кортежами хэш-раздела отношения A. Если установлено соответствие, то пара кортежей посылается в выходной поток. Таким образом обрабатывается каждая пара хэш-разделов.
