Re[3]: Вопрос на собеседовании (как надо было ответить?)
От: seregaa Ниоткуда http://blogtani.ru
Дата: 17.02.09 15:16
Оценка: 11 (2) +1
Здравствуйте, Ромашка, Вы писали:

Р>С увлечением наблюдал за дискуссией. Рад за MasterZiv и его правильный

Р>ответ (ниже по ветке).
увы, как оказалось — неправильный (((

Р>Небольшая ремарка:

Р>Не поймут и не переформулируют. JOIN по OR не оставляет оптимизатору
Р>шансов — будет использован только NESTED LOOP JOIN, а ему индексы пофигу.
да вобщем то несложно разбить конкретно это условие объединения на 4 _независимых_ подусловия, каждое из которых можно выполнить по отдельности (а корректность таких преобразований можно проверить математически):

select
    T1.F1, T2.F1
from
    Table1 T1 inner join Table2 T2
           on T1.F2 = T2.F2 and T1.F3 != T2.F3
union all
select
    T1.F1, T2.F1
from
    Table1 T1 inner join Table2 T2
           on T1.F2 != T2.F2 and T1.F3 = T2.F3
union all
select
    T1.F1, T2.F1
from
    Table1 T1 inner join Table2 T2
           on T1.F2 = T2.F2 and T1.F3 = T2.F3
union all
select
    T1.F1, null 
from
    Table1 T1
where 
    not exists (select * from Table2 T2 where T1.F2 = T2.F2 or T1.F3 = T2.F3)


здесь тоже возможны сканы таблиц, но по крайней мере без NL-ов. Время выполнения запроса под mssql ~1 сек. Для таблиц созданы кластерные индексы по F1 и простые не составные индексы по F2 и F3. План:


имхо здесь основная сложность в оценке время выполнения запроса и следовательно высок риск промахнуться с выбором оптимального варианта.
Мобильная версия сайта RSDN — http://rsdn.org/forum/rsdn/6938747
Автор: sergeya
Дата: 19.10.17
Re[2]: Вопрос на собеседовании (как надо было ответить?)
От: ilya_ny  
Дата: 16.02.09 17:56
Оценка: 2 (2)
Здравствуйте, _d_m_, Вы писали:

[я подправил только форматирование]

MT>>

MT>>Чем плох такой запрос? Как можно его оптимизировать?

MT>>select T1.F1, T2.F1
MT>>from Table1 T1
MT>>left join Table2 T2 on T1.F2=T2.F2 or T1.F3=T2.F3


___>or в джойне.


___>select T1.F1, T2.F1
___>from Table1 T1 left join Table T2 on T1.F2 = T2.F2
___>union all
___>select T1.F1, T2.F1
___>from Table1 T1 left join Table T2 on T1.F3 = T2.F3


неверно, это не эквивалентные запросы

пример: таблицы T1 (f1, f2, f3), T2 (f1, f2, f3) одинаковы и имеют след. данные:

f1, f2, f3
(1, 0, 0)
(1, 0, 1)


тогда исходный запрос вернет четыре ряда (1, 1), а твой 6 рядов (1, 1)
Re[3]: Вопрос на собеседовании (как надо было ответить?)
От: MasterZiv СССР  
Дата: 17.02.09 11:18
Оценка: 1 (1) +1
Овощ пишет:

> MZ> select T1.F1, case when T2_1.F1 then T2_1.F1 else T2_2.F1 end as T2F1

> MZ> from Table1 T1
> MZ> left join Table2 T2_1 on T1.F2=T2.F2
> MZ> left join Table2 T2_2 on T1.F3=T2.F3

тогда

> MZ> from Table1 T1

> MZ> left join Table2 T2_1 on T1.F2=T2.F2
> MZ> left join Table2 T2_2 on T1.F3=T2.F3 and not T1.F2=T2.F2
Posted via RSDN NNTP Server 2.1 beta
Re[5]: Вопрос на собеседовании (как надо было ответить?)
От: ilya_ny  
Дата: 17.02.09 02:10
Оценка: -1 :)
_d_m_ работает над оптимизацией запроса (http://files.rsdn.ru/21534/me.JPG)

Re: Вопрос на собеседовании (как надо было ответить?)
От: MasterZiv СССР  
Дата: 17.02.09 08:03
Оценка: +2
MitjaT пишет:

> Чем плох такой запрос? Как можно его оптимизировать?

>
> select T1.F1, T2.F1
> from Table1 T1
> left join Table2 T2 on T1.F2=T2.F2 or T1.F3=T2.F3

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

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

Так что вопрос, если говорить строго формально, не правомерен.
Но если при этом сделать огооврку, что типа "какие плохие
ситуации могут возникать при выполнении этого запроса на
практике", то в общем и ничего.

А переписать надо было бы так:

select T1.F1, case when T2_1.F1 then T2_1.F1 else T2_2.F1 end as T2F1
from Table1 T1
left join Table2 T2_1 on T1.F2=T2.F2
left join Table2 T2_2 on T1.F3=T2.F3
Posted via RSDN NNTP Server 2.1 beta
Re[2]: Вопрос на собеседовании (как надо было ответить?)
От: Ромашка Украина  
Дата: 17.02.09 11:58
Оценка: 5 (1)
MasterZiv пишет:

С увлечением наблюдал за дискуссией. Рад за MasterZiv и его правильный
ответ (ниже по ветке).

> плох тем, что JOIN по OR может быть плохо воспринят

> оптимизатором и не будет использован индекс при выполнении JOIN-а.
> Но это — только один из возможных вариантов
> развития событий. Думаю, многие оптимизаторы поймут эту
> ситуацию правильно и сами сделают правильную переформулировку запроса.

Небольшая ремарка:
Не поймут и не переформулируют. JOIN по OR не оставляет оптимизатору
шансов — будет использован только NESTED LOOP JOIN, а ему индексы пофигу.
Posted via RSDN NNTP Server 2.1 beta


Всё, что нас не убивает, ещё горько об этом пожалеет.
Re[4]: Вопрос на собеседовании (как надо было ответить?)
От: _d_m_  
Дата: 17.02.09 00:58
Оценка: 2 (1)
Здравствуйте, ilya_ny, Вы писали:

_>>неверно, это не эквивалентные запросы


Ах да, извиняюсь поспешил. Ладно, вот вам пища для размышлений:
DDL:
CREATE TABLE dbo.Table1(
    F1 int NOT NULL IDENTITY (1, 1),
    F2 int NOT NULL,
    F3 int NOT NULL
)
GO
ALTER TABLE dbo.Table1 ADD CONSTRAINT PK_Table1 PRIMARY KEY CLUSTERED (F1)
GO

CREATE TABLE dbo.Table2(
    F1 int NOT NULL IDENTITY (1, 1),
    F2 int NOT NULL,
    F3 int NOT NULL
)
GO
ALTER TABLE dbo.Table2 ADD CONSTRAINT PK_Table2 PRIMARY KEY CLUSTERED (F1)
GO
CREATE NONCLUSTERED INDEX [IX_Table2.F2] ON dbo.Table2 (F2)
GO
CREATE NONCLUSTERED INDEX [IX_Table2.F3] ON dbo.Table2 (F3)
GO

Наполнение данными:
set nocount on;
GO

-- Создаем записи которые не будут попадать под условие запроса
declare @i int;
set @i = 0;
begin tran;
while @i < 90000 begin
    insert Table2(F2, F3) values(@i, @i + 100000);
    set @i = @i + 1;
end;
commit;

insert
    Table1(
        F2,
        F3
    )
select top 2000
    F2 + 200000,
    F2 + 300000
from
    Table2
order by
    F1
;

-- Создаем записи которые будут попадать под условие запроса F2 = F2
set @i = 90000;
begin tran;
while @i < 92000 begin
    insert Table1(F2, F3) values(@i, @i + 100000);
    insert Table2(F2, F3) values(@i, @i + 200000);
    set @i = @i + 1;
end;
commit;

-- Создаем записи которые будут попадать под условие запроса F3 = F3
set @i = 92000;
begin tran;
while @i < 94000 begin
    insert Table1(F2, F3) values(@i + 100000, @i);
    insert Table2(F2, F3) values(@i + 200000, @i);
    set @i = @i + 1;
end;
commit;

-- Создаем записи которые будут попадать под условие запроса F2 = F2 = F3 = F3
set @i = 94000;
begin tran;
while @i < 96000 begin
    insert Table1(F2, F3) values(@i, @i);
    insert Table2(F2, F3) values(@i, @i);
    set @i = @i + 1;
end;
commit;

Запросы (исходный и эквивалентный более правильный):
select
    T1.F1,
    T2.F1
from
    Table1 T1
        left join
    Table2 T2
            on
                T1.F2 = T2.F2 or T1.F3 = T2.F3
;

select
    T1F1,
    max(T2F1)
from
    (select
        T1.F1 as T1F1,
        T2.F1 as T2F1
    from
        Table1 T1
            inner join
        Table2 T2
                on
                    T1.F2 = T2.F2
    union all
    select
        T1.F1,
        T2.F1
    from
        Table1 T1
            inner join
        Table2 T2
                on
                    T1.F3 = T2.F3
    union all
    select
        T1.F1,
        null
    from
        Table1 T1
    ) as T
group by
    T1F1
;

А теперь план. Исходный запрос выполнялся более 5 мин, эквивалентный правильный — менее секунды:
Re[2]: Вопрос на собеседовании (как надо было ответить?)
От: nikov США http://www.linkedin.com/in/nikov
Дата: 16.02.09 17:21
Оценка: 1 (1)
Здравствуйте, _d_m_, Вы писали:

___>or в джойне.


Неужто оптимизатор сам не просекает?
Re[2]: Вопрос на собеседовании (как надо было ответить?)
От: MitjaT Россия  
Дата: 16.02.09 18:15
Оценка: 1 (1)
Здравствуйте, _d_m_, Вы писали:

___>or в джойне.


___>
___>select
___>    T1.F1,
___>    T2.F1
___>from
___>    Table1 T1
___>        left join
___>    Table T2
___>            on
___>                T1.F2 = T2.F2
___>union all
___>select
___>    T1.F1,
___>    T2.F1
___>from
___>    Table1 T1
___>        left join
___>    Table T2
___>            on
___>                T1.F3 = T2.F3
___>;
___>



Результат может быть неверным. В результирующий набор может попасть дважды одна и та же строка из декартова произведения двух таблиц, в том случае, если T1.F2 = T2.F2 and T1.F3 = T1.F3.
Надо в этом случае дополнительно ввести условие, что "сведет на нет" такую оптимизацию.
Re[4]: Вопрос на собеседовании (как надо было ответить?)
От: Ромашка Украина  
Дата: 17.02.09 12:04
Оценка: 1 (1)
MasterZiv пишет:
> тогда
>
>> MZ> from Table1 T1
>> MZ> left join Table2 T2_1 on T1.F2=T2.F2
>> MZ> left join Table2 T2_2 on T1.F3=T2.F3 and not T1.F2=T2.F2

Давай не будем гадать. Ответ правильный, если не считать некоторых
описок. Я просто напишу правильно:

select
     T1.F1, IsNull(T2.F1, T3.F1) as F1
from Table1 T1
    left join Table2 T2 on T1.F2 = T2.F2
    left join Table2 T3 on T1.F3 = T3.F3 and not T1.F2 = T3.F2
order by T1.F1
Posted via RSDN NNTP Server 2.1 beta


Всё, что нас не убивает, ещё горько об этом пожалеет.
Re: Вопрос на собеседовании (как надо было ответить?)
От: _d_m_  
Дата: 16.02.09 16:50
Оценка: -1
Здравствуйте, MitjaT, Вы писали:

MT>Здравствуйте!


MT>Как вам такой письменный вопрос на собеседовании?

MT>Как правильно на него ответить?

MT>

MT>Чем плох такой запрос? Как можно его оптимизировать?

MT>select T1.F1, T2.F1
MT>from Table1 T1
MT>left join Table2 T2 on T1.F2=T2.F2 or T1.F3=T2.F3


or в джойне.

select
    T1.F1,
    T2.F1
from
    Table1 T1
        left join
    Table T2
            on
                T1.F2 = T2.F2
union all
select
    T1.F1,
    T2.F1
from
    Table1 T1
        left join
    Table T2
            on
                T1.F3 = T2.F3
;
Вопрос на собеседовании (как надо было ответить?)
От: MitjaT Россия  
Дата: 16.02.09 16:03
Оценка:
Здравствуйте!

Как вам такой письменный вопрос на собеседовании?
Как правильно на него ответить?

Чем плох такой запрос? Как можно его оптимизировать?

select T1.F1, T2.F1
from Table1 T1
left join Table2 T2 on T1.F2=T2.F2 or T1.F3=T2.F3

Re[3]: Вопрос на собеседовании (как надо было ответить?)
От: ilya_ny  
Дата: 16.02.09 18:00
Оценка:
_>неверно, это не эквивалентные запросы

_>пример: таблицы T1 (f1, f2, f3), T2 (f1, f2, f3) одинаковы и имеют след. данные:


_>
_>f1, f2, f3
_>(1, 0, 0)
_>(1, 0, 1)
_>


_>тогда исходный запрос вернет четыре ряда (1, 1), а твой 6 рядов (1, 1)




ну а если таблицы разные, то и результаты запросов будут разные
T1
(1, 0, 0)
(2, 0, 1)

T2
(3, 0, 0)
(4, 0, 1)
Re[3]: Вопрос на собеседовании (как надо было ответить?)
От: Mr.Cat  
Дата: 16.02.09 18:30
Оценка:
Здравствуйте, MitjaT, Вы писали:
MT>Надо в этом случае дополнительно ввести условие, что "сведет на нет" такую оптимизацию.

Сведет ли? Насколько я понимаю, or может помешать использовать при джойне индексы, что (в случае больших исходных таблиц и небольшого предполагаемого количества строк в результате) значительно сильнее ударит по перфомансу, чем необходимость выбрать distinct из результата юниона.

Чем гадать — лучше бы поглядели план запроса на интересующей Вас базе и запостили сюда.
Re[4]: Вопрос на собеседовании (как надо было ответить?)
От: MitjaT Россия  
Дата: 16.02.09 18:50
Оценка:
Здравствуйте, Mr.Cat, Вы писали:

MC>Чем гадать — лучше бы поглядели план запроса на интересующей Вас базе и запостили сюда.


Пожалуйста:



Запросы идентичны.
Re: Вопрос на собеседовании (как надо было ответить?)
От: Tissot Россия  
Дата: 16.02.09 18:51
Оценка:
Здравствуйте, MitjaT, Вы писали:

MT>Как правильно на него ответить?


MT>

MT>Чем плох такой запрос? Как можно его оптимизировать?

MT>select T1.F1, T2.F1
MT>from Table1 T1
MT>left join Table2 T2 on T1.F2=T2.F2 or T1.F3=T2.F3


Это весь вопрос или что-то еще было?
Re[5]: Вопрос на собеседовании (как надо было ответить?)
От: Mr.Cat  
Дата: 16.02.09 19:01
Оценка:
Здравствуйте, MitjaT, Вы писали:
MT>Запросы идентичны.

Вот и ответ. MSSQL может припахать индексы при or. Возможно, так могут не все базы, и в этом была суть вопроса. Или от Вас хотели услышать, что в общем и целом сложные функции в условии джойна стоит вручную упрощать.

Или мы действительно не туда копаем.
Re[2]: Вопрос на собеседовании (как надо было ответить?)
От: MitjaT Россия  
Дата: 16.02.09 19:18
Оценка:
Здравствуйте, Tissot, Вы писали:

T>Это весь вопрос или что-то еще было?


Весь, дословно.
Re: Вопрос на собеседовании (как надо было ответить?)
От: MozgC США http://nightcoder.livejournal.com
Дата: 16.02.09 19:51
Оценка:
Здравствуйте, MitjaT, Вы писали:

MT>Как вам такой письменный вопрос на собеседовании?

Смотря на какую позицию, может конкретно разработчик баз данных и должен знать, остальные — сомневаюсь.

MT>Чем плох такой запрос?

Хз.

MT>Как можно его оптимизировать?

Хз.

В общем лично я бы на вопрос не ответил, если вам интересно такое мнение со стороны.
Re[3]: Вопрос на собеседовании (как надо было ответить?)
От: _d_m_  
Дата: 17.02.09 00:44
Оценка:
Здравствуйте, nikov, Вы писали:

N>Здравствуйте, _d_m_, Вы писали:


___>>or в джойне.


N>Неужто оптимизатор сам не просекает?


ИИ?
Запрос на самом деле уродский — этакий сферический конь в вакууме, такой в реальной жизни не встречался мне никогда. Такую структуру данных даже не придет в голову создать начинающему разработчику с особо извращенной фантазией.
Re[5]: Вопрос на собеседовании (как надо было ответить?)
От: _d_m_  
Дата: 17.02.09 01:02
Оценка:
Здравствуйте, MitjaT, Вы писали:

MT>Здравствуйте, Mr.Cat, Вы писали:


MC>>Чем гадать — лучше бы поглядели план запроса на интересующей Вас базе и запостили сюда.


MT>Пожалуйста:

MT>
MT>

MT>Запросы идентичны.


Неверно.
Вот первых: Чтобы сравнить запросы их надо ставить в одном батче.
Во вторых: Что с индексами? Там кроме кластерного суррогатного первичного ключа, по моему больше нихрена нет.
Re[6]: Вопрос на собеседовании (как надо было ответить?)
От: _d_m_  
Дата: 17.02.09 01:04
Оценка:
Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, MitjaT, Вы писали:

MT>>Запросы идентичны.

Нет.

MC>Вот и ответ. MSSQL может припахать индексы при or. Возможно, так могут не все базы, и в этом была суть вопроса. Или от Вас хотели услышать, что в общем и целом сложные функции в условии джойна стоит вручную упрощать.


Где индексы? Там на планах сканирование кластерного индекса == сканирование таблицы.

MC>Или мы действительно не туда копаем.


Это — да.
Re[5]: Вопрос на собеседовании (как надо было ответить?)
От: ilya_ny  
Дата: 17.02.09 02:07
Оценка:
Здравствуйте, _d_m_, Вы писали:


_>>>неверно, это не эквивалентные запросы


___>Запросы (исходный и эквивалентный более правильный):



тоже самое:
пример: таблицы T1 (f1, f2, f3), T2 (f1, f2, f3) одинаковы и имеют след. данные:

F1 F2 F3
1, 0, 0
2, 0, 1



исходный запрос вернет 4 ряда

1, 1
1, 2
2, 1
2, 2


а "эквивалентный более правильный" только два
1, 2
2, 2


таким образом, он эквивалентным не является

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

===


___>
___>select
___>    T1.F1,
___>    T2.F1
___>from
___>    Table1 T1
___>        left join
___>    Table2 T2
___>            on
___>                T1.F2 = T2.F2 or T1.F3 = T2.F3
___>;

___>select
___>    T1F1,
___>    max(T2F1)
___>from
___>    (select
___>        T1.F1 as T1F1,
___>        T2.F1 as T2F1
___>    from
___>        Table1 T1
___>            inner join
___>        Table2 T2
___>                on
___>                    T1.F2 = T2.F2
___>    union all
___>    select
___>        T1.F1,
___>        T2.F1
___>    from
___>        Table1 T1
___>            inner join
___>        Table2 T2
___>                on
___>                    T1.F3 = T2.F3
___>    union all
___>    select
___>        T1.F1,
___>        null
___>    from
___>        Table1 T1
___>    ) as T
___>group by
___>    T1F1
___>; 
___>
Re[6]: Вопрос на собеседовании (как надо было ответить?)
От: _d_m_  
Дата: 17.02.09 03:36
Оценка:
Здравствуйте, ilya_ny, Вы писали:

_>_d_m_ работает над оптимизацией запроса (http://files.rsdn.ru/21534/me.JPG)


_>


Завтрак готовлю ващето
Re[2]: Вопрос на собеседовании (как надо было ответить?)
От: MasterZiv СССР  
Дата: 17.02.09 08:04
Оценка:
_d_m_ пишет:

> select

> T1.F1,
> T2.F1
> from
> Table1 T1
> left join
> Table T2
> on
> T1.F2 = T2.F2
> union all

UNION тут не катит. Тем более — ALL.
Posted via RSDN NNTP Server 2.1 beta
Re[5]: Вопрос на собеседовании (как надо было ответить?)
От: MasterZiv СССР  
Дата: 17.02.09 08:06
Оценка:
MitjaT пишет:

> MC>Чем гадать — лучше бы поглядели план запроса на интересующей Вас базе

> и запостили сюда.

План запроса тут как раз смотреть бессмысленно. частный случай ничего
не доказывает.
Имело бы смысл рассматривать только все возможные планы на всех
возможных раскладах данных.
Posted via RSDN NNTP Server 2.1 beta
Re[2]: Вопрос на собеседовании (как надо было ответить?)
От: Овощ http://www.google.com
Дата: 17.02.09 08:33
Оценка:
Здравствуйте, MasterZiv, Вы писали:

MZ>А переписать надо было бы так:


MZ> select T1.F1, case when T2_1.F1 then T2_1.F1 else T2_2.F1 end as T2F1

MZ> from Table1 T1
MZ> left join Table2 T2_1 on T1.F2=T2.F2
MZ> left join Table2 T2_2 on T1.F3=T2.F3

Запросы не эквивалентны.
Пример данных:
table1: ((1, 1, 1), (1, 1, 1))
table2: ((1, 1, 1), (1, 1, 1))
Выводят разное количество строк.
Re[5]: Вопрос на собеседовании (как надо было ответить?)
От: Овощ http://www.google.com
Дата: 17.02.09 12:26
Оценка:
Здравствуйте, Ромашка, Вы писали:

Р>MasterZiv пишет:

>> тогда
>>
>>> MZ> from Table1 T1
>>> MZ> left join Table2 T2_1 on T1.F2=T2.F2
>>> MZ> left join Table2 T2_2 on T1.F3=T2.F3 and not T1.F2=T2.F2

Р>Давай не будем гадать. Ответ правильный, если не считать некоторых

Р>описок. Я просто напишу правильно:

Р>
Р>select
Р>     T1.F1, IsNull(T2.F1, T3.F1) as F1
Р>from Table1 T1
Р>    left join Table2 T2 on T1.F2 = T2.F2
Р>    left join Table2 T3 on T1.F3 = T3.F3 and not T1.F2 = T3.F2
Р>order by T1.F1
Р>


Что-то у меня опять не сходится.

Пример данных:
table1: (0, 1, 2)
table2: ((1, 1, 1), (2, 2, 2))
Должно вернуть 2 строки.

Где-то опечатка?
Re[6]: Вопрос на собеседовании (как надо было ответить?)
От: ilya_ny  
Дата: 17.02.09 13:03
Оценка:
Здравствуйте, Овощ, Вы писали:


Р>>
Р>>select
Р>>     T1.F1, IsNull(T2.F1, T3.F1) as F1
Р>>from Table1 T1
Р>>    left join Table2 T2 on T1.F2 = T2.F2
Р>>    left join Table2 T3 on T1.F3 = T3.F3 and not T1.F2 = T3.F2
Р>>order by T1.F1
Р>>


О>Что-то у меня опять не сходится.


О>Пример данных:

О>table1: (0, 1, 2)
О>table2: ((1, 1, 1), (2, 2, 2))
О>Должно вернуть 2 строки.

О>Где-то опечатка?


ну так какой тогда правилный ответ?
Re: Вопрос на собеседовании (как надо было ответить?)
От: octo47 Россия  
Дата: 17.02.09 13:42
Оценка:
Здравствуйте, MitjaT, Вы писали:

MT>Здравствуйте!


MT>Как вам такой письменный вопрос на собеседовании?

MT>Как правильно на него ответить?

MT>

MT>Чем плох такой запрос? Как можно его оптимизировать?

MT>select T1.F1, T2.F1
MT>from Table1 T1
MT>left join Table2 T2 on T1.F2=T2.F2 or T1.F3=T2.F3


Зависит от БД, для PostgreSQL наиболее быстрый из всех 3-х предложенных.
Для Oracle чуть чуть медленнее третьего (см листинг pgsql, для оракла не привожу).


drop table if exists table1;
drop table if exists table2;
CREATE TABLE table1(
    F1 serial primary key,
    F2 integer not null,
    F3 integer not null
);
CREATE TABLE table2(
    F1 serial primary key,
    F2 integer not null,
    F3 integer not null
);
create index ix_table1_f2 on table1(f2);
create index ix_table1_f3 on table1(f3);
create index ix_table2_f2 on table2(f2);
create index ix_table2_f3 on table2(f3);

-- Создаем записи которые не будут попадать под условие запроса
insert into table2(f2, f3) select f as f2, f+100000 as f3 from generate_series(0, 90000-1, 1) f;
insert into table1(f2, f3) select f2+200000, f3+300000 from table2 order by f1 limit 2000;
-- Создаем записи которые будут попадать под условие запроса F2 = F2
insert into table1(f2, f3) select f as f2, f+100000 as f3 from generate_series(90000, 92000-1, 1) f;
insert into table2(f2, f3) select f as f2, f+200000 as f3 from generate_series(90000, 92000-1, 1) f;
-- Создаем записи которые будут попадать под условие запроса F3 = F3
insert into table1(f2, f3) select f+100000 as f2, f as f3 from generate_series(92000, 94000-1, 1) f;
insert into table2(f2, f3) select f+200000 as f2, f as f3 from generate_series(92000, 94000-1, 1) f;
-- Создаем записи которые будут попадать под условие запроса F2 = F2 = F3 = F3
insert into table1(f2, f3) select f as f2, f as f3 from generate_series(94000, 96000-1, 1) f;
insert into table2(f2, f3) select f as f2, f as f3 from generate_series(94000, 96000-1, 1) f;
analyse;
explain analyse
select     T1.F1, T2.F1
    from Table1 T1
    left join Table2 T2
    on  T1.F2 = T2.F2
        or T1.F3 = T2.F3 ;

explain analyse
select  T1F1, max(T2F1)
    from
        (select     T1.F1 as T1F1, T2.F1 as T2F1
                from Table1 T1
                inner join Table2 T2
                on  T1.F2 = T2.F2
            union all
            select     T1.F1, T2.F1
                from Table1 T1
                inner join Table2 T2
                on  T1.F3 = T2.F3
            union all
            select     T1.F1, null
                from Table1 T1
        ) as T
    group by T1F1 ;

cluster table1 using table1_pkey;
cluster table2 using table2_pkey;
explain analyse 
select  T1.F1, coalesce(T2_1.F1, T2_2.F1) as T2F1
    from Table1 T1
        left join Table2 T2_1 on  T1.F2=T2_1.F2
        left join Table2 T2_2 on (T1.F3=T2_2.F3 and not T1.F2=T2_2.F2);
select count(*) from table1;
select count(*) from table2;



                                                             QUERY PLAN                                                             
------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop Left Join  (cost=0.75..38484.32 rows=16000 width=8) (actual time=0.079..100.528 rows=8000 loops=1)
   Join Filter: ((t1.f2 = t2.f2) OR (t1.f3 = t2.f3))
   ->  Seq Scan on table1 t1  (cost=0.00..120.00 rows=8000 width=12) (actual time=0.007..4.181 rows=8000 loops=1)
   ->  Bitmap Heap Scan on table2 t2  (cost=0.75..4.77 rows=2 width=12) (actual time=0.008..0.009 rows=1 loops=8000)
         Recheck Cond: ((t1.f2 = t2.f2) OR (t1.f3 = t2.f3))
         ->  BitmapOr  (cost=0.75..0.75 rows=2 width=0) (actual time=0.007..0.007 rows=0 loops=8000)
               ->  Bitmap Index Scan on ix_table2_f2  (cost=0.00..0.37 rows=1 width=0) (actual time=0.003..0.003 rows=0 loops=8000)
                     Index Cond: (t1.f2 = t2.f2)
               ->  Bitmap Index Scan on ix_table2_f3  (cost=0.00..0.37 rows=1 width=0) (actual time=0.003..0.003 rows=0 loops=8000)
                     Index Cond: (t1.f3 = t2.f3)
 Total runtime: 103.928 ms
(11 rows)

                                                            QUERY PLAN                                                             
-----------------------------------------------------------------------------------------------------------------------------------
 HashAggregate  (cost=6582.00..6584.50 rows=200 width=8) (actual time=255.314..260.239 rows=8000 loops=1)
   ->  Append  (cost=220.00..6222.00 rows=24000 width=8) (actual time=98.856..242.948 rows=16000 loops=1)
         ->  Hash Join  (cost=220.00..2931.00 rows=8000 width=8) (actual time=98.855..107.491 rows=4000 loops=1)
               Hash Cond: (t2.f2 = t1.f2)
               ->  Seq Scan on table2 t2  (cost=0.00..1431.00 rows=96000 width=8) (actual time=0.006..40.053 rows=96000 loops=1)
               ->  Hash  (cost=120.00..120.00 rows=8000 width=8) (actual time=9.228..9.228 rows=8000 loops=1)
                     ->  Seq Scan on table1 t1  (cost=0.00..120.00 rows=8000 width=8) (actual time=0.007..4.450 rows=8000 loops=1)
         ->  Hash Join  (cost=220.00..2931.00 rows=8000 width=8) (actual time=105.900..112.798 rows=4000 loops=1)
               Hash Cond: (t2.f3 = t1.f3)
               ->  Seq Scan on table2 t2  (cost=0.00..1431.00 rows=96000 width=8) (actual time=0.007..42.931 rows=96000 loops=1)
               ->  Hash  (cost=120.00..120.00 rows=8000 width=8) (actual time=9.395..9.395 rows=8000 loops=1)
                     ->  Seq Scan on table1 t1  (cost=0.00..120.00 rows=8000 width=8) (actual time=0.007..4.426 rows=8000 loops=1)
         ->  Subquery Scan "*SELECT* 3"  (cost=0.00..200.00 rows=8000 width=4) (actual time=0.009..11.795 rows=8000 loops=1)
               ->  Seq Scan on table1 t1  (cost=0.00..120.00 rows=8000 width=4) (actual time=0.007..4.657 rows=8000 loops=1)
 Total runtime: 263.221 ms
(15 rows)

                                                                    QUERY PLAN                                                                    
--------------------------------------------------------------------------------------------------------------------------------------------------
 Hash Left Join  (cost=5764.22..7055.29 rows=8000 width=12) (actual time=215.136..266.488 rows=8000 loops=1)
   Hash Cond: (t1.f3 = t2_2.f3)
   Join Filter: (t1.f2 <> t2_2.f2)
   ->  Merge Left Join  (cost=2711.22..3320.29 rows=8000 width=16) (actual time=95.601..114.328 rows=8000 loops=1)
         Merge Cond: (t1.f2 = t2_1.f2)
         ->  Index Scan using ix_table1_f2 on table1 t1  (cost=0.00..346.96 rows=8000 width=12) (actual time=0.054..5.345 rows=8000 loops=1)
         ->  Index Scan using ix_table2_f2 on table2 t2_1  (cost=0.00..2766.45 rows=96000 width=8) (actual time=0.021..58.040 rows=94001 loops=1)
   ->  Hash  (cost=1431.00..1431.00 rows=96000 width=12) (actual time=119.398..119.398 rows=96000 loops=1)
         ->  Seq Scan on table2 t2_2  (cost=0.00..1431.00 rows=96000 width=12) (actual time=0.009..53.147 rows=96000 loops=1)
 Total runtime: 269.338 ms
(10 rows)

 count 
-------
  8000
(1 запись)

 count 
-------
 96000
(1 запись)


Вариант с принудительным использованием индексов во 2-м запросе, что дает что-то похожее на то, что делает mssql.
HashAggregate  (cost=100008101.30..100008103.80 rows=200 width=8) (actual time=264.442..268.939 rows=8000 loops=1)
  ->  Append  (cost=2724.91..100007741.30 rows=24000 width=8) (actual time=101.632..252.214 rows=16000 loops=1)
        ->  Merge Join  (cost=2724.91..3385.54 rows=8000 width=8) (actual time=101.630..117.700 rows=4000 loops=1)
              Merge Cond: (t1.f2 = t2.f2)
              ->  Index Scan using ix_table1_f2 on table1 t1  (cost=0.00..397.22 rows=8000 width=8) (actual time=0.020..4.918 rows=8000 loops=1)
              ->  Index Scan using ix_table2_f2 on table2 t2  (cost=0.00..2782.58 rows=96000 width=8) (actual time=0.017..59.696 rows=94001 loops=1)
        ->  Merge Join  (cost=0.28..3995.76 rows=8000 width=8) (actual time=0.025..112.698 rows=4000 loops=1)
              Merge Cond: (t1.f3 = t2.f3)
              ->  Index Scan using ix_table1_f3 on table1 t1  (cost=0.00..352.89 rows=8000 width=8) (actual time=0.011..3.831 rows=6001 loops=1)
              ->  Index Scan using ix_table2_f3 on table2 t2  (cost=0.00..3396.79 rows=96000 width=8) (actual time=0.010..57.608 rows=96000 loops=1)
        ->  Subquery Scan "*SELECT* 3"  (cost=100000000.00..100000200.00 rows=8000 width=4) (actual time=0.011..11.009 rows=8000 loops=1)
              ->  Seq Scan on table1 t1  (cost=100000000.00..100000120.00 rows=8000 width=4) (actual time=0.009..4.571 rows=8000 loops=1)
Total runtime: 271.772 ms
Re[6]: Вопрос на собеседовании (как надо было ответить?)
От: Ромашка Украина  
Дата: 17.02.09 14:04
Оценка:
Овощ пишет:
> Где-то опечатка?

Да нет, это я где-то лопухнулся.
Сча найдем правильный ответ.
Posted via RSDN NNTP Server 2.1 beta


Всё, что нас не убивает, ещё горько об этом пожалеет.
Re[3]: Вопрос на собеседовании (как надо было ответить?)
От: MasterZiv СССР  
Дата: 17.02.09 15:20
Оценка:
Ромашка пишет:

> Небольшая ремарка:

> Не поймут и не переформулируют. JOIN по OR не оставляет оптимизатору
> шансов — будет использован только NESTED LOOP JOIN, а ему индексы пофигу.

1) вы хотите сказать, что индексы неприменимы при NESTED LOOP JOIN в принципе ?
Нет, это не так.

2) почему вы думаете, что все на свете оптимизаторы не произведут
соотвтствующее эквивалентное преобразование автоматом ?
Это можно утверждать только доказав, что такого преобразования
не существует в принципе.

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

Это NESTED LOOP JOIN T1 и двух курсоров по Table2, с
позиционированием по разным условиям и индексам.

T1
NESTED LOOP JOIN
(Table2 T2_1 on T1.F2=T2.F2
а если в T2_1 записи не нашлось, то
Table2 T2_2 on T1.F3=T2.F3 )
Posted via RSDN NNTP Server 2.1 beta
Re[7]: Вопрос на собеседовании (как надо было ответить?)
От: Ромашка Украина  
Дата: 17.02.09 15:29
Оценка:
ilya_ny пишет:
> ну так какой тогда правилный ответ?

Не претендуя на правильность. Если уж не удается по глупости душевной
уломать сервер мультиплицировать правильно количество строк (пример
http://rsdn.ru/forum/message/3294469.aspx
Автор: Овощ
Дата: 17.02.09
), попробуем просто уменьшить
количество loop-ов. Для http://rsdn.ru/forum/message/3294167.aspx
Автор: _d_m_
Дата: 17.02.09
дает
приличный прирост производительности.

select T1.F1, T2.F1
from Table1 T1
    left join (select *
                from Table2
                where F2 in (select F2 from Table1)
                or F3 in (select F3 from Table1)
        )T2 on T1.F2=T2.F2 or T1.F3=T2.F3
Posted via RSDN NNTP Server 2.1 beta


Всё, что нас не убивает, ещё горько об этом пожалеет.
Re[4]: Вопрос на собеседовании (как надо было ответить?)
От: Ромашка Украина  
Дата: 17.02.09 15:42
Оценка:
MasterZiv пишет:
> 1) вы хотите сказать, что индексы неприменимы при NESTED LOOP JOIN в
> принципе ?
> Нет, это не так.

Да, это не так. MasterZiv, вы прекрасно понимаете, что я хочу сказать.
Не нужно играть со словами.

> 2) почему вы думаете, что все на свете оптимизаторы не произведут

