[MySql] select id's die NIET in andere tabel voorkomen

[Verwijderd]

Hallo,

ik zit te puzzelen om een query te maken die het volgende doet:

* uit tabel bedrijven ophalen, voor elk bedrijf waarvan de bedrijf_ID NIET voorkomt in de tabel forecast.

Ik had zoiets gemaakt:

code:

SELECT bedrijven.*
FROM bedrijven, forecast
WHERE NOT ( bedrijven.bedrijf_ID = forecast.bedrijf_ID )

maar als ik die uitvoer dan schiet mijn pc op tilt.

Is iemand die weet hoe ik dit in een query voor elkaar kan krijgen?

Alvast bedankt!

[whoami]

Je moet het met een subquery doen (maar dat ondersteunt MySQL niet), of met een outer join naar die andere tabel en controleren op NULL values.

code:

select bedrijf.id
from bedrijf
outer join forecast on bedrijf.id = forecast.bedrijf_id
WHERE forecast.bedrijf_id IS NULL

[ Voor 34% gewijzigd door whoami op 04-11-2004 10:55 ]

[GX]

whoami schreef op 04 november 2004 @ 10:54:
Je moet het met een subquery doen (maar dat ondersteunt MySQL niet)

Ervan uitgaande dat je MySQL 4.0 of lager hebt
4.1 doet subqueries prima..

[Verwijderd]

versie 4.0.21-nt heb ik (dus maar even upgraden dan)

Ik had al een subquery geprobeerd, alleen toen kreeg ik een foutmelding (via navicat)

De subquery die ik bedacht had, was als volgt:

code:

SELECT *
FROM bedrijven
WHERE NOT EXISTS
( SELECT bedrijf_ID FROM forecast )

Maar als ik sql een beetje begrijp dan zal de server niet echt snappen wat ik wil op deze manier...

Met die OUTER JOIN kom ik er ook niet helemaal uit. Ik heb het op deze manier geprobeerd (en wat andere opties):

code:

SELECT bedrijf_ID
FROM bedrijven
OUTER JOIN forecast ON bedrijven_bedrijf_ID = forecast.bedrijf_ID
WHERE forecast.bedrijf_ID IS NULL

Nog een klein zetje heb ik nodig... thx!

[ Voor 3% gewijzigd door Verwijderd op 04-11-2004 11:25 ]

[Eelke Spaak]

Als volgt:

code:

SELECT bedrijven.*
FROM bedrijven
WHERE NOT bedrijven.bedrijf_ID IN
  (SELECT forecast.bedrijf_ID FROM forecast)

[Haploid]

Verwijderd schreef op 04 november 2004 @ 11:25:
Met die OUTER JOIN kom ik er ook niet helemaal uit. Ik heb het op deze manier geprobeerd (en wat andere opties):

code:

SELECT bedrijf_ID
FROM bedrijven
OUTER JOIN forecast ON bedrijven_bedrijf_ID = forecast.bedrijf_ID
WHERE forecast.bedrijf_ID IS NULL

Nog een klein zetje heb ik nodig... thx!

Dit ziet er uit alsof het zou moeten werken, maar maak er voor de zekerheid nog even "SELECT DISTINCT bedrijf_ID" van, om te voorkomen dat je dubbelen krijgt (ik ga ervanuit dat een bedrijf meerdere malen in forecast kan voorkomen). Dus:

code:

SELECT DISTINCT bedrijf_ID
FROM bedrijven
OUTER JOIN forecast ON bedrijven_bedrijf_ID = forecast.bedrijf_ID
WHERE forecast.bedrijf_ID IS NULL

[Verwijderd]

Ik heb bij mij lokaal even versie 4.1.7-nt geinstalleerd. Daarop de betreffende databases gekopieerd, maar helaas doen beide voorstellen het niet.

De query met de subquery duurt heel lang, maar komt uiteindelijk met 0 resultaten terug.

De query met de OUTER JOIN geeft nog steeds een foutmelding over dat ik de syntax moet controleren ter hoogte van OUTER JOIN blablabla.

Ik had in die OUTER JOIN wel alvast even bedrijven_bedrijf_ID veranderd in bedrijven.bedrijf_ID. Dat deed de truc helaas ook niet.

Lastig zeg

[Tux]

Wat is de precieze error die je krijgt?

En wat is de query op het moment precies?

