[OT] Zagadka
Wojciech \Spook\ Sura - 24-12-2006 00:37
[OT] Zagadka
Witam!
Swego czasu natrafiłem na paskudny problem SQLowy, który po długich walkach
rozwiązałem, ale myślę, że stanowi on niezłą łamigłówkę.
Rozważmy tabele: kontrahent, adres, pracownik i posrednik.
Spełniają one następujące zależności:
a) Każdy adres jest przypisany do dokładnie jednego kontrahenta (wiązanie po
id);
b) Każdy pracownik za pomocą pośrednika jest przypisany do dowolnej liczby
adresów (w szczególności może być przypisany do adresów różnych
kontrahentów).
Problem jest następujący:
Wybrać z bazy dane, które zawierają wszystkich kontrahentów oraz w każdym
wierszu:
a) Musi znajdować się nazwa kontrahenta;
b) Musi znajdować się pewien adres powiązany z kontrahentem (nie robi
różnicy, który)
c) Musi znajdować się pewien pracownik powiązany z tym adresem (nie robi
różnicy, który)
I najważniejsze: Każdy kontrahent może pojawić się dokładnie jeden raz!
Oto stosowny SQL:
<sql mode="on">
create table kontrahent(
id integer not null auto_increment primary key,
nazwa varchar(100));
create table adres(
id integer not null auto_increment primary key,
nazwa varchar(100),
id_kontrahenta integer not null);
create table pracownik(
id integer not null auto_increment primary key,
imie varchar(100),
nazwisko varchar(100));
create table posrednik(
id integer not null auto_increment primary key,
id_osoby integer not null,
id_adresu integer not null);
insert into kontrahent (nazwa) values ('Kontrahent 1');
insert into kontrahent (nazwa) values ('Kontrahent 2');
insert into kontrahent (nazwa) values ('Kontrahent 3');
insert into adres (nazwa, id_kontrahenta) values ('Adres 1',1);
insert into adres (nazwa, id_kontrahenta) values ('Adres 2',1);
insert into adres (nazwa, id_kontrahenta) values ('Adres 3',2);
insert into adres (nazwa, id_kontrahenta) values ('Adres 4',2);
insert into adres (nazwa, id_kontrahenta) values ('Adres 5',3);
insert into adres (nazwa, id_kontrahenta) values ('Adres 6',3);
insert into pracownik (imie, nazwisko) values ('Imie1', 'Nazwisko1');
insert into pracownik (imie, nazwisko) values ('Imie2', 'Nazwisko2');
insert into pracownik (imie, nazwisko) values ('Imie3', 'Nazwisko3');
insert into pracownik (imie, nazwisko) values ('Imie4', 'Nazwisko4');
insert into pracownik (imie, nazwisko) values ('Imie5', 'Nazwisko5');
insert into pracownik (imie, nazwisko) values ('Imie6', 'Nazwisko6');
insert into pracownik (imie, nazwisko) values ('Imie7', 'Nazwisko7');
insert into pracownik (imie, nazwisko) values ('Imie8', 'Nazwisko8');
insert into pracownik (imie, nazwisko) values ('Imie9', 'Nazwisko9');
insert into pracownik (imie, nazwisko) values ('Imie10', 'Nazwisko10');
insert into pracownik (imie, nazwisko) values ('Imie11', 'Nazwisko11');
insert into pracownik (imie, nazwisko) values ('Imie12', 'Nazwisko12');
insert into posrednik (id_osoby, id_adresu) values (1, 1);
insert into posrednik (id_osoby, id_adresu) values (2, 1);
insert into posrednik (id_osoby, id_adresu) values (3, 2);
insert into posrednik (id_osoby, id_adresu) values (4, 2);
insert into posrednik (id_osoby, id_adresu) values (5, 3);
insert into posrednik (id_osoby, id_adresu) values (6, 3);
insert into posrednik (id_osoby, id_adresu) values (7, 4);
insert into posrednik (id_osoby, id_adresu) values (8, 4);
insert into posrednik (id_osoby, id_adresu) values (9, 5);
insert into posrednik (id_osoby, id_adresu) values (10, 5);
insert into posrednik (id_osoby, id_adresu) values (11, 6);
insert into posrednik (id_osoby, id_adresu) values (12, 6);
mysql> select k.nazwa as kontrahent,
-> a.nazwa as adres,
-> p.nazwisko as pracownik
-> from
-> kontrahent k,
-> adres a,
-> pracownik p,
-> posrednik po
-> where
-> k.id = a.id_kontrahenta and
-> a.id = po.id_adresu and
-> p.id = po.id_osoby
-> order by kontrahent asc, adres asc, pracownik asc;
+--------------+---------+------------+
| kontrahent | adres | pracownik |
+--------------+---------+------------+
| Kontrahent 1 | Adres 1 | Nazwisko1 |
| Kontrahent 1 | Adres 1 | Nazwisko2 |
| Kontrahent 1 | Adres 2 | Nazwisko3 |
| Kontrahent 1 | Adres 2 | Nazwisko4 |
| Kontrahent 2 | Adres 3 | Nazwisko5 |
| Kontrahent 2 | Adres 3 | Nazwisko6 |
| Kontrahent 2 | Adres 4 | Nazwisko7 |
| Kontrahent 2 | Adres 4 | Nazwisko8 |
| Kontrahent 3 | Adres 5 | Nazwisko10 |
| Kontrahent 3 | Adres 5 | Nazwisko9 |
| Kontrahent 3 | Adres 6 | Nazwisko11 |
| Kontrahent 3 | Adres 6 | Nazwisko12 |
+--------------+---------+------------+
12 rows in set (0.42 sec)
<sql mode="off">
Docelowy select powinien zwrócić na przykład taką tabelkę (na przykład, bo
mogą się różnić adresami bądź pracownikami, ale muszą zachowywać
powiązania):
+--------------+---------+------------+
| kontrahent | adres | pracownik |
+--------------+---------+------------+
| Kontrahent 1 | Adres 1 | Nazwisko1 |
| Kontrahent 2 | Adres 3 | Nazwisko6 |
| Kontrahent 3 | Adres 6 | Nazwisko11 |
+--------------+---------+------------+
Inny opis problemu:
Napisać coś pokroju:
SELECT DISTINCT ON (kontrahent) (...)
I notatka: w niektórych bazach powyższe zapytanie zadziała (tzn można
zakładać distincta na pojedyncze pole, co rozwiązuje problem). Zaakceptuję
jednak takie rozwiązanie tylko wtedy, gdy będzie szybsze od wszystkich
zaprezentowanych rozwiązań nie używających distincta na polu.
Baza danych dowolna - Mysql, postgres, interbase/firebird, oracle itp. Można
też zmodyfikować w rozsądnych granicach powyższe tabele - na przykład dodać
klucze obce, co powinno trochę przyspieszyć poszukiwanie.
Jako wynik proszę podać samo zapytanie oraz liczbę rekordów na których było
testowane i czas w jakim zadziałało.
Powiem tylko, że moje zapytanie było na firebirdzie 2.0 i zajęło coś koło 30
linijek sensownie sformatowanego SQLa (włączając w to jeszcze filtrowanie
nazw kontrahentów, adresów i pracowników).
Pozdrawiam -- Spook.
--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !
Paweł Matejski - 24-12-2006 00:37
Wojciech "Spook" Sura wrote:
> Witam!
>
> Swego czasu natrafiłem na paskudny problem SQLowy, który po długich
> walkach rozwiązałem, ale myślę, że stanowi on niezłą łamigłówkę.
>
> Rozważmy tabele: kontrahent, adres, pracownik i posrednik.
> Spełniają one następujące zależności:
> a) Każdy adres jest przypisany do dokładnie jednego kontrahenta
> (wiązanie po id);
> b) Każdy pracownik za pomocą pośrednika jest przypisany do dowolnej
> liczby adresów (w szczególności może być przypisany do adresów różnych
> kontrahentów).
>
> Problem jest następujący:
>
> Wybrać z bazy dane, które zawierają wszystkich kontrahentów oraz w
> każdym wierszu:
>
> a) Musi znajdować się nazwa kontrahenta;
> b) Musi znajdować się pewien adres powiązany z kontrahentem (nie robi
> różnicy, który)
> c) Musi znajdować się pewien pracownik powiązany z tym adresem (nie robi
> różnicy, który)
>
> I najważniejsze: Każdy kontrahent może pojawić się dokładnie jeden raz!
>
> Docelowy select powinien zwrócić na przykład taką tabelkę (na przykład,
> bo mogą się różnić adresami bądź pracownikami, ale muszą zachowywać
> powiązania):
>
> +--------------+---------+------------+
> | kontrahent | adres | pracownik |
> +--------------+---------+------------+
> | Kontrahent 1 | Adres 1 | Nazwisko1 |
> | Kontrahent 2 | Adres 3 | Nazwisko6 |
> | Kontrahent 3 | Adres 6 | Nazwisko11 |
> +--------------+---------+------------+
>
> Inny opis problemu:
>
> Napisać coś pokroju:
>
> SELECT DISTINCT ON (kontrahent) (...)
>
> I notatka: w niektórych bazach powyższe zapytanie zadziała (tzn można
> zakładać distincta na pojedyncze pole, co rozwiązuje problem).
> Zaakceptuję jednak takie rozwiązanie tylko wtedy, gdy będzie szybsze od
> wszystkich zaprezentowanych rozwiązań nie używających distincta na polu.
Będzie najszybsze.
A gdzie tu zagadka - problem był w użyciu distinct - reszta to już zwykły join,
który pokazałeś w swoim selekci.
W mysqlu za to do Twojego zapytania powinno wystarczyć dodać:
GROUP by k.nazwa
A w pozostałych bazach pozostaje brzydkie z podzapytaniem wykonywanym dla
każdego wiersza z kontrahent.
> Baza danych dowolna - Mysql, postgres, interbase/firebird, oracle itp.
> Można też zmodyfikować w rozsądnych granicach powyższe tabele - na
> przykład dodać klucze obce, co powinno trochę przyspieszyć poszukiwanie.
Klucze nie przyspieszają. Może chodziło Ci o indexy?
> Jako wynik proszę podać samo zapytanie oraz liczbę rekordów na których
> było testowane i czas w jakim zadziałało.
Nie chce mi się. Zresztą takie testy to se można....
> Powiem tylko, że moje zapytanie było na firebirdzie 2.0 i zajęło coś
> koło 30 linijek sensownie sformatowanego SQLa (włączając w to jeszcze
> filtrowanie nazw kontrahentów, adresów i pracowników).
Lol... 30 linijek? Mnie wyszło 15 (chyba można pozbyć się jeszcze pośrednika z
najbardziej zewnętrznego zapytania), ale to będzie napewno wolniejsze od dwóch
pierwszych.
select k.nazwa as kontrahent, a.nazwa as adres, p.nazwisko as pracownik
from kontrahent k, adres a, pracownik p, posrednik po,
( select kk.id as id_kontrahenta,
(select ppo.id_osoby
from adres aa,posrednik ppo
where ppo.id_adresu = aa.id
and aa.id_kontrahenta = kk.id
limit 1) as id_osoby
from kontrahent kk) ko
where k.id = a.id_kontrahenta
and a.id = po.id_adresu
and p.id = po.id_osoby
and ko.id_kontrahenta = k.id
and ko.id_osoby = p.id
order by kontrahent asc, adres asc, pracownik asc;
--
P.M.
Wojciech \Spook\ Sura - 24-12-2006 00:37
Paweł Matejski wrote:
> Będzie najszybsze.
Zgadujesz czy sprawdziłeś? Ja sprawdzałem moje długie zapytanie vs distinct
on (ba! sprawdzał mój wykładowca z baz danych na UWr) i za każdym razem
distinct on było najwolniejsze (explain analyze pokazywało dlaczego).
> A gdzie tu zagadka - problem był w użyciu distinct - reszta to już
> zwykły join, który pokazałeś w swoim selekci.
Problem w tym, żeby zapytanie było szybkie. Distinct je ostro spowolnił.
> W mysqlu za to do Twojego zapytania powinno wystarczyć dodać:
> GROUP by k.nazwa
To też było jedno z rozwiązań - ale tylko na MySqlu. Z tego, co pamiętam,
działało to równie wolno, jak distinct on - bo w zasadzie robi dokładnie to
samo.
> A w pozostałych bazach pozostaje brzydkie z podzapytaniem wykonywanym
> dla każdego wiersza z kontrahent.
No i o to mi chodziło. Tylko, że to brzydkie zapytanie jest stosunkowo
szybkie.
> Klucze nie przyspieszają. Może chodziło Ci o indexy?
Chodziło mi o foreign key - dlaczego nie przyspieszą?
> Nie chce mi się. Zresztą takie testy to se można....
Dlaczego? Ja jestem na przykład ciekawy, która baza obrobiłaby takie
zapytanie najszybciej i przy którym zapytaniu. Z czystej ciekawości - nie
mam zamiaru twierdzić, że jedna baza jest lepsza od drugiej, bo przerobiła
to konkretne zapytanie szybciej.
>> Powiem tylko, że moje zapytanie było na firebirdzie 2.0 i zajęło coś
>> koło 30 linijek sensownie sformatowanego SQLa (włączając w to jeszcze
>> filtrowanie nazw kontrahentów, adresów i pracowników).
>
> Lol... 30 linijek? Mnie wyszło 15 (chyba można pozbyć się jeszcze
> pośrednika z najbardziej zewnętrznego zapytania), ale to będzie
> napewno wolniejsze od dwóch pierwszych.
Czytanie ze zrozumieniem. A filtrujesz nazwy kontrahentów, adresów i
pracowników? Poza tym mówiłem o zapytaniu, które ja pisałem. Powyższy
przykład jest silnym uproszczeniem mojego problemu. Rozbij to jeszcze na
nazwę adresu, miasto i ulicę, dodaj grupę kontrahenta i wprowadź na wszystko
filtry, a potem - rozsądnie grupując - zmieść się w 15 linijkach.
> select k.nazwa as kontrahent, a.nazwa as adres, p.nazwisko as
> pracownik
> from kontrahent k, adres a, pracownik p, posrednik po,
> ( select kk.id as id_kontrahenta,
> (select ppo.id_osoby
> from adres aa,posrednik ppo
> where ppo.id_adresu = aa.id
> and aa.id_kontrahenta = kk.id
> limit 1) as id_osoby
> from kontrahent kk) ko
> where k.id = a.id_kontrahenta
> and a.id = po.id_adresu
> and p.id = po.id_osoby
> and ko.id_kontrahenta = k.id
> and ko.id_osoby = p.id
> order by kontrahent asc, adres asc, pracownik asc;
No i to jest - o ile dobrze widzę - rozwiązanie (a przynajmniej jedno z
rozwiązań). Jakoś w czwartek wrzucę tu moje zapytanie.
Pozdrawiam -- Spook.
--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !
Paweł Matejski - 24-12-2006 00:37
Wojciech "Spook" Sura wrote:
> Paweł Matejski wrote:
>> Będzie najszybsze.
>
> Zgadujesz czy sprawdziłeś? Ja sprawdzałem moje długie zapytanie vs
> distinct on (ba! sprawdzał mój wykładowca z baz danych na UWr) i za
> każdym razem distinct on było najwolniejsze (explain analyze pokazywało
> dlaczego).
Zgaduje. :) A do bawienia się explainem jest za mało danych.
>> A gdzie tu zagadka - problem był w użyciu distinct - reszta to już
>> zwykły join, który pokazałeś w swoim selekci.
>
> Problem w tym, żeby zapytanie było szybkie. Distinct je ostro spowolnił.
To pasuje to wyraźnie napisać, że zagadką jest napisanie wydajnego zapytania!
>> W mysqlu za to do Twojego zapytania powinno wystarczyć dodać:
>> GROUP by k.nazwa
>
> To też było jedno z rozwiązań - ale tylko na MySqlu. Z tego, co
> pamiętam, działało to równie wolno, jak distinct on - bo w zasadzie robi
> dokładnie to samo.
>
>> A w pozostałych bazach pozostaje brzydkie z podzapytaniem wykonywanym
>> dla każdego wiersza z kontrahent.
>
> No i o to mi chodziło. Tylko, że to brzydkie zapytanie jest stosunkowo
> szybkie.
Pokażesz, to zobaczymy.
>> Klucze nie przyspieszają. Może chodziło Ci o indexy?
>
> Chodziło mi o foreign key - dlaczego nie przyspieszą?
A dlaczego maja przyspieszać?
>> Nie chce mi się. Zresztą takie testy to se można....
>
> Dlaczego? Ja jestem na przykład ciekawy, która baza obrobiłaby takie
> zapytanie najszybciej i przy którym zapytaniu. Z czystej ciekawości -
> nie mam zamiaru twierdzić, że jedna baza jest lepsza od drugiej, bo
> przerobiła to konkretne zapytanie szybciej.
Ale nie zapewnimy porównywalnych warunków do testów! Różne sprzęty, różne dane.
> No i to jest - o ile dobrze widzę - rozwiązanie (a przynajmniej jedno z
> rozwiązań). Jakoś w czwartek wrzucę tu moje zapytanie.
Do czwartku, to tu wszyscy o tym zapomną.
--
P.M.
Jacek Czapla - 24-12-2006 00:37
Paweł Matejski napisał(a):
> Wojciech "Spook" Sura wrote:
>> Paweł Matejski wrote:
>>> Będzie najszybsze.
>> Zgadujesz czy sprawdziłeś? Ja sprawdzałem moje długie zapytanie vs
>> distinct on (ba! sprawdzał mój wykładowca z baz danych na UWr) i za
>> każdym razem distinct on było najwolniejsze (explain analyze pokazywało
>> dlaczego).
>
> Zgaduje. :) A do bawienia się explainem jest za mało danych.
>
>>> A gdzie tu zagadka - problem był w użyciu distinct - reszta to już
>>> zwykły join, który pokazałeś w swoim selekci.
>> Problem w tym, żeby zapytanie było szybkie. Distinct je ostro spowolnił.
>
> To pasuje to wyraźnie napisać, że zagadką jest napisanie wydajnego zapytania!
>
>>> W mysqlu za to do Twojego zapytania powinno wystarczyć dodać:
>>> GROUP by k.nazwa
>> To też było jedno z rozwiązań - ale tylko na MySqlu. Z tego, co
>> pamiętam, działało to równie wolno, jak distinct on - bo w zasadzie robi
>> dokładnie to samo.
>>
>>> A w pozostałych bazach pozostaje brzydkie z podzapytaniem wykonywanym
>>> dla każdego wiersza z kontrahent.
>> No i o to mi chodziło. Tylko, że to brzydkie zapytanie jest stosunkowo
>> szybkie.
>
> Pokażesz, to zobaczymy.
>
>>> Klucze nie przyspieszają. Może chodziło Ci o indexy?
>> Chodziło mi o foreign key - dlaczego nie przyspieszą?
>
> A dlaczego maja przyspieszać?
Coś mi się kołacze po łbie, że niektóre bazy dodają niejawnie indeksy do
kluczy, a niektóre nie dodają nawet dla PK.
Jeśli to prawda, to w niektórych przyśpieszy a niektórych nie, z tym, ze
oczywiście nie zależy to od klucza obcego a od ewentualnego indeksowania.
--
*Jacek Czapla* //usuń ".pułapka" z adresu email
www.ASIT.pl
http://www.busyonline.pl - Rezerwacja miejsc w busach
zanotowane.pldoc.pisz.plpdf.pisz.pleffulla.pev.pl
|
[OT?] Monitory dla =?ISO-8859-2?Q?grafik=F3w_-_pytanie_o_?==?ISO-8859-2?Q?przej=B6ci=F3wki?=
(OT) do oceny - =?ISO-8859-2?Q?poprawno=B6=E6_graficzna_i_?==?ISO-8859-2?Q?plityczna=3A=29?=
[OT] Praca - wymagania PS, CD, AI, AE, QE, MS, CD, AVI, SWF...
[OT] Daemon Tools-y dla 64 bit wreszcie =?ISO-8859-2?Q?s=B1?=
=?iso-8859-2?Q?[OT]_Praca_-_pierwsza_jask=F3=B3ka?=
=?ISO-8859-2?Q?[OT]Jak_to_zrobi=E6=3F_Pomocy.?=
[ot] Agencja Reklamowa nawiąże zdalną współpracę z grafikiem
Re: [OT] Chcesz zostać typografem? Ostatnia szansa
OT: Sybase w Polsce, place w UK itd.
[OT] kody pocztowe i teryt - szukam informacji
zanotowane.pldoc.pisz.plpdf.pisz.plmorebeer.opx.pl
Cytat
Decede mihi sole - nie zasłaniaj mi słonca.
Gdy kogoś kochasz, jesteś jak stworzyciel świata - na cokolwiek spojrzysz, nabiera to kształtu, wypełnia się barwą, światłem. Powietrze przytula się do ciebie, choćby był mróz, a ty masz w sobie tyle radości, że musisz ją rozdawać wokoło, bo się w tobie nie mieści
Hoc fac - tak czyń.
A tergo - od tyłu; z tyłu.
I czarne włosy posiwieją. Safona |
|
