Задачка Эйнштейна и запрос на MSSQL vs. FB

romaklimenko

Всем привет!

Вопрос к гуру и просто умным людям.

Есть общеизвестная загадка Эйнштейна.
Около двух лет назад я развлекался ее решением на MSSQL с помощью запроса. Впрочем, моя попытка не оригинальна. Здесь товарищи сделали то же самое. Итак, у меня запрос отработал секунд за 15.
А на днях поднялась эта тема и я поднял старые файлы и запустил тот же запрос на Firebird 2.0.012169 Beta 2. Полная лажа - больше часа. Не дотерпел и ушел домой. MSSQL у меня сейчас нет. План подсмотреть неоткуда. Отдолжил у соседа комп с MSDE - запустил из Access по ODBC - 10 сек.

Я понимаю, что декартово произведение и все такое, но мне в этой ситуации интересно следующее:
1) можно ли переписать запрос красивше?
2) почему FB так тормозит? Это только в бете или вообще?
3) как сделать то же самое, но без тормозов?
4) почему MSSQL не спотыкаетя о декартово произведение?

Ниже привожу свои скрипты. Работают и под FB, и под MSSQL.

CREATE TABLE ANIMAL (
ANIMAL VARCHAR(10) NOT NULL
);

CREATE TABLE COLOR (
COLOR VARCHAR(10) NOT NULL
);

CREATE TABLE DRINK (
DRINK VARCHAR(10) NOT NULL
);

CREATE TABLE NATION (
NATION VARCHAR(10) NOT NULL
);

CREATE TABLE SMOKE (
SMOKE VARCHAR(10) NOT NULL
);

INSERT INTO ANIMAL (ANIMAL) VALUES ('КОШКА');
INSERT INTO ANIMAL (ANIMAL) VALUES ('РЫБА');
INSERT INTO ANIMAL (ANIMAL) VALUES ('СОБАКА');
INSERT INTO ANIMAL (ANIMAL) VALUES ('ЛОШАДЬ');
INSERT INTO ANIMAL (ANIMAL) VALUES ('ПТИЦА');

COMMIT WORK;

INSERT INTO COLOR (COLOR) VALUES ('БЕЛЫЙ');
INSERT INTO COLOR (COLOR) VALUES ('ЖЕЛТЫЙ');
INSERT INTO COLOR (COLOR) VALUES ('КРАСНЫЙ');
INSERT INTO COLOR (COLOR) VALUES ('ГОЛУБОЙ');
INSERT INTO COLOR (COLOR) VALUES ('ЗЕЛЕНЫЙ');

COMMIT WORK;

INSERT INTO DRINK (DRINK) VALUES ('КОФЕ');
INSERT INTO DRINK (DRINK) VALUES ('МОЛОКО');
INSERT INTO DRINK (DRINK) VALUES ('ВОДА');
INSERT INTO DRINK (DRINK) VALUES ('ПИВО');
INSERT INTO DRINK (DRINK) VALUES ('ЧАЙ');

COMMIT WORK;

INSERT INTO NATION (NATION) VALUES ('АНГЛИЧАНИН');
INSERT INTO NATION (NATION) VALUES ('ШВЕД');
INSERT INTO NATION (NATION) VALUES ('НЕМЕЦ');
INSERT INTO NATION (NATION) VALUES ('ДАТЧАНИН');
INSERT INTO NATION (NATION) VALUES ('НОРВЕЖЕЦ');

COMMIT WORK;

INSERT INTO SMOKE (SMOKE) VALUES ('PALL MALL');
INSERT INTO SMOKE (SMOKE) VALUES ('MARLBORO');
INSERT INTO SMOKE (SMOKE) VALUES ('ROTHMANS');
INSERT INTO SMOKE (SMOKE) VALUES ('WINFIELD');
INSERT INTO SMOKE (SMOKE) VALUES ('DUNHILL');

COMMIT WORK;

ALTER TABLE ANIMAL ADD CONSTRAINT FK_ANIMAL PRIMARY KEY (ANIMAL);
ALTER TABLE COLOR ADD CONSTRAINT FK_COLOR PRIMARY KEY (COLOR);
ALTER TABLE DRINK ADD CONSTRAINT FK_DRINK PRIMARY KEY (DRINK);
ALTER TABLE NATION ADD CONSTRAINT FK_NATION PRIMARY KEY (NATION);
ALTER TABLE SMOKE ADD CONSTRAINT FK_SMOKE PRIMARY KEY (SMOKE);