[Black Hawk]

Probeer dit eens (verschil met andere voorbeelden dat je hier in de eerste SELECT maar 1 kolom hebt)

code:

SELECT     bedrijf_ID 
FROM         bedrijven
WHERE     (bedrijf_ID  NOT IN
               (SELECT     bedrijf_ID 
                FROM          forecast))

[ Voor 4% gewijzigd door Black Hawk op 04-11-2004 14:09 ]

[Haploid]

Verwijderd schreef op 04 november 2004 @ 13:58:
De query met de OUTER JOIN geeft nog steeds een foutmelding over dat ik de syntax moet controleren ter hoogte van OUTER JOIN blablabla.

Ja, wat voor foutmelding precies? Oh wacht, kan het zijn dat MySQL misschien verwacht dat je FULL OUTER JOIN gebruikt? Probeer dat eens.

[ACM]

Dan eerder dat ie wil dat je LEFT (OUTER) JOIN neemt. (haakjes geeft aan dat outer in dit geval optioneel is)

[Haploid]

ACM schreef op 04 november 2004 @ 14:21:
Dan eerder dat ie wil dat je LEFT (OUTER) JOIN neemt. (haakjes geeft aan dat outer in dit geval optioneel is)

Ja, OK. Ik ging ervanuit dat de tabel forecast verwijst naar de tabel bedrijven. Dan zou het niet uitmaken, maar toch LEFT is correcter. Verder kan ik ook niet vinden in de MySQL documentatie dan FULL uberhaupt ondersteund wordt, eerder het omgekeerde.

Dus, Haleb0pp, dan wordt 't vooralsnog:

code:

SELECT DISTINCT b.bedrijf_ID
FROM bedrijven b
LEFT JOIN forecast f ON b.bedrijf_ID = f.bedrijf_ID
WHERE f.bedrijf_ID IS NULL

[Gods Lonely Man]

zo word het dan toch?

code:

SELECT bedrijven.*
FROM bedrijven LEFT JOIN forecast ON ( bedrijven.bedrijf_ID = forecast.bedrijf_ID )
WHERE forecast.bedrijf_ID IS NULL

edit:
fear my slowness

[ Voor 15% gewijzigd door Gods Lonely Man op 04-11-2004 14:29 ]

[Verwijderd]

OK zowel de oplossing met de subquery zoals Black Hawk hem aangaf werkt, als de oplossing met de LEFT JOIN van PsychoBoy. Allebei zijn het vrij trage queries, dus ik ga voor de LEFT JOIN omdat ik dan mijn server niet hoef te upgraden

Thx a lot allemaal!!!

[Haploid]

Any time, b0pp.

Voor wat betreft de performance zouden indexen (indices) op de Bedrijf_ID kolommen van beide tabellen misschien een idee zijn.

code:

CREATE INDEX ix_bedrijven1 ON bedrijven(bedrijf_ID)
CREATE INDEX ix_forecast1 ON forecast(bedrijf_ID)

De eerste is waarschijnlijk niet nodig, ik neem aan dat er standaard index staat op die kolom als dat de primary key is. De tweede zou behoorlijk wat tijd kunnen schelen.

[Verwijderd]

Verwijderd schreef op 04 november 2004 @ 14:56:
OK zowel de oplossing met de subquery zoals Black Hawk hem aangaf werkt, als de oplossing met de LEFT JOIN van PsychoBoy. Allebei zijn het vrij trage queries, dus ik ga voor de LEFT JOIN omdat ik dan mijn server niet hoef te upgraden

Thx a lot allemaal!!!

Toch even theoretisch zeiken
De subquery is bij andere databases vaak de meest efficiente aangezien bij de outer join de test voor elk record apart gedaan moet worden terwijl bij de methode met subquery de subquery slechts eenmalig uitgevoerd hoeft te worden. Dat betekend dat je database server in het geval van de subquery enkel twee simpele queries moet doen en daarna matchen. Bij de outer join ontkom je er niet aan de forecast tabel voor elk record door te lopen wat vele malen trager is.
Helaas is de optimizer van mySQL blijkbaar nog steeds niet zo ver dat die onafhankelijke subqueries "goed" afhandeld, maar in toekomstige versies of andere dbs kan de methode met subquery dus een duidelijke performancewinst geven.

[Haploid]

