Перечисление соединений
Применяя стратегии доступа и соединений, описанные в предыдущем разделе, оптимизаторы DB2 рассматривают возможные последовательности соединений, производя поиск хорошего плана в одной и той же восходящей манере, но с использованием разных алгоритмов.
В DB2 для MVS для перечисления различных порядков соединения используется динамическое программирование. Базовые алгоритмы детально описаны в [SAC+79]. Как правило, две таблицы не будут соединяться, если для них отсутствует предикат соединения. Однако применяются специальные эвристики для попыток распознавания случаев, в которых может оказаться выгодным декартово произведение. Все таблицы, для которых гарантированно будет произведена одна строка по причине наличия полностью уточненного уникального индекса, фиксируются в начале порядка соединений. Эта ситуация без потерь, она полностью безопасна и сокращает время оптимизации. В DB2 для MVS также используется тот факт, что эти «однострочные» таблицы не влияют на упорядоченность результирующего набора.
По мере возрастания числа таблиц, участвующих в соединении, требования динамического программирования по времени и памяти могут стать чрезмерными на небольших PC с OS/2. В результате в DB2/* используется «жадный» алгоритм [Loh88a], который очень эффективен, поскольку никогда не меняет курс. Поскольку жадный алгоритм всегда занимается наиболее дешевыми соединениями, оптимизатор может кэшировать результат соединения во временной таблице и использовать ее как внутреннюю таблицу более позднего соединения. Тем самым, в DB2/* допускаются составные внутренние источники данных (планы «густых деревьев» (bushy tree)). Как и при использовании DB2 для MVS, на возможные соединения указывают предикаты соединения. Декартово произведение берется только при отсутствии предикатов соединения.
В DB2/* с использованием Starburst у пользователя будет иметься возможность расширения пространства поиска до размеров, превышающих те, которые допускаются в DB2 для MVS. Опции времени компиляции будут разрешать пользователю указывать на потребность использования алгоритма динамического программирования или жадной эвристики для оптимизации каждого запроса, возможность использования составных внутренних источников и на то, следует ли откладывать получение декартовых произведений до предела или допустить такую возможность где-либо в последовательности плана.
Перебор большего числа комбинаций соединений может позволить оптимизатору найти более эффективный план, но может привести к повышению стоимости выполнения самого процесса оптимизации [OL90]. Чтобы избегать потенциальных декартовых произведений, в DB2/* с использованием Starburst любой предикат, ссылающийся на более чем одну таблицу, будет считаться действующим, как предикат соединения. Например, предикат вида X.1 + Y.2 > Z.4 может использоваться для соединения таблиц X, Y и Z. Кроме того, будут ликвидированы зависящие от реализации ограничения на число таблиц, ссылки на которые содержатся в запросе; единственным ограничением будет объем памяти, доступной для хранения фрагментов плана в течение оптимизации.
