Обобщение последовательности соединений
Во многих системах последовательность операций соединения синтаксически ограничивается для ограничения размеров пространства поиска. Например, в проекте System R рассматриваются только линейные последовательности операций соединения, и декартово произведение отношений вычисляется только после всех соединений.
Поскольку операции соединения коммутативны, последовательность соединений в дереве операций не обязательно должна быть линейной. В частности, запрос, состоящий в соединении отношений R1, R2, R3, R4, может быть алгебраически представлен и вычислен как Join ( Join (A,B), Join (C,D) ). Соответствующие деревья операций (и запросов) называются кустовыми, пример такого дерева приведен на рис. 2(b). Кустовые последовательности соединений требуют материализации промежуточных отношений. Хотя кустовые деревья могут привести к более дешевому плану выполнения запроса, они значительно увеличивают расходы на перебор пространства поиска. При наличии некоторых исследований достоинств использования кустовых последовательностей соединений, до сих пор в большинстве систем используются линейные последовательности соединений и только ограниченные подмножества кустовых деревьев соединения.
Откладывание вычисления декартова произведения тоже может привести к плохой эффективности. Для многих запросов категории поддержки принятия решений, у которых граф запроса образует звезду, было замечено, что вычисление декартова произведения соответствующих узлов (таблиц "измерений" в терминологии OLAP [7]) приводит к значительному снижению стоимости.
В расширяемых системах поведение компонента перебора соединений может адаптироваться к конкретному запросу, ограничивая "кустистость" деревьев соединений или разрешая или запрещая вычисление декартовых произведений [46]. Однако нетривиально заранее определить воздействие такой настройки на качество и стоимость поиска.