Verwijderd schreef op 04 november 2004 @ 15:29:
De subquery is bij andere databases vaak de meest efficiente aangezien bij de outer join de test voor elk record apart gedaan moet worden terwijl bij de methode met subquery de subquery slechts eenmalig uitgevoerd hoeft te worden. Dat betekend dat je database server in het geval van de subquery enkel twee simpele queries moet doen en daarna matchen. Bij de outer join ontkom je er niet aan de forecast tabel voor elk record door te lopen wat vele malen trager is.
Helaas is de optimizer van mySQL blijkbaar nog steeds niet zo ver dat die onafhankelijke subqueries "goed" afhandeld, maar in toekomstige versies of andere dbs kan de methode met subquery dus een duidelijke performancewinst geven.

Nee, daar ben ik het nou niet mee eens. Uitgaande van drie verschillende opstellingen:

1. Join zonder index
2. Subquery
3. Join met index

Gegeven verder:
N = aantal rijen in tabel "bedrijven"
M = aantal rijen in tabel "forecast"
m = aantal rijen in de subquery in 2 (is <M)

1. De join zonder index die moet (inderdaad) alle rijen in bedrijven met alle records in forecast vergelijken. Dat kost dus orde M * N tijd.
Totaal = M * N

2. De subquery is uitgevoerd in order M tijd, of minder als je een mooie index hebt, maar <M in ieder geval. Vervolgens moet elke rij in bedrijven vergeleken worden met de subquery, waarbij hij moet zoeken of de ID voorkomt in de subquery. Dit kost per rij in de subquery orde log(m), dus in totaal order N * log(m) tijd.
Totaal = M + N * log(m)

3. Bij de join MET index moet voor elke rij in bedrijven de ID worden opgezocht in forecast. Dit opzoeken kan in orde 1 tijd, met de mooie hash index die nu op de kolom ID in forecast staat. Dus, totaal orde N tijd.
Totaal = N

De getallen spreken voor zichzelf. Indexen heersen boven subqueries, behalve als de subquery een heel kleine resultaat set oplevert (dan scoren ze ongeveer gelijk).

[Verwijderd]

Bij de join MET index moet voor elke rij in bedrijven de ID worden opgezocht in forecast. Dit opzoeken kan in orde 1 tijd, met de mooie hash index die nu op de kolom ID in forecast staat. Dus, totaal orde N tijd.
Totaal = N

Dit klopt natuurlijk niet.

We praten hier over een OUTER join. Er is dus niet 1 record in de forecast tabel die gematched wordt aan een record in de bedrijven tabel. Er moet dus wel een scan plaatsvinden op de forecast tabel. Dus het blijft N*M

Daarnaast is het een beetje makkelijk om N+M*log(m) te gebruiken en tegelijkertijd orde N voor de geindexeerde tabel.
Een (goede) optimizer zal de query met subquery waarschijnlijk als volgt afhandelen.

Run de Subquery.
Verbouw de hoofdquery naar
Select * from table (Dus zonder NOT IN gedeelte) tenzij er erg weinig resultaten in de subquery zitten. In dat geval wordt het
select * from table where bedrijfID NOT IN [x1, x2, x3, x4, xn]
waarbij x1..xn VASTE getallen zijn.

In het laatste geval heb je dus geen *log(m) gedeelte aangezien je met vaste waarden werkt. In het eerste geval wordt de NOT IN beperking in het geheugen van de server getest. Dit is vele malen sneller als het fetchen van records uit de database. Als je van mening bent dat je dat een Orde log (m) moet toekennen kan je niet het scannen van de index een Orde 1 toekennen. Dat moet dan logischerwijs ook de orde N krijgen. De index kan hier weliswaar niet gebruikt worden maar dat vergeet ik dus maar even.

Conclusie. De query met subquery is N+M (* log(m)) en de geindexeerde query is N(*M) De query met subquery is dus (qua orde) minimaal gelijkwaardig. Wel is het zo dan N natuurlijk een stuk minder is dan N+M maar het is wel dezelfde orde.
Trouwens, een query met onafhankelijke subquery kan door een optimizer eenvoudig worden omgezet naar een join. Andersom is wat lastiger. Dus een onafhankelijke subquery heeft bij gebruik van een goede database engine (= iets beters dan mySQL ) altijd minimaal dezelfde performance als een join. Soms is die echter beter.

