Почему INTERSECT такой же медленный, как вложенный JOIN?

Я использую MS SQL.

У меня есть огромная таблица с индексами, чтобы сделать этот запрос быстрым:

select userid from IncrementalStatistics where
IncrementalStatisticsTypeID = 5 and
IncrementalStatistics.AssociatedPlaceID = 47828 and
IncrementalStatistics.Created > '12/2/2010

Он возвращается менее чем за 1 секунду. В таблице миллиарды строк. Есть только около 10000 результатов.

Я ожидаю, что этот запрос также завершится примерно через секунду:

select userid from IncrementalStatistics where
IncrementalStatisticsTypeID = 5 and
IncrementalStatistics.AssociatedPlaceID = 47828 and
IncrementalStatistics.Created > '12/2/2010'

intersect

select userid from IncrementalStatistics where
IncrementalStatisticsTypeID = 5 and
IncrementalStatistics.AssociatedPlaceID = 40652 and
IncrementalStatistics.Created > '12/2/2010'

intersect

select userid from IncrementalStatistics where
IncrementalStatisticsTypeID = 5 and
IncrementalStatistics.AssociatedPlaceID = 14403 and
IncrementalStatistics.Created > '12/2/2010'

Но это занимает 20 секунд. Все отдельные запросы занимают ‹ 1 секунды и возвращают около 10 000 результатов.

Я ожидаю, что SQL внутренне выдаст результаты каждого из этих подзапросов в хеш-таблицу и сделает хэш-пересечение - должно быть O (n). Наборы результатов достаточно велики, чтобы поместиться в памяти, поэтому я сомневаюсь, что это проблема ввода-вывода.

Я написал альтернативный запрос, который представляет собой просто серию вложенных JOIN, и это также занимает около 20 секунд, что имеет смысл.

Почему INTERSECT работает так медленно? Сводится ли это к JOIN на ранней стадии обработки запроса?


sql join query-optimization algorithm intersect
person John Shedletsky    schedule 06.12.2010    source источник
comment
Я сомневаюсь, что это проблема с вводом-выводом. Какой план объяснения говорит о том, что это самая затратная часть запроса?   -  person Donnie    schedule 07.12.2010
comment
Есть ли в MS SQL EXPLAIN или какой-либо способ просмотра плана запроса? Основываясь на ответах других людей, похоже, что реализация INTERSECT просто не умна...   -  person Brendan OConnor    schedule 08.12.2010
comment
@Brendan - да, есть хорошая визуализация плана запроса. Этот запрос не казался достаточно тонким, чтобы прибегать к нему — я искал интуитивный аргумент.   -  person John Shedletsky    schedule 08.12.2010

Ответы (1)


arrow_upward
14
arrow_downward

Вместо этого попробуйте это. Очевидно, не проверено, но я думаю, что это даст вам желаемые результаты.

select userid 
    from IncrementalStatistics 
    where IncrementalStatisticsTypeID = 5 
        and IncrementalStatistics.AssociatedPlaceID in (47828,40652,14403)  
        and IncrementalStatistics.Created > '12/2/2010'
    group by userid
    having count(distinct IncrementalStatistics.AssociatedPlaceID) = 3
person Joe Stefanelli    schedule 06.12.2010
comment
Чувак! Это было на тонну быстрее. Я хотел бы понять, почему? Кажется, что под капотом на самом деле выполняется больше работы, чем указано выше. - person John Shedletsky; 07.12.2010
comment
@John Shedletsky: Это быстрее, потому что это один проход по таблице IncrementalStatistics по сравнению с тремя совершенно отдельными запросами. - person Joe Stefanelli; 07.12.2010
comment
@Joe: Я сомневаюсь, что это причина того, что это намного быстрее. ПЕРЕСЕЧЕНИЕ 2 наборов из 10000 строк в памяти занимает менее 1 секунды на любом ПК, поэтому единственная причина, по которой запрос Джона может выполняться дольше, чем 3*1+1+1=5 секунд, заключается в том, что механизм БД выбирает плохой план для его выполнения. исходный запрос. - person j_random_hacker; 07.12.2010
comment
@j_random_hacker: Очевидно, трудно сказать, не имея доступа к системе ОП. Когда я сам сравнивал это, логическое чтение и время ЦП были очень близки для обеих версий, однако план выполнения для версии с пересечением включает 3 отдельных операции поиска индекса по сравнению с одним поиском индекса для группы по/имеющей версии. - person Joe Stefanelli; 07.12.2010
comment
Хороший вопрос для интервью. Я собираюсь использовать его на следующем веб-инженере, которого мы наймем. - person John Shedletsky; 07.12.2010
comment
@John: Если вы ищете вопрос для интервью с правильным ответом (в отличие от того, чтобы просто увидеть, как кандидат работает с возможностями), я думаю, что это не очень хороший выбор, поскольку он зависит от знания непостижимого внутреннего поведения MS. Планировщик SQL-запросов. Извините за такой негатив, здорово, что ответ Джо сработал для вас, но на самом деле это просто удача (как он говорит, две версии были очень похожи в его системе). - person j_random_hacker; 08.12.2010
comment
Хорошее использование group by ... having count() - person Scotty.NET; 28.11.2013