Почему один запрос очень медленный, но идентичный запрос к аналогичной таблице выполняется в мгновение ока

У меня есть этот запрос ... который выполняется очень медленно (почти минуту):

select distinct main.PrimeId 
from PRIME main 
join   
( 
select distinct p.PrimeId   from PRIME p   
left  outer join ATTRGROUP a 
on p.PrimeId = a.PrimeId   or p.PrimeId = a.RelatedPrimeId    
where a.PrimeId is not null and a.RelatedPrimeId is not null  
) mem  
on main.PrimeId = mem.PrimeId

В таблице PRIME 18k строк, и имеет PK на PrimeId.

Таблица ATTRGROUP содержит 24k строк и имеет составной PK для PrimeId, col2, затем RelatedPrimeId, а затем cols 4-7. Также есть отдельный индекс для RelatedPrimeId.

Запрос в конечном итоге возвращает 8,5 тыс. Строк - различные значения PrimeId в таблице PRIME, которые соответствуют PrimeId или RelatedPrimeId в таблице ATTRGROUP

У меня идентичный запрос, использующий ATTRADDRESS вместо ATTRGROUP. ATTRADDRESS имеет идентичную структуру ключа и индекса, что и ATTRGROUP. на нем всего 11 тыс. строк, что, правда, меньше, но в этом случае запрос выполняется примерно за cond и возвращает 11k строк.

Итак, мой вопрос:

Как может запрос быть намного медленнее в одной таблице, чем в другой, несмотря на то, что структуры идентичны.

Пока что я пробовал это на SQL 2005 и (с использованием той же базы данных, обновленной) SQL 2008 R2. Двое из нас независимо друг от друга получили одинаковые результаты, восстановив одну и ту же резервную копию на двух разных компьютерах.

Другие подробности:

• бит в скобках выполняется менее чем за секунду, даже в медленном запросе
• есть возможный ключ к плану выполнения, которого я не понимаю. Вот его часть с подозрительной операцией со строками в 320000000 строк:

Однако фактическое количество строк в этой таблице немногим превышает 24 КБ, а не 320 МБ!

Если я реорганизую часть запроса в скобках, так что он использует UNION, а не OR, таким образом:

select distinct main.PrimeId 
from PRIME main 
join   
( 
select distinct p.PrimeId   from PRIME p   
left  outer join ATTRGROUP a 
on p.PrimeId = a.PrimeId
where a.PrimeId is not null and a.RelatedPrimeId is not null  
UNION
select distinct p.PrimeId   from PRIME p   
left  outer join ATTRGROUP a 
on p.PrimeId = a.RelatedPrimeId    
where a.PrimeId is not null and a.RelatedPrimeId is not null  
) mem  
on main.PrimeId = mem.PrimeId

... тогда медленный запрос занимает менее секунды.

Я был бы очень признателен за любое понимание этого! Дайте мне знать, если вам понадобится дополнительная информация, и я обновлю вопрос. Спасибо!

Кстати, я понимаю, что в этом примере есть избыточное соединение. Это не может быть легко удалено, поскольку в производстве все это генерируется динамически, а бит в скобках принимает множество различных форм.

Изменить :

Я перестроил индексы в ATTRGROUP, делает нет существенной разницы.

Edit 2 :

Если я использую временную таблицу, например:

select distinct p.PrimeId into #temp
from PRIME p   
left  outer join ATTRGROUP a 
on p.PrimeId = a.PrimeId   or p.PrimeId = a.RelatedPrimeId    
where a.PrimeId is not null and a.RelatedPrimeId is not null  

select distinct main.PrimeId 
from Prime main join   
#temp mem  
on main.PrimeId = mem.PrimeId

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

Править 3 :

Обновление статистики тоже не имеет значения.

Спасибо за все ваши предложения.