Ook is het niet zo dat je maar constant indexen kan blijven toevoegen om de meest vage velden te indexeren zodat al je queries optimaal lopen. Ook het bijhouden van een index kost tijd waardoor je insert, update en delete queries trager worden. Dus goede indexen verhogen de performance aanzienlijk maar zijn geen reden om de effectiviteit van je query te verwaarlozen noch een oplossing voor al je problemen. Deze query is dan ook een voorbeeld van een query die weinig voordeel heeft van indexen maar heel veel van een goede optimizer. Dat wil niet zeggen dat je geen indexen moet gebruiken, enkel dat er ook andere methoden zijn om goede performance te halen.

Als je dan je query op twee manieren kan formulieren, vind ik het raadzaam dat je het op zo'n manier doet dat een verbetering van de database engine ook jou database een boost geeft.

[ Voor 117% gewijzigd door Verwijderd op 05-11-2004 01:22 ]

[Haploid]

Verwijderd schreef op 04 november 2004 @ 23:58:
[...]

Dit klopt natuurlijk niet.

We praten hier over een OUTER join. Er is dus niet 1 record in de forecast tabel die gematched wordt aan een record in de bedrijven tabel. Er moet dus wel een scan plaatsvinden op de forecast tabel. Dus het blijft N*M

Inderdaad, er hoeft niet 1 record per bedrijf in de forecast tabel te staan. Maar het aantal records per bedrijf in forecast is niet meteen in de orde van grootte van M, je kunt eerder zeggen dat het gemiddeld M / N records zijn.

Als je een hash index op de kolom BedrijfID hebt, dan hoef je niet zo veel te doen om de records te vinden met een bepaald BedrijfID. Je berekent de hash waarde, en je springt in de index naar die waarde. Dat kost orde 1 tijd, het doorlopen van de linked list van records met dezelfde BedrijfID kost dan orde M / N tijd, maar een goede optimizer zal dat niet doen vanwege de DISTINCT.

Dus, worst case kost de JOIN met index orde N * (M / N) tijd, ofwel orde M. Best case is dat nog steeds orde N.

Verwijderd schreef op 04 november 2004 @ 23:58:
[...]

In het laatste geval heb je dus geen *log(m) gedeelte aangezien je met vaste waarden werkt. In het eerste geval wordt de NOT IN beperking in het geheugen van de server getest. Dit is vele malen sneller als het fetchen van records uit de database. Als je van mening bent dat je dat een Orde log (m) moet toekennen kan je niet het scannen van de index een Orde 1 toekennen. Dat moet dan logischerwijs ook de orde N krijgen. De index kan hier weliswaar niet gebruikt worden maar dat vergeet ik dus maar even.

De database engine zal inderdaad dat lijstje creeeren en opslaan in geheugen, maar dat lijstje is LANG, maar liefst orde M groot. Nou niet gaan doen alsof er maar een paar records in de forecast tabel staan. Het zoeken van een matching waarde in een lijstje van lengte M kost orde log(M). Als je dat N keer moet doen, kom ik nog steeds op orde N * log(M) tijd.

Een slimme optimizer zou je hash index moeten aanmaken voor tijdelijk gebruik op de tussenresultaten, dan is het gelijkwaardig aan de JOIN versie.

Verwijderd schreef op 04 november 2004 @ 23:58:
[...]

Ook is het niet zo dat je maar constant indexen kan blijven toevoegen om de meest vage velden te indexeren zodat al je queries optimaal lopen. Ook het bijhouden van een index kost tijd waardoor je insert, update en delete queries trager worden. Dus goede indexen verhogen de performance aanzienlijk maar zijn geen reden om de effectiviteit van je query te verwaarlozen noch een oplossing voor al je problemen. Deze query is dan ook een voorbeeld van een query die weinig voordeel heeft van indexen maar heel veel van een goede optimizer. Dat wil niet zeggen dat je geen indexen moet gebruiken, enkel dat er ook andere methoden zijn om goede performance te halen.

Dit is niet zomaar een rare plek om een index te plaatsen. Het is vrij normaal om indexen te plaatsen of foreign key velden, want die zul je altijd in JOINs nodig hebben. Anders moet je idd table scannen, en dat is dramatisch voor de performance. Alleen als je een tabel hebt waarop meer updates worden gerund dan selects, dan zou ik het niet doen, maar hoeveel van zulke tabellen heb je nou in de praktijk, behalve wat transactie en auditing tabellen.