> соотвтствующее эквивалентное преобразование автоматом ?
> Это можно утверждать только доказав, что такого преобразования
> не существует в принципе.

Или что они неэффективны в принципе. В принципе, я с вами согласен.

> Но в данном случае есть просто тупо алгоритм выполнения запроса,

> который невыразим в SQL и будет использовать индексы.
> Это NESTED LOOP JOIN T1 и двух курсоров по Table2, с
> позиционированием по разным условиям и индексам.

Ужас, вы не находите?

Меня другое интересует: почему http://rsdn.ru/forum/message/3295340.aspx
Автор: Ромашка
Дата: 17.02.09

работает намного быстрее?
Posted via RSDN NNTP Server 2.1 beta


Всё, что нас не убивает, ещё горько об этом пожалеет.
Re[4]: Вопрос на собеседовании (как надо было ответить?)
От: Ромашка Украина  
Дата: 17.02.09 15:44
Оценка:
seregaa пишет:
> да вобщем то несложно разбить конкретно это условие объединения на 4
> _независимых_ подусловия, каждое из которых можно выполнить по
> отдельности (а корректность таких преобразований можно проверить
> математически):

Класс, поздравляю. Это, похоже, уже правильный ответ.
Posted via RSDN NNTP Server 2.1 beta


Всё, что нас не убивает, ещё горько об этом пожалеет.
Re[5]: Вопрос на собеседовании (как надо было ответить?)
От: MasterZiv СССР  
Дата: 17.02.09 16:57
Оценка:
Ромашка пишет:

> Да, это не так. MasterZiv, вы прекрасно понимаете, что я хочу сказать.

> Не нужно играть со словами.

Не, я правда не понял.

>> Но в данном случае есть просто тупо алгоритм выполнения запроса,

>> который невыразим в SQL и будет использовать индексы.
>> Это NESTED LOOP JOIN T1 и двух курсоров по Table2, с
>> позиционированием по разным условиям и индексам.
>
> Ужас, вы не находите?

Что ужас ? Никакого ужаса.

>

> Меня другое интересует: почему http://rsdn.ru/forum/message/3295340.aspx
Автор: Ромашка
Дата: 17.02.09

> работает намного быстрее?

Не понимаю, почему вы решили, что оно быстрее.

Я вот не могу сказать ни того, ни другого.

ладно.
Posted via RSDN NNTP Server 2.1 beta
Re[4]: Вопрос на собеседовании (как надо было ответить?)
От: seregaa Ниоткуда http://blogtani.ru
Дата: 17.02.09 17:18
Оценка:
Здравствуйте, MasterZiv, Вы писали:

MZ>Но в данном случае есть просто тупо алгоритм выполнения запроса,

MZ>который невыразим в SQL и будет использовать индексы.

MZ>Это NESTED LOOP JOIN T1 и двух курсоров по Table2, с

