Правильная ссылка на эту страницу
http://az-design.ru/Support/DataBase/SQL/SQL0002.shtml

SQL-рецепт – как найти того, кого нет (вер.2)

       Так как никто не предложил более красивого решения, то пришлось искать самому. Тем более, что опять приспичило.
       Итак, имеем две таблицы:

Create table AZLibrPersons 
    (AZRowKey   AZInt32 not null Primary key,
     LibrTitle  AZTitle,
     LibrPath   AZTitle,
     ......     .....
     DtModify   AZTStamp);
Create table AZLibrPersonSrc 
    (Person     AZSID not null references AZLibrPersons on update cascade,
     Source     AZSID not null references AZLibrSources on update cascade,
     Notes      AZNotes,
     DtModify   AZTStamp,
Primary key (Person,Source));
Commit;

       Задача — найти записи в таблице AZLibrPersons, которые отсутствуют в таблице AZLibrPersonSrc для выбранного поля Source и в то же время содержат в поле LibrTitle образец поиска.
       Для простоты обсуждений обозначим количество записей в большой таблице (AZLibrPersons) как A, а в малой таблице (AZLibrPersonSrc) как B.
       Если использовать конструкцию с not in, как показано ниже:

Select AZRowKey,LibrTitle from AZLibrPersons
 where AZrowKey not in (Select Person from AZLibrPersonSrc where Source=1); 

       То получаем очень долгий запрос.
       Для тестирования будем использовать Firebird 2.0 и EMS SQLManager2005, чтобы была какая-то определенность.
       Анализ производительности в EMS показывает, что при выполнении запроса выполняются индексированных чтений:

       (A - B/2)*B + B/2

       и неиндексированных чтений = A

       Что для реальной ситуации (A=8783, B=2752) дает 20385440 индексированных чтений. Реально таблицы будут иметь значения A=50000 и B=3000. Хотя возможен вариант когда таблица B=12700 записей. В таком случае полное число чтений будет составлять 554'361'350. Естественно, что для последовательного поиска такой алгоритм непригоден.
       Этого следовало ожидать. Предикат IN приводит к сравнению AZRowKey с каждым возвращенным значением набора, пока не будет найдено соответствие. С точки зрения производительности предикат IN не будет полезен, когда подзапрос возвращает достаточно большое количество значений.

       Но если использовать конструкцию с внешним соединением, что результаты можно сильно улучшить.

       Для начала вспомним, что такое внешнее соединение.
       В отличие от внутреннего соединения оператор внешнего соединения выбирает строки участвующих таблиц, даже если в некоторых случаях не найдено соответствие. Когда полное соответствие строк не может быть сформировано соединением, тогда "отсутствующие" элементы данных формируются как NULL.
       Каждое внешнее соединение имеет правую и левую часть, левая часть является потоком, который присутствует в левой части фразы JOIN, а правая часть — потоком, который назван аргументом фразы JOIN. В операторе, содержащем множество соединений, понятия "левый" и "правый" относительны — правый поток одного предложения соединения может быть левым другого предложения.
       "Левый" и "правый" значимы в логике спецификаций внешнего соединения. Внешнее соединение может быть левым, правым и полным. Каждый тип внешнего соединения создает различный выходной набор данных из тех же входных потоков. Ключевые поля LEFT, RIGHT и FULL достаточны для установления факта, что соединение "внешнее"; ключевое слово OUTER является необязательной частью синтаксиса.
       Левое внешнее соединение в запросе создает набор данных, состоящий из полностью заполненных столбцов, где найдены соответствующие строки (как и во внутреннем соединении), а также частично заполненных строк для каждого экземпляра, где соответствие правой стороны не найдено для ключа левой стороны. Нессответствующие столбцы будут "заполнены" значением NULL. Вот оператор, который иллюстирует вышесказанное:

Select Table1.PK, Table1.Col1, Table2.PKX, Table2.ColX
 from Table1 left outer join Table2
    on table1.PK=Tablw2.FK
where ..... <условия поиска>

       на рисунке показано, как будут объединены потоки для левого соединения:

PK COL1
99 Abc
100 Bcd
101 Cde
102 Def
103 Efg
104 Fgh
105 Ghi
106 Hij
107 Ijk
108 Jkl
109 Klm
Table 1
 
PKX COLX FK
234 AAA 99
235 BBB 101
236 CCC 102
237 DDD 104
238 EEE 105
239 FFF 106
240 GGG 109
241 HHH 111
242 III 114
243 JJJ 115
244 KKK 116
Table 2
 
PK COL1 PKX COLX
99 Abc 234 AAA
100 Bcd NULL NULL
101 Cde 235 BBB
102 Def 236 CCC
103 Efg NULL NULL
104 Fgh 237 DDD
105 Ghi 238 EEE
106 Hij 239 FFF
107 Ijk NULL NULL
108 Jkl NULL NULL
109 Klm 240 GGG
Joined set

       В этом случае вместо того чтобы отбрасывать строки левого потока, для которых нет соответствия в правом потоке, запрос создает строку, содержащие данные из левого потока и NULL для каждого указанного в правом потоке столбца.
       Если внимательно присмотреться к результату соединения, то увидим, что необходимые нам строки содержат NULL в поле COLX. Таким образом если выбрать только эти строки, то получим требуемый результат. Это можно выполнить следующим запросом:

Select p.AZRowKey,p.LibrTitle,ps.Person
from AZLibrPersons p
Left Outer Join AZLibrPersonSrc ps
  on ps.Person=p.AZRowKey
where ps.Person is null

       При этом быстродействие этого запроса несравнимо выше. Для его выполнения необходимо сделать только A индексируемых чтений и B неиндексируемых чтений. Что для предыдущего случая равносильно 8783+2752=11535 чтений, что в 1767 раз меньше. А для полного варианта ускорение составляет более 48000 раз. Самое главное, что зависимость времени выполнения запроса от размеров таблиц линейная, а не степенная.
       Проблема осталась только в том, что из таблицы AZLibrPersonSrc нужно выбирать не все записи, а только те, у которых поле Source=N. Однако если подумать, то можно увидеть что запрос и таблица это в принципе одно и тоже и тогда конечный запрос можно записать следующим образом:

Select p.AZRowKey,p.LibrTitle,ps.Person
from AZLibrPersons p
Left Outer Join (Select Person from AZLibrPersonSrc where Source=N) ps
  on ps.Person=p.AZRowKey
where ps.Person is null and p.LibrTitle like 'Text%'

       Практика показала, что такой запрос работает очень быстро и может быть использован при последовательном поиске.

       При обсуждении в рабочей группе
       http://groups.google.com/group/ru-firebird/browse_thread/thread/56ef506f9fa37114#
       Влад Хорсун уточнил что LEFT JOIN нужно делать с DISTINCT выборкой из правого множества, за что ему большое спасибо. Тогда запрос будет выглядеть следующим образом:

Select p.AZRowKey,p.LibrTitle,ps.Person
from AZLibrPersons p
Left Outer Join (Select distinct Person from AZLibrPersonSrc where Source=N) ps
  on ps.Person=p.AZRowKey
where ps.Person is null and p.LibrTitle like 'Text%'

       Но в данном случае уникальность значений в обоих таблицах обеспечивается Primary Key, как это и бывает в большинстве подобных случаев.

       Однако обсуждение дало и новые идеи. А что если использовать еще один предикат Exists. Как пишет Хелен Борри "Самый полезный из всех предикатов существования - Exists представляет самый быстрый из всех возможных методов способ проверки существования значения в другой таблице.
       Стандартный предикат SQL EXISTS(значение-подзапроса) и его противоположный аналог NOT EXISTS дают способ выполнени проверки существования набора, который является очень дешевым с точки зрения используемых ресурсов. Он не генерирует выходной набор, а просто проходит по таблице, пока не найдет строку, соответствующую условиям в подзапросе. В этот момент возвращается истина. Если же не находится ни одной строки, то возвращается ложь." (стр.434).
       Таким образом можно построить другой запрос, который должен выполняется еще быстрее.

Select p.AZRowKey,p.LibrTitle from AZLibrPersons p
 where not exists

(Select Person from AZLibrPersonSrc ps where ps.Source=1 and ps.Person=p.AZRowKey);

       Попробуем измерить затраты времени с помощью isql.exe, т.е. выполняем три запроса в скрипте и посмотрим ту статистику, которую он выдает. А также выполним эти запросы в реальном приложении, чтобы учесть возможные накладные расходы. Количество строк в AZLibrPersons=8783, AZLibrPersonSrc=2752.

1)

Select p.AZRowKey,p.LibrTitle from AZLibrPersons p
 where not exists
 (Select Person from AZLibrPersonSrc ps where ps.Source=1 and ps.Person=p.AZRowKey);

2)

Select p.AZRowKey,p.LibrTitle,ps.Person
 from AZLibrPersons p
 Left Outer Join (Select Person from AZLibrPersonSrc where Source=1) ps
 on ps.Person=p.AZRowKey
 where ps.Person is null;

3)

Select p.AZRowKey,p.LibrTitle from AZLibrPersons p
 where p.AZrowKey not in (Select Person from AZLibrPersonSrc where Source=1);
  Запрос 1 Запрос 2 Запрос 3
Delta memory 101704 564 11576
Fetches 55683 55346 40811928
Elapsed time 0.110 sec 0.110 sec 189.200 sec
Приложение 0.109 sec 0.093 sec 191.728 sec

       Как видно в данном случае запросы 1 и 2 практически равноценны. Возможно при достаточно большом количестве уникальных записей в обоих таблицах запрос с внешним соединением будет выполняться несколько быстрее. Но в случаях когда таблица в подзапросе будет содержать много повторяющихся записей, то запрос 1 будет работать много быстрее, так как предикат Exists отлавливает только первую попавшуюся запись.
       В любом случае план 1 и 2 запросов одинаковый - внешний запрос читается 1 раз без индексов, внутренний запрос читается 1 раз по индексу. И на конкретных данных лучше попробовать оба.

© 21.04.2008, Архангельский А.Г.
исправлено 05.05.2008

Оглавление
Главная страница




Дата последнего изменения:
Thursday, 21-Aug-2014 09:10:44 MSK


Постоянный адрес статьи:
http://az-design.ru/Support/DataBase/SQL/SQL0002.shtml