[Verwijderd]

Je berekent de hash waarde, en je springt in de index naar die waarde. Dat kost orde 1 tijd

Eh, nee, dit is orde M. Je scant tenslotte de index om de juiste waarde te vinden.

Dus, worst case kost de JOIN met index orde N * (M / N) tijd, ofwel orde M. Best case is dat nog steeds orde N.

Ordes en best cases in 1 zin Ordes zijn bedoelt om een bovengrens aan te geven aan de mate van complexiteit. Best case ordes zijn dan ook onzin.

Daarnaast ben je een tabel aan het scannen voor meerdere waarden. Je weet pas of je klaar bent als je de complete tabel gehad hebt dus het scannen kost orde M. Het gebruik van de index maakt dus voor de orde niets uit en de verwachte zoektijd naar een enkel record M/N speelt al helemaal geen rol bij het orde verhaal.

Ik weet dat sommige mensen het scannen van een index Orde 1 geven omdat het zo stuk sneller is als het doorzoeken van de data. Echter, als je dat doet zul je ook andere processen die significant sneller zijn als het scannen van data Orde 1 moeten geven. Dit geldt dan ook voor het lijstje wat de dbengine genereert. Doe je het niet dan ben je appels met peren aan het vergelijken.

De database engine zal inderdaad dat lijstje creeeren en opslaan in geheugen, maar dat lijstje is LANG, maar liefst orde M groot. Nou niet gaan doen alsof er maar een paar records in de forecast tabel staan. Het zoeken van een matching waarde in een lijstje van lengte M kost orde log(M). Als je dat N keer moet doen, kom ik nog steeds op orde N * log(M) tijd.

Dit is dus het appels en peren verhaal. Het lijstje met lengte M doorzoeken kost tijd maar het scannen van een index met lengte M niet. Dit is inconsequent. Maak een keuze en wees daar consequent in. Mij maakt het vrij weinig uit of je het beide van de orde N vindt of een subquery van orde N*log(M) en de indexed join van order N*M vindt. In beide gevallen is de aan M gerelateerde tijd te verwaarlozen in vergelijking met de aan N gerelateerde tijd.

En dat indexen nuttig zijn is duidelijk, en op foreign keys zijn ze inderdaad vrij standaard. Echter in je vorige post schreef je:

De getallen spreken voor zichzelf. Indexen heersen boven subqueries, behalve als de subquery een heel kleine resultaat set oplevert

Dit soort opmerkingen is voor een hoop mensen een oproep om de database vol te gooien met indexen omdat een index aanmaken zo lekker simpel is en men de nadelen niet direct ziet. (Index corruptie, tragere updates e.d.)
Dus indexen zijn goed mits met mate gebruikt. (In dit geval zou ik waarschijnlijk sowieso een index op die foreign key zetten. Die zal wel vaker gebruikt worden)

Maar indexen heersen niet over wat voor query dan ook. Alle soorten queries hebben voordeel van indexen, maar een slecht geschreven query kan door indexen niet gered worden terwijl een goed geschreven query ook kan presteren zonder dat er een overvloed aan indexen nodig is.

Dus indexen of niet, ik begon dit omdat ik vind dat men bij het schrijven van queries meer moet nadenken over wat een optimizer ermee aan kan. En het is nou eenmaal zo dat onafhankelijke subqueries door een optimizer vaak effectiever worden geoptimaliseerd dan Outer Joins. Dus gegeven de keuze uit de twee opties in deze situatie zou ik altijd kiezen voor de versie met subquery (tenzij mySQL echt een hele belabberde optimizer heeft)

[Haploid]

Verwijderd schreef op 05 november 2004 @ 15:31:
[...]

Eh, nee, dit is orde M. Je scant tenslotte de index om de juiste waarde te vinden.

Nee, nee. Je berekent een hash waarde aan de hand van wat je dan ook wil opzoeken en deze hash waarde verwijst direct naar een entry in de index. Je hoeft die hash waarde niet op te zoeken in de index, het IS een pointer naar een positie in de index. Dat is juist de kracht van hash tabellen. In het ergste geval zijn er meerdere entries in de index met dezelfde hash waarde, die zitten dan in een linked listje of iets dergelijks.

[...]