MZ>позиционированием по разным условиям и индексам.

MZ>T1

MZ>NESTED LOOP JOIN
MZ> (Table2 T2_1 on T1.F2=T2.F2
MZ> а если в T2_1 записи не нашлось, то
MZ> Table2 T2_2 on T1.F3=T2.F3 )

Можно уговорить mssql использовать почти такой алгоритм с помощью табличной функции:
create function dbo.getByF2F3 (@f2 int, @f3 int)
returns @results table 
(
    F1 int
)
as
begin
    insert @results select F1 from Table2 where F2 = @f2 or F3 = @f3
    return
end;
GO

select 
    T1.F1, T2.F1
from
    Table1 T1
    outer apply dbo.getByF2F3(T1.F2, T1.F3) T2


Время выполнения ~15сек, план:
Мобильная версия сайта RSDN — http://rsdn.org/forum/rsdn/6938747
Автор: sergeya
Дата: 19.10.17
Re: Вопрос на собеседовании (как надо было ответить?)
От: tnikolai  
Дата: 20.02.09 13:41
Оценка:
Здравствуйте, MitjaT, Вы писали:

MT>Здравствуйте!


MT>Как вам такой письменный вопрос на собеседовании?

MT>Как правильно на него ответить?

MT>

MT>Чем плох такой запрос? Как можно его оптимизировать?

MT>select T1.F1, T2.F1
MT>from Table1 T1
MT>left join Table2 T2 on T1.F2=T2.F2 or T1.F3=T2.F3


а так

select T1.F1, T2.F1
from Table1 T1
left join Table2 T2 on (not (T1.F2!=T2.F2 AND T1.F3!=T2.F3))
Re[2]: Вопрос на собеседовании (как надо было ответить?)
От: MasterZiv СССР  
Дата: 20.02.09 19:50
Оценка:
tnikolai пишет:

> select T1.F1, T2.F1

> from Table1 T1
> left join Table2 T2 on (not (T1.F2!=T2.F2 AND T1.F3!=T2.F3))

Одна фигня.
От применения правила деМоргана таблица истинности этого
булевого выражения не меняется.

Т.е., если кто не правильно понял — и то, и это одинаково
сложно для оптимизатора.
Posted via RSDN NNTP Server 2.1 beta
Re[6]: Вопрос на собеседовании (как надо было ответить?)
От: avpavlov  
Дата: 24.02.09 19:53
Оценка:
from Table1 T1
left join Table2 T2_1 on T1.F2=T2.F2
left join Table2 T2_2 on T1.F3=T2.F3 and T2.F2 is null
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.