Стратегии выполнения NAAJ
В соответствии с семантикой NAAJ строка левой части может соединяться с несколькими строками правой части (соответствовать нескольким строкам). Например, строка левой части, которая содержит неопределенное значение в одном из соединяемых столбцов, будет соответствовать строкам правой части, которые содержат любое значение в соответствующем столбце. В этом случае условие NAAJ вычисляется в UNKNOWN, и, следовательно, строка не возвращается. Пусть, например, левая таблица L из запроса Q25 содержит строку (null, 3, null). Предположим, что правая таблица R содержит две строки: R = {(1, 3, 1), (2, 3, 2)}. Хотя в R отсутствует строка (null, 3, null), нашей строке из L соответствуют обе строки R, поскольку столбец c2 в обеих строках содержит значение 3. Поэтому строка (null, 3, null) не возвращается.
Методы выполнения обычного антисоединения посредством сортировки со слиянием или хеширования расширяются: по мере построения требуемой структуры данных теперь они собирают информацию о том, какие столбцы соединения содержат неопределенные значения.
После этого выполняются шаги 1 и 2, описанные в подразделе 6.1, для раннего завершения выполнения соединения, возвращающего все строки или не возвращающего ни одной строки. В случае, когда эти шаги не срабатывают, для каждой строки левой части мы ищем соответствующую строку в правой части (если на шаге 3 алгоритма, приведенного в подразделе 6.1, эта строка не исключается). Если на любом из следующих трех шагов, описываемых ниже, соответствие обнаруживается, то строка левой части отбрасывается, как и в обычном антисоединении.
-
Поиск в отсортированной структуре данных или хеш-таблице для правой части на предмет наличия точного соответствия.
-
Поиск других возможных соответствий с использованием собранной информации о неопределенных значениях. Например, предположим, что имеются три столбца соединения c1, c2 и с3, но в правой части неопределенные значения имеются только в столбцах c1 и c2. Если поступающая на обработку строка левой части содержит значения (1,2,3), то в структуре доступа к правой части ищутся строки (1,null,3), (null, 2, 3) и (null, null, 3).
-
Если в одном или нескольких столбцах соединения строки левой части содержится неопределенное значение, то создается дополнительная структура доступа для столбцов, не содержащих неопределенные значения (если она еще не строилась). Например, предположим, что строка левой части содержит значения (null, 2, 3). Для правой части создается дополнительная отсортированная структура данных или хеш-таблица с использованием столбцов c2 и с3, и далее в новой структуре данных ищутся строки (x, 2, 3), (x, 2, null), (x, null, 3) и (x, null,null).
Если вести учет всех возможных схем расположения неопределенных значений в правой части, становится возможна дальнейшая оптимизация. Используя пример, приведенный выше при описании шага 3, предположим, что нам известен факт наличия в правой части строки, содержащой неопределенное значение null в столбцах c2 и с3. Эта строка будет соответствовать любой строке левой части, у которой c1 содержит неопределенное значение. В этом случае строка левой части (null, 2, 3) может быть немедленно исключена, и не требуется построение дополнительной структуры доступа. Эта информация также может быть использована для исключения некоторых поисковых действий, выполняемых на шаге 2.
Оптимизация ключа из одного столбца: Если в условии NAAJ участвует только один столбец (как, например, в запросе Q24), то стратегия выполнения существенно упрощается. Строки левой части, содержащие неопределенное значение в столбце соединения, могут быть пропущены или включены в результат без реального поиска соответствий в зависимости от того, имеются или не имеются в правой части какие-либо строки.
