Антисоединение с учетом наличия неопределенных значений
В этом разделе обсуждается вариант антисоединения, появившийся в 11g и называемый антисоединением с учетом наличия неопределенных значений (null-aware antijoin, NAAJ). В большинстве приложений достаточно часто используются подзапросы с <> ALL (т.е. NOT IN), так как разработчики приложений находят синтаксис подзапросов с <> ALL более интуитивно-понятным, чем синтаксис примерно эквивалентных конструкций с NOT EXISTS. Вложенность подзапросов с NOT EXISTS устраняется c использованием антисоединения. Семантика антисоединения прямо противоположна семантике внутреннего соединения, поскольку строка из левой таблицы становится кандидатом в результат только в том случае, когда она не соединяется ни с одной из строк правой таблицы. Мы называем эту операцию обычным антисоединением. Как правило, в коммерческих СУБД обычное антисоединение может использоваться для устранения вложенности подзапросов с <> ALL только в случаях, когда все столбцы в квантифицированном сравнении гарантированно не содержат неопределенных значений. Имеется другая стратегия, описанная в [9], в которой для учета возможности появления неопределенных значений используются дубликат таблицы и дополнительное антисоединение.
В SQL операция <> ALL может трактоваться как конъюнкция неравенств. Аналогично можно трактовать операции < ALL, <= ALL, > ALL и >= ALL. В стандарте SQL поддерживается троичная логика и, следовательно, любое реляционное сравнение с неопределенными значениями всегда вычисляется в UNKNOWN. Например, предикаты 7 = NULL, 7 <> NULL, NULL = NULL, NULL <> NULL вычисляются в UNKNOWN, и это логическое значение отличается от FALSE тем, что его отрицание тоже равняется UNKNOWN. Если итоговым результатом раздела WHERE является FALSE или UNKNOWN, то соответствующая строка отфильтровывается. Рассмотрим запрос Q23, содержащий подзапрос с >= ALL.
Q23
SELECT T1.C FROM T1 WHERE T1.x <> ALL (SELECT T2.y FROM T2 WHERE T2.z > 10);
Предположим, что подзапрос возвращает набор значений {7,11,NULL}, а в T1.x имеется следующий набор значений: {NULL,5,11}. Операция >= ALL может быть выражена как T1.x <> 7 AND T1.x <> 11 AND T1.x <> NULL. Это выражение вычисляется в UNKNOWN, так как T1.x <> NULL всегда вычисляется в UNKNOWN независимо от значения T1.x. Поэтому для этого набора значений Q23 вообще не вернет строк. Обычное антисоединение, если его использовать в этом случае, некорректно вернет {NULL,5}.
Для демонстрации повышения производительности за счет использования антисоединения с учетом наличия неопределенных значений проводилось две группы экспериментов. В экспериментах первой группы использовался запрос Q26, выдающий из заданного списка поставщиков имена поставщиков, у которых не было заказов в заданном месяце (в январе 1996 г.). В этой схеме L_SUPPKEY может содержать неопределенные значения, а S_SUPPKEY — нет.
Q26
SELECT s_name FROM supplier WHERE s_suppkey in (<supplier_list>) AND s_suppkey <> ALL (SELECT l_suppkey FROM lineitem WHERE l_shipdate >>= '1996-01-01' AND l_shipdate < '1996-02-01');
Без использования NAAJ вложенность подзапроса в Q26 устранить невозможно, а это приводит к коррелированному выполнению, когда мы должны выполнять подзапрос для каждой строки таблицы поставщиков. Такой запрос выполняется мучительно долго, поскольку для вычисления коррелированного предиката невозможно использовать индексное зондирование (index probe). Это связано с тем, что Oracle преобразует подзапрос с ALL в подзапрос с NOT EXISTS и использует коррелированный предикат, который эквивалентен предикату (l_suppkey IS NULL OR l_suppkey = r_suppkey). Единственным достоинством выполнения этого запроса без использования NAAJ является разделение таблицы lineitem по l_shipdate, позволяющее сократить объем сканирования до одного раздела. Рис. 10 иллюстрирует прирост производительности при возрастании числа поставщиков до 40. Преобразованный запрос выполняется с использованием антисоединения таблиц supplier и lineitem с учетом наличия неопределенных значений; антисоединие вычисляется на основе хэширования.
Второй эксперимент проводился на реальной рабочей нагрузке — 241000 запросов, производимых Oracle Applications. Схема содержит около 14 000 таблиц, представляющих приложения кадровой службы (human resources), финансовые приложения (financial), приложения приема заявок (order entry), CRM, управления цепочкой поставок (supply chain) и т.д. Базы данных большинства приложений имеют сильно нормализованные схемы. Число таблиц в запросах варьируется между 1 и 159, в среднем — 8 таблиц на запрос.
Рис.10. Выполнение запроса без NAAJ и с NAAJ
Имелось 72 запроса с DISTINCT и подзапросами с <> ALL, пригодных для выполнения на основе NAAJ. Для 68 из них при использовании NAAJ затраченное процессорное время сократилось в среднем в 736730 раз! Один запрос выполнялся 350 секунд без использования NAAJ и 0,001 секунды — с использованием NAAJ. Время выполнения 4 запросов увеличилось в среднем в 100 раз, причем в наихудшем случае затраченное процессорное время увеличилось c 0,000001 секунды до 0,016 секунды.