Мой запрос:

select
A1.ANIMAL AS H1ANIMAL,
D1.DRINK AS H1DRINK,
N1.NATION AS H1NATION,
S1.SMOKE AS H1SMOKE,
C1.COLOR as H1COLOR,

A2.ANIMAL AS H2ANIMAL,
D2.DRINK AS H2DRINK,
N2.NATION AS H2NATION,
S2.SMOKE AS H2SMOKE,
C2.COLOR as H2COLOR,

A3.ANIMAL AS H3ANIMAL,
D3.DRINK AS H3DRINK,
N3.NATION AS H3NATION,
S3.SMOKE AS H3SMOKE,
C3.COLOR as H3COLOR,

A4.ANIMAL AS H4ANIMAL,
D4.DRINK AS H4DRINK,
N4.NATION AS H4NATION,
S4.SMOKE AS H4SMOKE,
C4.COLOR as H4COLOR,

A5.ANIMAL AS H5ANIMAL,
D5.DRINK AS H5DRINK,
N5.NATION AS H5NATION,
S5.SMOKE AS H5SMOKE,
C5.COLOR as H5COLOR

from ANIMAL A1,
DRINK D1,
NATION N1,
SMOKE S1,
COLOR C1,

ANIMAL A2,
DRINK D2,
NATION N2,
SMOKE S2,
COLOR C2,

ANIMAL A3,
DRINK D3,
NATION N3,
SMOKE S3,
COLOR C3,

ANIMAL A4,
DRINK D4,
NATION N4,
SMOKE S4,
COLOR C4,

