Nagradni SQL zadatak: uklanjanje preklapajućih filtera
Friday, 21.10.2011 – DejanE dragi moji SQLovci, došao sam na ideju da vam ponudim jedan nagradni SQL zadatak. Radi se o jednom zadatku, sa kojim sam se susreo na poslu, a smatram ga veoma zanimljivim i interesantnim za razbuđivanje moždanih vijuga. 🙂
Postaviću vam zadatak, a najbolje rješenje će biti nagrađeno knjigom po izboru sa Amazona u vrijednosti do 50 EUR i biće objavljeno ovdje na blogu. Rješenje možete slati putem e-maila (dejan@) ili ostaviti kao komentar ispod teksta. Najbolje rješenje je ono, koje se najbrže izvrši – dakle, nebitno je koje ćete metode koristiti. Jedini uslov je da rezultat bude odrađen SQL upitom – nije dozvoljeno korištenje PL/SQL-a ili nekog drugog prog. jezika – samo SQL!
Opis zadatka
– imamo tabelu FILTER_CRITERIAS sa testnim podacima (za kreiranje tabele i unos potrebnih podataka, pokrenite ovu skriptu – insert_filter_criterias.sql )
– u tabeli se nalaze slijedeće kolone:
- ID – ključ za određenu grupu filtera
- NUMBER_KEY – filter za brojeve
- STRING_KEY – filter za stringove
- SERIES – filter za serijsku oznaku
- FIELD – filter za neko malo polje
- TEXT_ITEM – filter za neko veće tekstualno polje
– svaka grupa filtera je određena svojim ključem (ID)
– kombinacija svih filtera u jednom redu neke grupe zajednički čine tzv. kombi-filter, znači NUMBER_KEY, STRING_KEY, SERIES, FIELD i TEXT_ITEM zajedno čine jedan kombi-filter
– kombi-filter iz tabele FILTER_CRITERIAS se koristi u WHERE klauzuli nekog SQL upita, u kojem se vrijednosti iz neke tabele uspoređuju sa filterom
– e sad, pošto je moguće, da se određeni kombi-filteri preklapaju, zbog čega se dobijaju dupli redovi iz ciljne tabele, onda se kombi-filteri moraju svesti na najmanji mogući djelilac kao npr. kod skraćivanja razlomaka. Npr. ako je filter STRING_KEY prazan, tj. NULL, onda je on non-greedy i pokriva više slučajeva u odnosu na slučaj kada za STRING_KEY imamo npr. ‘DUMMY’, koji je više greedy: LIKE ‘%’ pokriva sve, a LIKE ‘DUMMY%’ samo stringove, koji počinju sa DUMMY. Isto važi i za ostale filtere. Da bih vam dočarao šta zapravo želim postići, prikazaću u tablici trenutne podatke, te redove, koji se preklapaju i kako bi trebao izgledati konačan rezultat.
Raw filter podaci
Zeleni redovi sadrže kombi-filter, koji isključuje preklapajuće kombi-filtere u istoj grupi
Ovako bi trebao da izgleda konačan rezultat
Nadam se da je jasan cilj ovog zadatka, a ako je nešto nejasno, možete ostaviti komentar ispod teksta ili poslati mi e-mail.
Konačni rok za slanje rješenja je 20.11.2011., nakon čega će uslijediti odabir i proglašenje najboljeg rješenja.
Eto, pa da vidimo ko je najbolji SQLovac. 🙂
19 Responses to “Nagradni SQL zadatak: uklanjanje preklapajućih filtera”
a gde je skripta za objekat “neka_tabela”?
By aleksandar on Oct 21, 2011
neka_tabela je u svemu ovome nebitna 😀
filteri iz FILTER_CRITERIAS se na isti nacin primijenjuju na bilo koju tabelu…
By Dejan on Oct 21, 2011
hm, a ti inače tako pišeš upit napamet ili proveravaš verodostojnost rezultata tako što IMAŠ “neku_tabelu”?
By aleksandar on Oct 21, 2011
Naravno da imam kreirane tabele, na koje primijenjujem ove filtere, ali kao sto rekoh, u ovom slucaju neka_tabela nije bitna. Ne opterecuj se njome 🙂
Cilj je samo izostaviti redudantne kombi-filtere iz svake grupe. Na koju tabelu ce se ti filteri primijeniti je potpuno nebitno, samo sam naveo na koji nacin se ti filteri koriste… Ti se trebas orjentisati samo na FILTER_CRITERIAS.
By Dejan on Oct 21, 2011
ja verujem da je tebi jasno, ali probaj da razumeš moj zahtev 🙂
šta ako u nekoj_tabeli ne postoji red koji bi se vratio kao duplikat jer ga neće naći filter kojeg želiš da se oslobodiš? ja onda mogu da napišem upit koji će prividno da bude ispravan.
By aleksandar on Oct 21, 2011
Evo prepravio sam zadatak – je l’ sad lakse? 🙂
Ponavljam opet – dio zadatka nije, da se provjeri da li se iz ciljne tabele vracaju dupli redovi ili ne. Zadatak je da se redudantni filteri izostave.
By Dejan on Oct 21, 2011
jasno mi je šta je zadatak. i ne znam zašto ne staviš DISTINCT u prvom redu, nego mučiš i sebe i nas. 🙂
By aleksandar on Oct 21, 2011
i još nešto: NUMBER_KEY je irelevantan u svemu ovome?
By aleksandar on Oct 21, 2011
ne bas, jer NUMBER_KEY moze pokrivati neku vrijednost, koja nije pokrivena drugim filterima…
osim toga, svaki filter moze prazan, cak stavise u jednom redu moze svaki filter biti prazan, pa onda imas kompletni non-greedy kombi-filter
jbg znam da je mozda nejasno, i meni je trebalo citav dan samo da skontam sta je autor htio reci 😀 naime, na poslu trenutno radim SQL i PL/SQL code review i optimizaciju ogromne aplikacije, pa sam naletio na ovaj slucaj – postoji tabela sa tim filterima, na osnovu kojih se vrsi selekcija podataka u drugim tabelama – bolesno i nezgrapno rjesenje, ali sta je tu je …
By Dejan on Oct 21, 2011
Izmenio si zadatak, pa sada ne znam kako se koristi filter_criterias u upitima. Sećam se da je bio jedan OR u upitu, jedan INSTR, a kako je tačno izgledalo, pojma nemam. Ajde vrati onaj primer upotrebe, makar manjim slovima da ne smeta aleksandru 🙂
By djoka_l on Oct 22, 2011
djoka: hehehe i ti se zakacio za onaj SQL upit 🙂 nebitno je kako se koriste filteri, ono je samo bio primjer…
znaci, imas tabelu sa redudantnim vrijednostima u odredjenim kolonama (u ovom slucaju grupisane kao kombi-filter), a cilj je izbaciti redudantne vrijednosti.
By Dejan on Oct 23, 2011
Naravno da je bitan upit, ondnosno WHERE uslovi, jer “overlaping redundant filter” ima neko značenje samo u kontekstu kako se filter primenjuje. Osim toga, uštedeo bi mi malo kucanja.
Dakle, WHERE uslovi su mi trebali da bih iz ugnežđenog upita dobio one uslove koji se, na način koji ti koristiš filtere, preklapaju sa onima koji su generalniji.
Evo upita (znam da mi fali uparivanje text_item jer nisi vratio prvobitni upit):
select * from filter_criterias
where rowid not in (
select match.rowid
from filter_criterias match, filter_criterias pattern
where match.rowid != pattern.rowid
and match.id = pattern.id
— Ovde idu isti uslovi kao u obrisanom primeru za uparivanje neke tabele
— sa filterima iz tabele filter_criterias
and (pattern.number_key = match.number_key or
nvl(match.string_key, ‘?’) like nvl(pattern.string_key, nvl(match.string_key, ‘?’)) || ‘%’
)
and nvl(match.series, ‘?’) = nvl(pattern.series, nvl(match.series, ‘?’))
and nvl(match.field, ‘?’) like nvl(pattern.field, nvl(match.field, ‘?’)) || ‘%’
)
By djoka_l on Oct 23, 2011
Uzgred, ja bih dodao i non’unique indeks nad poljem id tabele filter_criterias, pa onda ubacio i još jedan uslov u nested query:
and match.id = P_EXTERNAL_ID
i verovatno dobio bolje performanse za veliku tabelu filter_criterias
By djoka_l on Oct 23, 2011
ako je numbeR_key bitan, onda mislim da slika koju si naveo kao očekivani rezultat nije u redu. zato sam pitao da li je to polje od značaja.
By aleksandar on Oct 24, 2011
@djoka_l & @aleksandar: ma evo vam onaj SQL, kad ste toliko zapeli 😀
select t1.*
from neka_tabela t1,
— ovdje dolazi vas upit kao inline view
(SELECT … FROM filter_criterias) fc
where fc.id = p_filter_group_id
and (NVL(t1.number_key, ‘-1’) = NVL(fc.number_key, NVL(t1.number_key, ‘-1’))
OR
NVL(t1.string_key, ‘?’) like NVL(fc.string_key, NVL(t1.string_key, ‘?’)) ||’%’
)
and NVL(t1.series, ‘?’) = NVL(fc.series, NVL(t1.series, ‘?’))
and NVL(t1.field, ‘?’) like NVL(fc.field, NVL(t1.field, ‘?’) ) ||’%’
and INSTR(NVL(t1.text_item, ‘?’), nvl(fc.text_item, NVL(t1.text_item, ‘?’))) > 0;
@aleksandar: Hmmm, ne znam na koje filtere mislis? Ako mislis npr. na filter:
1;1;EBBR;F;LOWW;
onda je on redudantan, jer filter: 1;;E;;; pokriva SVE stringove, koji pocinju sa E, a samim tim i SVE brojeve, gdje string pocinje sa E, jer je kolona numer key prazna…
Da je tu jos npr. filter: 1;1;;;; , onda bi taj filter bio u konacnom rezultatu, jer nije redudantan, posto za string key moze biti CXY ili neki drugi, koji ne zapocinje sa E …
Znam da je mozda zadatak nejasan i da sam ga mozda nezgrapno postavio, ali evo pokusavam da razjasnim sta je cilj 😀 u stvarnosti je zadatak jos tezi, pa sam ga pokusao pojednostaviti…
Oprostite mi, ako sam nesto previdio ili nejasno napisao – vrlo rado cu ispraviti/dodati/pojasniti sta god bude trebalo. 🙂
By Dejan on Oct 24, 2011
a zašto si onda izbacio jedan od dva reda koji počinju sa 37?
By aleksandar on Oct 24, 2011
zato sto 1;;L;;LO; pokriva 1;37;LOWW;C;LOVV;DUMMY:
– number_key NULL pokriva sve brojeve
– string_key L pokriva sve stringove, koji pocinju sa L, u ovom slucaju LOWW
– series NULL pokriva sve vrijednosti iz kolone series, pa tako i vrijednost C
– field LO pokriva sve stringove, koji pocinju sa LO, u ovom slucaju LOVV
– text_item NULL pokriva sve vrijednosti, pa tako i DUMMY
By Dejan on Oct 25, 2011
Dakle, rok je prosao. Niste se bas pretrgli u rjesavanju ovog zadatka 🙁 Nije valjda da je bilo tako tesko?
U svakom slucaju, djoka_l je zasluzio knjigu po izboru, jer je jedini dao kakvo-takvo upotrebljivo rjesenje – javi se preko emaila, sa nazivom knjige, koju zelis i navedi mi adresu na koju da ti se isporuci knjiga.
By Dejan on Nov 23, 2011
Nemoj da se maltretiraš sa slanjem knjige, nisam to radio zbog nagrade. Inače, moje rešenjce čak ni ne radi kako treba, uradio sam ga odmah posle zadavanja, ali mi posle nije bilo interesantno da ga popravljam. Veći mi je motiv da sam problem nego nagrada. Nije mi se svidelo ni ograničenje da sve mora u SQL-u bez upotrebe PL/SQL koda. Bilo bi zgodno da ti staviš svoje rešenje koje si primenio.
By djoka_l on Dec 1, 2011