Ordes en best cases in 1 zin Ordes zijn bedoelt om een bovengrens aan te geven aan de mate van complexiteit. Best case ordes zijn dan ook onzin.

Met de ordes geef je aan hoe de hoeveelheid berekeningen groeit ten opzichte van een of meer variablen. Dus, als iets orde N tijd kost, dan zal het geval met N=200 twee keer zoveel tijd kosten als het geval met N=100. Als iets orde N*N tijd kost,
dan zal het geval met N=200 vier keer zoveel tijd kosten als het geval met N=100.

In mijn berekening wist ik niet zeker hoe de optimizer om zou gaan met een bepaalde constructie, dus heb ik twee mogelijkheden behandeld. Een van beide is waar (voor een bepaalde server), ofwel de best ofwel de worst case.


Daarnaast ben je een tabel aan het scannen voor meerdere waarden. Je weet pas of je klaar bent als je de complete tabel gehad hebt dus het scannen kost orde M. Het gebruik van de index maakt dus voor de orde niets uit en de verwachte zoektijd naar een enkel record M/N speelt al helemaal geen rol bij het orde verhaal.

Ik weet dat sommige mensen het scannen van een index Orde 1 geven omdat het zo stuk sneller is als het doorzoeken van de data. Echter, als je dat doet zul je ook andere processen die significant sneller zijn als het scannen van data Orde 1 moeten geven. Dit geldt dan ook voor het lijstje wat de dbengine genereert. Doe je het niet dan ben je appels met peren aan het vergelijken.

Die snap ik niet helemaal. Ik geef het berekenen van een hash waarde orde 1 tijd omdat dat gewoon een vaste hoeveelheid tijd kost die niet groeit naar mate M of N toenemen. Dat lijstje wat de database bij de subquery maakt is nou eenmaal M lang en daarin iets opzoeken kan alleen in orde 1 tijd als er een hash tabel van wordt gemaakt.

Dit soort opmerkingen is voor een hoop mensen een oproep om de database vol te gooien met indexen omdat een index aanmaken zo lekker simpel is en men de nadelen niet direct ziet. (Index corruptie, tragere updates e.d.)
Dus indexen zijn goed mits met mate gebruikt. (In dit geval zou ik waarschijnlijk sowieso een index op die foreign key zetten. Die zal wel vaker gebruikt worden)

Ok, ik wilde ook niet aangeven dat je alles moet indexeren. Maar deze kolom in deze tabel zou ik zeker doen. Daar zijn we het over eens.

Dus indexen of niet, ik begon dit omdat ik vind dat men bij het schrijven van queries meer moet nadenken over wat een optimizer ermee aan kan. En het is nou eenmaal zo dat onafhankelijke subqueries door een optimizer vaak effectiever worden geoptimaliseerd dan Outer Joins. Dus gegeven de keuze uit de twee opties in deze situatie zou ik altijd kiezen voor de versie met subquery (tenzij mySQL echt een hele belabberde optimizer heeft)

Ik zal het je nog sterker vertellen. Ik heb op m'n werk even zitten experimenteren. Weliswaar onder SqlServer, maar goed, zal wel ongeveer gelijk zijn. Die koos voor beide oplossingen min of meer hetzelfde plan van aanpak (je kunt in SqlServer kijken hoe hij de query gaat opbouwen):

[subquery]
1. table scan van bedrijven (of index als die bestaat)
2. table scan van forecast (of index als die bestaat)
3. haal de distinct waardes uit (2)
4. merge join (1) en (3)
5. haal de distinct waardes uit (4)

[join]
1. table scan van bedrijven (of index als die bestaat)
2. table scan van forecast (of index als die bestaat)
3. merge join (1) en (2)
4. filter de null waardes eruit
5. haal de distinct waardes uit (4)

Dus, eigenlijk doet ie voor beide queries hetzelfde, een merge join. Ik heb ook wat testdata zitten proberen, maar de performance van beide queries scheelt vrij weinig. Misschien dat de subquery merkbaar sneller is als er veel forecasts zijn per bedrijf, omdat stap 3 dan de merge join aanzienlijk kleiner maakt.

[Verwijderd]

Nee, nee. Je berekent een hash waarde aan de hand van wat je dan ook wil opzoeken en deze hash waarde verwijst direct naar een entry in de index. Je hoeft die hash waarde niet op te zoeken in de index, het IS een pointer naar een positie in de index. Dat is juist de kracht van hash tabellen. In het ergste geval zijn er meerdere entries in de index met dezelfde hash waarde, die zitten dan in een linked listje of iets dergelijks.