ANIMAL A5,
DRINK D5,
NATION N5,
SMOKE S5,
COLOR C5
where
A1.ANIMAL <> A2.ANIMAL and
A1.ANIMAL <> A3.ANIMAL and
A1.ANIMAL <> A4.ANIMAL and
A1.ANIMAL <> A5.ANIMAL and
A2.ANIMAL <> A3.ANIMAL and
A2.ANIMAL <> A4.ANIMAL and
A2.ANIMAL <> A5.ANIMAL and
A3.ANIMAL <> A4.ANIMAL and
A3.ANIMAL <> A5.ANIMAL and
A4.ANIMAL <> A5.ANIMAL
and
C1.COLOR <> C2.COLOR and
C1.COLOR <> C3.COLOR and
C1.COLOR <> C4.COLOR and
C1.COLOR <> C5.COLOR and
C2.COLOR <> C3.COLOR and
C2.COLOR <> C4.COLOR and
C2.COLOR <> C5.COLOR and
C3.COLOR <> C4.COLOR and
C3.COLOR <> C5.COLOR and
C4.COLOR <> C5.COLOR
and
D1.DRINK <> D2.DRINK and
D1.DRINK <> D3.DRINK and
D1.DRINK <> D4.DRINK and
D1.DRINK <> D5.DRINK and
D2.DRINK <> D3.DRINK and
D2.DRINK <> D4.DRINK and
D2.DRINK <> D5.DRINK and
D3.DRINK <> D4.DRINK and
D3.DRINK <> D5.DRINK and
D4.DRINK <> D5.DRINK
and
N1.NATION <> N2.NATION and
N1.NATION <> N3.NATION and
N1.NATION <> N4.NATION and
N1.NATION <> N5.NATION and
N2.NATION <> N3.NATION and
N2.NATION <> N4.NATION and
N2.NATION <> N5.NATION and
N3.NATION <> N4.NATION and
N3.NATION <> N5.NATION and
N4.NATION <> N5.NATION
and
S1.SMOKE <> S2.SMOKE and
S1.SMOKE <> S3.SMOKE and
S1.SMOKE <> S4.SMOKE and
S1.SMOKE <> S5.SMOKE and
S2.SMOKE <> S3.SMOKE and
S2.SMOKE <> S4.SMOKE and
S2.SMOKE <> S5.SMOKE and
S3.SMOKE <> S4.SMOKE and
S3.SMOKE <> S5.SMOKE and
S4.SMOKE <> S5.SMOKE
and
-- 1
((N1.NATION = 'АНГЛИЧАНИН' and C1.COLOR = 'КРАСНЫЙ') or
(N2.NATION = 'АНГЛИЧАНИН' and C2.COLOR = 'КРАСНЫЙ') or
(N3.NATION = 'АНГЛИЧАНИН' and C3.COLOR = 'КРАСНЫЙ') or
(N4.NATION = 'АНГЛИЧАНИН' and C4.COLOR = 'КРАСНЫЙ') or
(N5.NATION = 'АНГЛИЧАНИН' and C5.COLOR = 'КРАСНЫЙ'))
and
-- 2
((N1.NATION = 'ШВЕД' and A1.ANIMAL = 'СОБАКА') or
(N2.NATION = 'ШВЕД' and A2.ANIMAL = 'СОБАКА') or
(N3.NATION = 'ШВЕД' and A3.ANIMAL = 'СОБАКА') or
(N4.NATION = 'ШВЕД' and A4.ANIMAL = 'СОБАКА') or
(N5.NATION = 'ШВЕД' and A5.ANIMAL = 'СОБАКА'))
and
-- 3
((N1.NATION = 'ДАТЧАНИН' and D1.DRINK = 'ЧАЙ') or
(N2.NATION = 'ДАТЧАНИН' and D2.DRINK = 'ЧАЙ') or
(N3.NATION = 'ДАТЧАНИН' and D3.DRINK = 'ЧАЙ') or
(N4.NATION = 'ДАТЧАНИН' and D4.DRINK = 'ЧАЙ') or
(N5.NATION = 'ДАТЧАНИН' and D5.DRINK = 'ЧАЙ'))
and
-- 4
((C1.COLOR = 'ЗЕЛЕНЫЙ' and C2.COLOR = 'БЕЛЫЙ') or
(C2.COLOR = 'ЗЕЛЕНЫЙ' and C3.COLOR = 'БЕЛЫЙ') or
(C3.COLOR = 'ЗЕЛЕНЫЙ' and C4.COLOR = 'БЕЛЫЙ') or
(C4.COLOR = 'ЗЕЛЕНЫЙ' and C5.COLOR = 'БЕЛЫЙ'))
and
-- 5
((C1.COLOR = 'ЗЕЛЕНЫЙ' and D1.DRINK = 'КОФЕ') or
(C2.COLOR = 'ЗЕЛЕНЫЙ' and D2.DRINK = 'КОФЕ') or
(C3.COLOR = 'ЗЕЛЕНЫЙ' and D3.DRINK = 'КОФЕ') or
(C4.COLOR = 'ЗЕЛЕНЫЙ' and D4.DRINK = 'КОФЕ') or
(C5.COLOR = 'ЗЕЛЕНЫЙ' and D5.DRINK = 'КОФЕ'))
and
-- 6
((S1.SMOKE = 'PALL MALL' and A1.ANIMAL = 'ПТИЦА') or
(S2.SMOKE = 'PALL MALL' and A2.ANIMAL = 'ПТИЦА') or
(S3.SMOKE = 'PALL MALL' and A3.ANIMAL = 'ПТИЦА') or
(S4.SMOKE = 'PALL MALL' and A4.ANIMAL = 'ПТИЦА') or
(S5.SMOKE = 'PALL MALL' and A5.ANIMAL = 'ПТИЦА'))
and
-- 7
(D3.DRINK = 'МОЛОКО')
and
-- 8
((S1.SMOKE = 'DUNHILL' and C1.COLOR = 'ЖЕЛТЫЙ') or
(S2.SMOKE = 'DUNHILL' and C2.COLOR = 'ЖЕЛТЫЙ') or
(S3.SMOKE = 'DUNHILL' and C3.COLOR = 'ЖЕЛТЫЙ') or
(S4.SMOKE = 'DUNHILL' and C4.COLOR = 'ЖЕЛТЫЙ') or
(S5.SMOKE = 'DUNHILL' and C5.COLOR = 'ЖЕЛТЫЙ'))
and
-- 9
(N1.NATION = 'НОРВЕЖЕЦ')
and
-- 10
((S1.SMOKE = 'MARLBORO' and A2.ANIMAL = 'КОШКА') or
(S2.SMOKE = 'MARLBORO' and 'КОШКА' in (A1.ANIMAL, A3.ANIMAL)) or
(S3.SMOKE = 'MARLBORO' and 'КОШКА' in (A2.ANIMAL, A4.ANIMAL)) or
(S4.SMOKE = 'MARLBORO' and 'КОШКА' in (A3.ANIMAL, A5.ANIMAL)) or
(S5.SMOKE = 'MARLBORO' and A4.ANIMAL = 'КОШКА'))
and
-- 11
((S1.SMOKE = 'DUNHILL' and A2.ANIMAL = 'ЛОШАДЬ') or
(S2.SMOKE = 'DUNHILL' and 'КОШКА' in (A1.ANIMAL, A3.ANIMAL)) or
(S3.SMOKE = 'DUNHILL' and 'КОШКА' in (A2.ANIMAL, A4.ANIMAL)) or
(S4.SMOKE = 'DUNHILL' and 'КОШКА' in (A3.ANIMAL, A5.ANIMAL)) or
(S5.SMOKE = 'DUNHILL' and A4.ANIMAL = 'ЛОШАДЬ'))
and
-- 12
((S1.SMOKE = 'WINFIELD' and D1.DRINK = 'ПИВО') or
(S2.SMOKE = 'WINFIELD' and D2.DRINK = 'ПИВО') or
(S3.SMOKE = 'WINFIELD' and D3.DRINK = 'ПИВО') or
(S4.SMOKE = 'WINFIELD' and D4.DRINK = 'ПИВО') or
(S5.SMOKE = 'WINFIELD' and D5.DRINK = 'ПИВО'))
and
-- 13
((N1.NATION = 'НОРВЕЖЕЦ' and C2.COLOR = 'ГОЛУБОЙ') or
(N2.NATION = 'НОРВЕЖЕЦ' and 'ГОЛУБОЙ' in (C1.COLOR, C3.COLOR)) or
(N3.NATION = 'НОРВЕЖЕЦ' and 'ГОЛУБОЙ' in (C2.COLOR, C4.COLOR)) or
(N4.NATION = 'НОРВЕЖЕЦ' and 'ГОЛУБОЙ' in (C3.COLOR, C5.COLOR)) or
(N5.NATION = 'НОРВЕЖЕЦ' and C4.COLOR = 'ГОЛУБОЙ'))
and
-- 14
((S1.SMOKE = 'ROTHMANS' and N1.NATION = 'НЕМЕЦ') or
(S2.SMOKE = 'ROTHMANS' and N2.NATION = 'НЕМЕЦ') or
(S3.SMOKE = 'ROTHMANS' and N3.NATION = 'НЕМЕЦ') or
(S4.SMOKE = 'ROTHMANS' and N4.NATION = 'НЕМЕЦ') or
(S5.SMOKE = 'ROTHMANS' and N5.NATION = 'НЕМЕЦ'))
and
-- 15
((S1.SMOKE = 'MARLBORO' and D2.DRINK = 'ВОДА') or
(S2.SMOKE = 'MARLBORO' and 'ВОДА' in (D1.DRINK, D3.DRINK)) or
(S3.SMOKE = 'MARLBORO' and 'ВОДА' in (D2.DRINK, D4.DRINK)) or
(S4.SMOKE = 'MARLBORO' and 'ВОДА' in (D3.DRINK, D5.DRINK)) or
(S5.SMOKE = 'MARLBORO' and D4.DRINK = 'ВОДА'))

