Здравствуйте, Ромашка, Вы писали:
Р>С увлечением наблюдал за дискуссией. Рад за 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
wherenot exists (select * from Table2 T2 where T1.F2 = T2.F2 or T1.F3 = T2.F3)
здесь тоже возможны сканы таблиц, но по крайней мере без NL-ов. Время выполнения запроса под mssql ~1 сек. Для таблиц созданы кластерные индексы по F1 и простые не составные индексы по F2 и F3. План:
имхо здесь основная сложность в оценке время выполнения запроса и следовательно высок риск промахнуться с выбором оптимального варианта.
Овощ пишет:
> 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]: Вопрос на собеседовании (как надо было ответить?)
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]: Вопрос на собеседовании (как надо было ответить?)
С увлечением наблюдал за дискуссией. Рад за MasterZiv и его правильный
ответ (ниже по ветке).
> плох тем, что JOIN по OR может быть плохо воспринят > оптимизатором и не будет использован индекс при выполнении JOIN-а. > Но это — только один из возможных вариантов > развития событий. Думаю, многие оптимизаторы поймут эту > ситуацию правильно и сами сделают правильную переформулировку запроса.
Небольшая ремарка:
Не поймут и не переформулируют. JOIN по OR не оставляет оптимизатору
шансов — будет использован только NESTED LOOP JOIN, а ему индексы пофигу.
Posted via RSDN NNTP Server 2.1 beta
Всё, что нас не убивает, ещё горько об этом пожалеет.
Re[4]: Вопрос на собеседовании (как надо было ответить?)
Здравствуйте, 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 = F2set @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 = F3set @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 = F3set @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]: Вопрос на собеседовании (как надо было ответить?)
Здравствуйте, _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]: Вопрос на собеседовании (как надо было ответить?)
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: Вопрос на собеседовании (как надо было ответить?)
Здравствуйте, 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, Вы писали: MT>Надо в этом случае дополнительно ввести условие, что "сведет на нет" такую оптимизацию.
Сведет ли? Насколько я понимаю, or может помешать использовать при джойне индексы, что (в случае больших исходных таблиц и небольшого предполагаемого количества строк в результате) значительно сильнее ударит по перфомансу, чем необходимость выбрать distinct из результата юниона.
Чем гадать — лучше бы поглядели план запроса на интересующей Вас базе и запостили сюда.
Re[4]: Вопрос на собеседовании (как надо было ответить?)
Здравствуйте, MitjaT, Вы писали: MT>Запросы идентичны.
Вот и ответ. MSSQL может припахать индексы при or. Возможно, так могут не все базы, и в этом была суть вопроса. Или от Вас хотели услышать, что в общем и целом сложные функции в условии джойна стоит вручную упрощать.
Или мы действительно не туда копаем.
Re[2]: Вопрос на собеседовании (как надо было ответить?)
Здравствуйте, MitjaT, Вы писали:
MT>Как вам такой письменный вопрос на собеседовании?
Смотря на какую позицию, может конкретно разработчик баз данных и должен знать, остальные — сомневаюсь.
MT>Чем плох такой запрос?
Хз.
MT>Как можно его оптимизировать?
Хз.
В общем лично я бы на вопрос не ответил, если вам интересно такое мнение со стороны.
Re[3]: Вопрос на собеседовании (как надо было ответить?)
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, _d_m_, Вы писали:
___>>or в джойне.
N>Неужто оптимизатор сам не просекает?
ИИ?
Запрос на самом деле уродский — этакий сферический конь в вакууме, такой в реальной жизни не встречался мне никогда. Такую структуру данных даже не придет в голову создать начинающему разработчику с особо извращенной фантазией.
Re[5]: Вопрос на собеседовании (как надо было ответить?)
Здравствуйте, MitjaT, Вы писали:
MT>Здравствуйте, Mr.Cat, Вы писали:
MC>>Чем гадать — лучше бы поглядели план запроса на интересующей Вас базе и запостили сюда.
MT>Пожалуйста: MT> MT>
MT>Запросы идентичны.
Неверно.
Вот первых: Чтобы сравнить запросы их надо ставить в одном батче.
Во вторых: Что с индексами? Там кроме кластерного суррогатного первичного ключа, по моему больше нихрена нет.
Re[6]: Вопрос на собеседовании (как надо было ответить?)
Здравствуйте, Mr.Cat, Вы писали:
MC>Здравствуйте, MitjaT, Вы писали: MT>>Запросы идентичны.
Нет.
MC>Вот и ответ. MSSQL может припахать индексы при or. Возможно, так могут не все базы, и в этом была суть вопроса. Или от Вас хотели услышать, что в общем и целом сложные функции в условии джойна стоит вручную упрощать.
Где индексы? Там на планах сканирование кластерного индекса == сканирование таблицы.
MC>Или мы действительно не туда копаем.
Это — да.
Re[5]: Вопрос на собеседовании (как надо было ответить?)
MitjaT пишет:
> MC>Чем гадать — лучше бы поглядели план запроса на интересующей Вас базе > и запостили сюда.
План запроса тут как раз смотреть бессмысленно. частный случай ничего
не доказывает.
Имело бы смысл рассматривать только все возможные планы на всех
возможных раскладах данных.
Posted via RSDN NNTP Server 2.1 beta
Re[2]: Вопрос на собеседовании (как надо было ответить?)
Здравствуйте, 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]: Вопрос на собеседовании (как надо было ответить?)
Здравствуйте, Ромашка, Вы писали:
Р>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]: Вопрос на собеседовании (как надо было ответить?)
Р>>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: Вопрос на собеседовании (как надо было ответить?)
Здравствуйте, 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 = F2insert 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 = F3insert 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 = F3insert 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;
Ромашка пишет:
> Небольшая ремарка: > Не поймут и не переформулируют. 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]: Вопрос на собеседовании (как надо было ответить?)
ilya_ny пишет: > ну так какой тогда правилный ответ?
Не претендуя на правильность. Если уж не удается по глупости душевной
уломать сервер мультиплицировать правильно количество строк (пример http://rsdn.ru/forum/message/3294469.aspx
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]: Вопрос на собеседовании (как надо было ответить?)
MasterZiv пишет: > 1) вы хотите сказать, что индексы неприменимы при NESTED LOOP JOIN в > принципе ? > Нет, это не так.
Да, это не так. MasterZiv, вы прекрасно понимаете, что я хочу сказать.
Не нужно играть со словами.
> 2) почему вы думаете, что все на свете оптимизаторы не произведут > соотвтствующее эквивалентное преобразование автоматом ? > Это можно утверждать только доказав, что такого преобразования > не существует в принципе.
Или что они неэффективны в принципе. В принципе, я с вами согласен.
> Но в данном случае есть просто тупо алгоритм выполнения запроса, > который невыразим в SQL и будет использовать индексы. > Это NESTED LOOP JOIN T1 и двух курсоров по Table2, с > позиционированием по разным условиям и индексам.
seregaa пишет: > да вобщем то несложно разбить конкретно это условие объединения на 4 > _независимых_ подусловия, каждое из которых можно выполнить по > отдельности (а корректность таких преобразований можно проверить > математически):
Класс, поздравляю. Это, похоже, уже правильный ответ.
Posted via RSDN NNTP Server 2.1 beta
Всё, что нас не убивает, ещё горько об этом пожалеет.
Re[5]: Вопрос на собеседовании (как надо было ответить?)
Ромашка пишет:
> Да, это не так. MasterZiv, вы прекрасно понимаете, что я хочу сказать. > Не нужно играть со словами.
Не, я правда не понял.
>> Но в данном случае есть просто тупо алгоритм выполнения запроса, >> который невыразим в SQL и будет использовать индексы. >> Это NESTED LOOP JOIN T1 и двух курсоров по Table2, с >> позиционированием по разным условиям и индексам. > > Ужас, вы не находите?
Здравствуйте, 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