Om maar eens een boek te quoten over database ontwerp (in het engels): (Fundamentals of db systems Third edition (ja ik ben oud) pagina 186)

It is possible to create indexes that are based on hashing. The index entries (K, pr) can be organised as a dynamic expandible hash file searching for an entry using the hash search algoritm on K Once the entry is found the pointer Pr is used to locate the corresponding record in the data file

Dus zodra je de pointer Pr hebt gevonden weet je waar de data staat. Echter, je moet eerst de hash file doorzoeken om de pointer Pr te vinden. Dit doorzoeken van de hash file is van de orde M.

Ik zal het je nog sterker vertellen. Ik heb op m'n werk even zitten experimenteren. Weliswaar onder SqlServer, maar goed, zal wel ongeveer gelijk zijn. Die koos voor beide oplossingen min of meer hetzelfde plan van aanpak (je kunt in SqlServer kijken hoe hij de query gaat opbouwen):

De perfecte optimizer zal een join en subquery precies hetzelfde afhandelen. Het probleem zit hem in de wat minder perfecte optimizers, voor die optimizers is het stukken makkelijker om een onafhankelijke subquery correct af te handelen dan een outer join. Ik heb verschillende databases (MS SQL Server, Oracle, DB2, Interbase, ....) de mist in zien gaan bij het bepalen van het beste plan voor een query. Meestal bij het gebruik van complexere joins terwijl subqueries, en al helemaal onafhankelijke subqueries, geen problemen op leverden.

[ Voor 17% gewijzigd door Verwijderd op 06-11-2004 04:20 ]

[Haploid]

Verwijderd schreef op 06 november 2004 @ 04:14:
[...]
Om maar eens een boek te quoten over database ontwerp (in het engels): (Fundamentals of db systems Third edition (ja ik ben oud) pagina 186)

Wat is oud? Ik heb de second edition Als je kijkt in wat bij mij hoofdstuk 4.8 heet (Hashing Techniques), dan zeggen ze daar:

The idea behind hashing is to provide a function h, called a hash function or randomizing function, that is applied to the hash field value of a record and yields the address of the disk block in which the record is stored. [...] For most records, we need only a single block access to retreive that record.

Eigenlijk staat hashen een beetje kort beschreven in het boek, maar op deze site http://ciips.ee.uwa.edu.a.../PLDS210/hash_tables.html staat een keurige gedetailleerde omschrijving. Er is zelfs een mooie animatie te vinden onderaan de pagina Ik quote nog even een paar regeltjes uit de tekst:

The direct address approach requires that the function, h(k), is a one-to-one mapping from each k to integers in (1,m). Such a function is known as a perfect hashing function: it maps each key to a distinct integer within some manageable range and enables us to trivially build an O(1) search time table.

Unfortunately, finding a perfect hashing function is not always possible. Let's say that we can find a hash function, h(k), which maps most of the keys onto unique integers, but maps a small number of keys on to the same integer. If the number of collisions (cases where multiple keys map onto the same integer), is sufficiently small, then hash tables work quite well and give O(1) search times.

En weer een quoteje van jou:

Dus zodra je de pointer Pr hebt gevonden weet je waar de data staat. Echter, je moet eerst de hash file doorzoeken om de pointer Pr te vinden. Dit doorzoeken van de hash file is van de orde M.

Je hoeft helemaal geen file door te zoeken. Je berekent de hash waarde voor een bepaalde BedrijfID en die hash waarde geeft aan in welk blok op de schijf je record staat.

De perfecte optimizer zal een join en subquery precies hetzelfde afhandelen. Het probleem zit hem in de wat minder perfecte optimizers, voor die optimizers is het stukken makkelijker om een onafhankelijke subquery correct af te handelen dan een outer join. Ik heb verschillende databases (MS SQL Server, Oracle, DB2, Interbase, ....) de mist in zien gaan bij het bepalen van het beste plan voor een query. Meestal bij het gebruik van complexere joins terwijl subqueries, en al helemaal onafhankelijke subqueries, geen problemen op leverden.

Oh zeker, ze kunnen soms rare dingen doen. Maar dit voorbeeld is een vrij simpele query, dat moet toch wel lukken, toch?