Сообщение **kdv** » 08 ноя 2006, 00:57

запустил тот же запрос на Firebird 2.0.012169 Beta 2. Полная лажа

и правда, полная лажа. какой смысл запускать на beta 2, если есть rc5? Даже если бы результат был тот же самый?

p.s. на мой взгляд задача слегка далеко от практики находится.

romaklimenko

Привет!

kdv писал(а):
запустил тот же запрос на Firebird 2.0.012169 Beta 2. Полная лажа
и правда, полная лажа. какой смысл запускать на beta 2, если есть rc5? Даже если бы результат был тот же самый?

p.s. на мой взгляд задача слегка далеко от практики находится.

Смысл в том, что базу на 60млн записей в одной из таблиц лень бэкапить-ресторить из-за того, чтобы проверить как там на RC5 решается задачка с немцами и рыбками. Если там лады, то все просто замечательно, хотя чисто умозрительно мне непонятно все-таки за счет чего такой тупой запрос так бысто отработал на конкурирующем продукте. Там же вариантов куча: 25 таблиц по пять записей! Даже если задачка далека от проблем насущных, приятно, если продукт, на котором ты работаешь, справляется с ней лучше чем MSDE.

А апдейтиться я буду только после финального релиза. Работает - не трогай.

CyberMax · Сообщение **CyberMax** » 08 ноя 2006, 10:17

