InterBase: тормозология и глюконавтика
Страница 9. Как делаются соединения таблиц

Как делаются соединения таблиц

Кстати, основание логарифма зависит от размера оперативной памяти (кэша то есть) и быстродействия процессора и на современных (даже персональных) машинах очень велико - сотни и тысячи. Так что про логарифм обычно можно забыть и считать log(n) ~ const.

В то же время, тупое соединение полным перебором всех комбинаций делается за n*m обращений к данным, где в одной таблице n записей, а в другой - m. С учётом того, что записи обычно физически разбросаны по базе, мы имеем квадратичную зависимость обращений к диску от размера данных. А если соединяются три таблицы - то кубическую. И чем дальше, тем хуже. На фоне этого сортировка миллионов записей превращается в мелочь.

Тем не менее, всякая уважающая себя СУБД решает эти вопросы принципиально более быстро. Далее будем рассматривать соединение двух таблиц, так как три и более таблицы можно соединять попарно. И будем считать, что соединение делается по условию равенства полей этих двух таблиц. Представим себе, что обе соединяемые таблицы физически отсортированы. И мы можем читать из них записи подряд без существенных физических затрат.

И так, читаем первые записи из обеих таблиц и сравниваем их. Если поля для сравнения совпадают, выдаём комбинацию записей, как результат соединения, и читаем следующую запись одной из таблиц (не важно какой). Если совпадения нет, то читаем очередную запись из той таблицы, где сравниваемое поле меньше. Снова сравниваем, и т. д.

Поскольку записи упорядочены, то каждое чтение приводит к выдаче записи, сравниваемое поле которой не меньше, чем у предыдущей. Значит, чтение приводит к возрастанию (в читаемой таблице) и рано или поздно текущая запись станет либо равной текущей в другой таблице (ура, нашли совпадение!), либо больше. В последнем случае принимаемся аналогичным образом вычитывать другую.

Можно показать, что при таком алгоритме будут учтены все комбинации записей с равными полями. И сделано это будет за один проход. То есть за n+m операций! Очевидно, что это лучше, чем n*m. А на четырёх таблицах n+m+p+q уж совсем лучше, чем n*m*p*q.

Однако в начале рассуждений было сделано предположение о физической отсортированности таблиц. На практике это редко бывает справедливо. Хотя лучшие СУБД предоставляют возможность создания так называемых кластерных индексов. Фактически это не индекс, а способ хранения самих записей в упорядоченном виде. Сортировать всю таблицу полностью было бы накладно, однако можно разрезать её на группы записей с близкими значениями и отсортировать эти группы внутри. Таким образом, "чтение в заданном порядке" будет происходить почти непрерывно, лишь с редкими перескоками от одной группы к другой. Вот только есть огорчающее обстоятельство: в нынешних версиях InterBase ничего подобного вообще нет.

Тем не менее, как было замечено выше, задачу перебора записей в заданном порядке можно решить с помощью индекса. Это решение не совсем такое быстрое, как кластеризация, кроме того случая, когда прямо в индексе содержатся все необходимые поля (последним фактом interbase не воспользуется). Но всё же это быстрее, чем перекапывать все данные. В том числе и по этой причине во многих СУБД, включая InterBase, существует жёсткое правило: все ключи, участвующие в ссылочных (и ключевых тоже) ограничениях должны в обязательном порядке индексироваться. InterBase вообще делает это автоматически, порождая под ключи индексы с именами RDB$PRIMARYnnn, RDB$UNIQUEnnn, а под внешние ключи (ссылки) - RDB$FOREIGNnnn. Здесь везде nnn - номер индекса в базе.

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

Ещё дополнительное замечание: оба используемых индекса должны давать в своих таблицах одинаковый порядок для сравниваемых значений. То есть индексы должны быть по соответствующим полям и если полей несколько, то они должны быть перечислены в одинаковом порядке. Например, если соединяются таблицы T1 и T2 по условию T1.x1=T2.y1 and T1.x2=T2.y2, то для быстрого соединения подойдут пары индексов T1(x1, x2), T2(y1, y2) или T1(x2, x1), T2(y2, y1), но не подойдёт T1(x2, x1), T2(y1, y2).

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

Ну а теперь представим, что индексов нет, а соединять надо. Полный перебор - плохо, это очевидно. В этом случае хороший результат может дать предварительное создание в базе отсортированных (точнее - кластеризованных) копий таблиц с последующим их слиянием. На первый взгляд решение парадоксальное, и даже страшное. Копировать и сортировать только ради одного запроса? Но если вдуматься - сортировка требует n*log(n) операций. Слияние же займет m+n. Порядок суммы этих величин не намного больше, чем m+n. Хотя постоянный коэффициент по сравнению с классическим слиянием будет вдвое-втрое выше. В InterBase это называется словами SORT MERGE.

Наконец, в InterBase есть и третий способ реализации соединения - JOIN. Только не путайте его со словом join, которое пишется в части from оператора select. Это немного другая тема. В данном случае имеется в виду слово join из части plan. Это и есть простой индексный перебор. То есть берутся записи первой таблицы "как есть" (может быть, отфильтрованные с учётом других условий запроса) и для каждой записи ищется пара из второй таблицы по индексу.

На самом деле то, что изложено, это далеко не всё. Есть способы соединения, включающие вместо сортировки предварительный проход по индексу с построением временной физически отсортированной версии (тоже иногда оправданная операция), есть построение сильно упакованных хешей прямо в памяти, и много других наворотов. Но не в InterBase.