Камрад, беты промышленно не применяются. А твоя задача - ну очень редкий случай. Лучше тестируй на реальных данных.

romaklimenko

CyberMax писал(а):Камрад, беты промышленно не применяются. Ну а твоя задача - ну очень редкий случай. Лучше тестируй на реальных данных.

Нет, ребята, извините, конечно, но это как в анекдоте, когда пионер в троллейбусе обращается к стоящему в дверях пассажиру:
- Дяденька, вы выходите на следующей остановке?
- Слушай, мальчик. Выхожу я или не выхожу - не важно. Важно чтобы ты в школе хорошо учился.

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

А если серьезно, то RC тоже промышленно не применяются, но ведь это и не важно...

Код: Выделить всё

void Why(){
    if (VERSION != CURRENT){
        Console.WriteLine("Обнови FireBird!"); // до RC5
        exit();
    }
    else{
        // AI есть только у MSDE?
				Console.WriteLine("Тебе это не надо. Свободен.");  
        exit();
    }
}

Сообщение **kdv** » 08 ноя 2006, 20:16

А если серьезно, то RC тоже промышленно не применяются, но ведь это и не важно...

фокус в том, что оптимизатор менялся в RC4. т.е. уже между RC3 и RC4 есть отличия. Может быть для этой задачи что-то и поменялось. Но лично я, даже если не поменялось, особого смысла упираться в заточку оптимизатора под эту задачу не вижу. Теория это одно, а практика - другое.

читал-бы ты конференцию на gmane, видел-бы баталии по поводу изменений в оптимизаторе в RC4...

romaklimenko

kdv писал(а):фокус в том, что оптимизатор менялся в RC4. т.е. уже между RC3 и RC4 есть отличия.

Дмитрий, все так.

Спасибо за общение. Таки перейду на RC4. Просто поразила разница во времени, тем более, что по моим подсчетам 5^25 - это очень много, а майкрософтовцы как-то умудрились решить проблему интеллектуально и меня это заинтересовало. А к тому же мой запрос показался мне корявым до безобразия и подумалось неужели лучше никто не решил.

Вот. А FB я все равно люблю всем сердцем и жду не дождусь финального релиза.

Oleg Loa · Сообщение **Oleg Loa** » 15 ноя 2006, 12:22

Вон на sql.ru народ этим тестом oracle в даун отправил, а ты FB, FB

http://www.sql.ru/forum/actualthread.aspx?tid=362323

romaklimenko

Oleg Loa писал(а):Вон на sql.ru народ этим тестом oracle в даун отправил, а ты FB, FB

http://www.sql.ru/forum/actualthread.aspx?tid=362323

Однако.

Только я не удивлен, почему этот запрос тормозит. Скорее, почему иногда он НЕ тормозит.

Ни у кого нет плана от MSSQL?

Oleg Loa · Сообщение **Oleg Loa** » 16 ноя 2006, 19:06

romaklimenko писал(а):Ни у кого нет плана от MSSQL?

Тупой join по индексам и всё. Oracele 9.2.0.7 на препаре сначала умирает потом через пол часа выдаёт что не хватило памяти и идиты в лес со своим запросом

Dioxin · Сообщение **Dioxin** » 20 ноя 2006, 14:00

Попробовал этот изврат на PostgreSQL 8.1.4 (WIN32:))
Решает... только время решения прыгает.
С разными типами индексов от 12 до 120 секунд
в среднем - около минуты...