04 mei 2025·8 min
Jeffrey Ullmans databasetheorie achter snelle, schaalbare queries
Hoe Jeffrey Ullmans kernideeën moderne databases aandrijven: relationele algebra, optimalisatieregels, joins en compiler-achtige planning die systemen helpt schalen.
Hoe Jeffrey Ullmans kernideeën moderne databases aandrijven: relationele algebra, optimalisatieregels, joins en compiler-achtige planning die systemen helpt schalen.
De meeste mensen die SQL schrijven, dashboards maken of een trage query tunen hebben baat gehad bij het werk van Jeffrey Ullman — zelfs als ze zijn naam nooit gehoord hebben. Ullman is een computerwetenschapper en docent wiens onderzoek en studieboeken hebben bepaald hoe databases data beschrijven, over queries redeneren en ze efficiënt uitvoeren.
Wanneer een database-engine je SQL omzet naar iets dat snel draait, leunt die op ideeën die zowel precies als aanpasbaar moeten zijn. Ullman hielp de betekenis van queries te formaliseren (zodat het systeem ze veilig kan herschrijven) en bracht database-denken in verband met compiler-denken (zodat een query geparsed, geoptimaliseerd en vertaald kan worden naar uitvoerbare stappen).
Die invloed is stil omdat ze niet verschijnt als een knop in je BI-tool of als een zichtbare functie in je cloudconsole. Ze verschijnt als:
JOIN herschrijftDit artikel gebruikt Ullmans kernideeën als een rondleiding door database-interne onderdelen die in de praktijk het meest belangrijk zijn: hoe relationele algebra onder SQL ligt, hoe query-herschrijvingen betekenis behouden, waarom kosten-gebaseerde optimizers de keuzes maken die ze maken, en hoe join-algoritmen vaak bepalen of een taak in seconden of uren klaar is.
We halen ook een paar compiler-achtige concepten binnen — parsen, herschrijven en plannen — omdat database-engines meer op geavanceerde compilers lijken dan veel mensen denken.
Een korte belofte: we houden de discussie nauwkeurig, maar vermijden wiskundige bewijzen. Het doel is mentale modellen te geven die je de volgende keer dat prestaties, schaal of verwarrend query-gedrag opduikt op het werk kunt toepassen.
Als je ooit een SQL-query hebt geschreven en verwacht dat die "gewoon één ding betekent", vertrouw je op ideeën die Jeffrey Ullman hielp populariseren en formaliseren: een helder model voor data, plus precieze manieren om te beschrijven wat een query vraagt.
In kern beschouwt het relationele model data als tabellen (relaties). Elke tabel heeft rijen (tuples) en kolommen (attributen). Dat klinkt nu vanzelfsprekend, maar het belangrijkste is de discipline die het creëert:
Deze manier van kijken maakt het mogelijk om over correctheid en prestaties te redeneren zonder te sussen. Als je weet wat een tabel vertegenwoordigt en hoe rijen geïdentificeerd worden, kun je voorspellen wat joins zouden moeten doen, wat duplicaten betekenen en waarom bepaalde filters resultaten veranderen.
Ullmans lesmateriaal gebruikt vaak relationele algebra als een soort query-calculator: een kleine set bewerkingen (selectie, projectie, join, unie, verschil) die je kunt combineren om uit te drukken wat je wilt.
Waarom het uitmaakt voor werken met SQL: databases vertalen SQL naar een algebraïsche vorm en herschrijven die vervolgens naar een equivalente vorm. Twee queries die er anders uitzien kunnen algebraïsch hetzelfde zijn — en zo kunnen optimizers joins herschikken, filters naar beneden duwen of onnodig werk verwijderen terwijl de betekenis blijft.
SQL is grotendeels “wat”, maar engines optimaliseren vaak met algebraïsche “hoe”-vormen.
SQL-dialecten verschillen (Postgres vs. Snowflake vs. MySQL), maar de fundamenten niet. Begrijpen van sleutels, relaties en algebraïsche equivalentie helpt je zien wanneer een query logisch fout is, wanneer ze alleen traag is en welke wijzigingen de betekenis behouden over platforms heen.
Relationele algebra is de “wiskunde onder” SQL: een kleine set operatoren die beschrijven welk resultaat je wilt. Jeffrey Ullmans werk maakte deze operator-werkwijze scherp en leerbaar — en het is nog steeds het mentale model dat de meeste optimizers gebruiken.
Een databasequery kan worden uitgedrukt als een pijplijn van een paar bouwstenen:
WHERE)SELECT col1, col2)JOIN ... ON ...)UNION)EXCEPT in veel SQL-dialecten)Omdat de set klein is, wordt het eenvoudiger om over correctheid te redeneren: als twee algebra-expressies equivalent zijn, geven ze voor elke geldige databasetoestand dezelfde tabel terug.
Neem een bekende query:
SELECT c.name
FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE o.total > 100;
Conceptueel is dit:
begin met een join van customers en orders: customers ⋈ orders
selecteer alleen orders boven 100: σ(o.total > 100)(...)
projecteer de ene kolom die je wilt: π(c.name)(...)
Dat is niet de exacte interne notatie die elke engine gebruikt, maar het is het juiste idee: SQL wordt een operatorboom.
Verschillende bomen kunnen hetzelfde betekenen. Filters kunnen vaak eerder worden toegepast (pas σ toe vóór een grote join), en projecties kunnen ongebruikte kolommen eerder weggooien (pas π eerder toe).
Die equivalentieregels laten een database je query herschrijven naar een goedkoper plan zonder de betekenis te veranderen. Zodra je queries als algebra ziet, stopt “optimalisatie” met magie en wordt het een veilige, op regels gebaseerde herstructurering.
Als je SQL schrijft, voert de database het niet “zoals geschreven” uit. Ze zet je statement om in een queryplan: een gestructureerde representatie van het werk dat gedaan moet worden.
Een goed mentaal model is een boom van operatoren. Bladeren lezen tabellen of indexen; interne knopen transformeren en combineren rijen. Veelvoorkomende operatoren zijn scan, filter (selectie), project (kolomkeuze), join, group/aggregate en sort.
Databases scheiden planning vaak in twee lagen:
Ullmans invloed zie je in de nadruk op betekenisbehoudende transformaties: herschik het logische plan op veel manieren zonder het antwoord te veranderen, en kies daarna een efficiënte fysieke strategie.
Voordat de engine de uiteindelijke uitvoeringsaanpak kiest, past de optimizer algebraïsche “schoonmaak”-regels toe. Deze herschrijvingen veranderen het resultaat niet; ze verminderen onnodig werk.
Veelvoorkomende voorbeelden:
Stel dat je orders wilt voor gebruikers in één land:
SELECT o.order_id, o.total
FROM users u
JOIN orders o ON o.user_id = u.id
WHERE u.country = 'CA';
Een naïeve interpretatie zou alle gebruikers joinen met alle orders en daarna filteren op Canada. Een betekenisbehoudende herschrijving duwt de filter naar beneden zodat de join minder rijen raakt:
country = 'CA'order_id en totalIn planten termen probeert de optimizer dit te veranderen van:
Join(Users, Orders) → Filter(country='CA') → Project(order_id,total)
naar iets als:
Filter(country='CA') on Users → Join(with Orders) → Project(order_id,total)
Zelfde antwoord. Minder werk.
Deze herschrijvingen zijn makkelijk over het hoofd te zien omdat je ze nooit intypt—maar ze zijn een hoofdreden dat dezelfde SQL snel op de ene database kan draaien en traag op een andere.
Als je een SQL-query uitvoert, overweegt de database meerdere geldige manieren om hetzelfde antwoord te krijgen en kiest vervolgens degene die ze het goedkoopst verwacht. Dat beslissingsproces heet kosten-gebaseerde optimalisatie—en het is één van de meest praktische plekken waar Ullman-achtige theorie dagelijks terugkomt.
Een kostmodel is een scoresysteem dat de optimizer gebruikt om alternatieve plannen te vergelijken. De meeste engines schatten kosten met een paar kernbronnen:
Het model hoeft niet perfect te zijn; het moet vaak genoeg richtinggevend juist zijn om goede plannen te kiezen.
Voordat het plannen kan scoren, stelt de optimizer bij elke stap de vraag: hoeveel rijen zal dit opleveren? Dat is cardinality estimation.
Als je filtert met WHERE country = 'CA', schat de engine welk deel van de tabel matcht. Als je klanten en orders joinet, schat ze hoeveel paren er op de join-sleutel matchen. Die rijaantal-gissingen bepalen of ze een indexscan verkiest boven een volledige scan, een hash join boven een nested loop, of dat een sort klein of enorm zal zijn.
De schattingen van de optimizer worden aangedreven door statistieken: aantallen, waardeverdelingen, null-percentages en soms correlaties tussen kolommen.
Als statistieken verouderd of afwezig zijn, kan de engine rijaantallen met veelvoud fout inschatten. Een plan dat goedkoop lijkt op papier kan in de praktijk duur blijken—klassieke symptomen zijn plotselinge vertragingen na datagroei, “willekeurige” planwisselingen of joins die onverwacht naar schijf moeten uitwijken.
Betere schattingen vereisen vaak meer werk: gedetailleerdere stats, sampling of het verkennen van meer kandidaat-plannen. Maar plannen kost zelf ook tijd, vooral voor complexe queries.
Dus optimizers balanceren twee doelen:
Dat inzicht helpt je EXPLAIN-output te interpreteren: de optimizer probeert niet sluw te zijn—hij probeert onder beperkte informatie voorspelbaar juist te zijn.
Ullmans werk hielp een eenvoudig maar krachtig idee populair maken: SQL wordt niet zozeer “gedraaid” als wel vertaald naar een uitvoeringsplan. Nergens is dat duidelijker dan bij joins. Twee queries die dezelfde rijen teruggeven kunnen enorm verschillen in uitvoeringstijd afhankelijk van welk join-algoritme de engine kiest — en in welke volgorde tabellen worden gejoined.
Nested loop join is conceptueel eenvoudig: voor elke rij aan de linkerkant zoek je bijpassende rijen aan de rechterkant. Het kan snel zijn wanneer de linkerkant klein is en de rechterkant een bruikbare index heeft.
Hash join bouwt een hashtabel van één input (vaak de kleinere) en proeft die met de andere. Het blinkt uit bij grote, ongesorteerde inputs met gelijkheidscondities (bijv. A.id = B.id), maar heeft geheugen nodig; uitwisseling naar schijf kan het voordeel tenietdoen.
Merge join loopt twee inputs af in sorteervolgorde. Het is een goede keuze wanneer beide kanten al gesorteerd zijn (of goedkoop te sorteren), zoals wanneer indexen rijen in join-key volgorde leveren.
Bij drie of meer tabellen explodeert het aantal mogelijke join-volgorden. Twee grote tabellen eerst joinen kan een enorm tussenresultaat opleveren dat alles vertraagt. Een betere volgorde begint vaak met het meest selectieve filter (weinigste rijen) en joinet naar buiten toe, zodat tussenresultaten klein blijven.
Indexen versnellen niet alleen opzoekingen — ze maken bepaalde joinstrategieën mogelijk. Een index op de join-sleutel kan een dure nested loop veranderen in een snelle “seek per rij”-patroon. Ontbrekende of onbruikbare indexen kunnen de engine dwingen tot hash joins of grote sorts voor merge joins.
Databases "runnen" SQL niet zomaar. Ze compileren het. Ullmans invloed bestrijkt zowel databasetheorie als compiler-denken, en die verbinding verklaart waarom query-engines zich gedragen als toolchains voor programmeertalen: ze vertalen, herschrijven en optimaliseren voordat er werk wordt gedaan.
Als je een query verstuurt, lijkt de eerste stap op de front-end van een compiler. De engine tokeniseert keywords en identifiers, controleert grammatica en bouwt een parse tree (vaak vereenvoudigd naar een abstract syntax tree). Hier worden basisfouten opgevangen: ontbrekende komma's, dubbelzinnige kolomnamen, ongeldige GROUP BY-regels.
Een nuttig mentaal model: SQL is een programmeertaal waarvan het “programma” toevallig datarelaties beschrijft in plaats van lussen.
Compilers zetten syntaxis om naar een tussenrepresentatie (IR). Dat doen databases ook: ze vertalen SQL-syntaxis naar logische operatoren zoals:
GROUP BY)Die logische vorm ligt dichter bij relationele algebra dan bij SQL-tekst, wat het makkelijker maakt om over betekenis en equivalentie te redeneren.
Compileroptimalisaties houden programmaresultaten identiek terwijl uitvoer goedkoper wordt. Database-optimizers doen hetzelfde met regelsystemen zoals:
Dat is de databasevariant van “dead code elimination”: niet identieke technieken, maar dezelfde filosofie — behoud semantiek, verlaag kosten.
Als je query traag is, kijk dan niet alleen naar SQL. Bekijk het queryplan zoals je compiler-output zou inspecteren. Een plan vertelt je wat de engine daadwerkelijk koos: join-volgorde, indexgebruik en waar tijd wordt besteed.
Praktische conclusie: leer EXPLAIN-output lezen als een prestatie-"assembly listing". Het maakt tunen van gokken naar evidence-based debugging. Voor meer over hoe je dat een gewoonte maakt: zie practical-query-optimization-habits.
Goede query-prestaties beginnen vaak voordat je SQL schrijft. Ullmans schema-ontwerptheorie (vooral normalisatie) gaat over data zó structureren dat de database correct, voorspelbaar en efficiënt blijft naarmate het groeit.
Normalisatie streeft naar:
Die correctheidswinst vertaalt zich later in prestatievoordelen: minder gedupliceerde velden, kleinere indexen en minder dure updates.
Je hoeft geen bewijzen te onthouden om de ideeën te gebruiken:
Denormalisatie kan verstandig zijn wanneer:
Het belangrijkste is doelbewust denormaliseren, met een proces om duplicaten synchroon te houden.
Schema-ontwerp bepaalt wat de optimizer kan doen. Duidelijke sleutels en foreign keys maken betere joinstrategieën, veiligere herschrijvingen en nauwkeurigere rijaantal-schattingen mogelijk. Tegelijkertijd kan overmatige duplicatie indexen opblazen en writes vertragen, en multi-waarde kolommen blokkeren efficiënte predicaten. Naarmate data groeit, blijken deze vroege modelkeuzes vaak belangrijker dan micro-optimalisaties van één enkele query.
Wanneer een systeem "schaalt", gaat het zelden alleen om grotere machines. Vaak is het lastige dat dezelfde querybetekenis bewaard moet blijven terwijl de engine een heel andere fysieke strategie kiest om runtimes voorspelbaar te houden. Ullmans nadruk op formele equivalenties is precies wat die strategiewijzigingen mogelijk maakt zonder resultaten te veranderen.
Bij kleine datasets werken veel plannen. Bij schaal kan het verschil tussen een tabel scannen, een index gebruiken of een voorgecomputeerd resultaat gebruiken het verschil betekenen tussen seconden en uren. De theoretische kant is belangrijk omdat de optimizer een veilige set herschrijvingsregels nodig heeft (bijv. filters naar voren duwen, joins herordenen) die het antwoord niet veranderen — zelfs als ze het werk radicaal veranderen.
Partitionering (op datum, klant, regio, enz.) verandert één logische tabel in veel fysieke stukken. Dat beïnvloedt planning:
De SQL-tekst kan ongewijzigd blijven, maar het beste plan hangt nu af van waar de rijen fysiek liggen.
Materialized views zijn in wezen “opgeslagen subexpressies.” Als de engine kan bewijzen dat je query overeenkomt met (of herschreven kan worden naar) een opgeslagen resultaat, kan hij duur werk vervangen door een snelle lookup. Dit is relationele algebra in de praktijk: equivalente expressies herkennen en dan hergebruiken.
Caching versnelt herhaalde reads, maar lost geen query op die te veel data moet scannen, enorme tussenresultaten moet shufflen of een gigantische join moet berekenen. Bij schaalproblemen is de oplossing vaak: reduceer de hoeveelheid data die geraakt wordt (lay-out/partitionering), verminder herhaald werk (materialized views) of verander het plan — niet alleen “meer cache.”
Ullmans invloed zie je in één praktische ingesteldheid: behandel een trage query als een intentieverklaring die de database vrij is te herschrijven, en verifieer vervolgens wat hij daadwerkelijk heeft besloten te doen. Je hoeft geen theoreticus te zijn om te profiteren — je hebt alleen een herhaalbare routine nodig.
Begin met de onderdelen die meestal runtime domineren:
Als je maar één ding doet: identificeer de eerste operator waar het aantal rijen explodeert. Dat is meestal de kernoorzaak.
Deze zijn makkelijk te schrijven en verrassend kostbaar:
WHERE LOWER(email) = ... kan indexgebruik voorkomen (gebruik een genormaliseerde kolom of een functionele index als ondersteund).Relationele algebra moedigt twee praktische stappen aan:
WHERE-condities toe vóór joins waar mogelijk om inputs te verkleinen.Een goede hypothese klinkt als: “Deze join is duur omdat we te veel rijen joinen; als we orders eerst filteren op de laatste 30 dagen, daalt de join-input.”
Gebruik een eenvoudige beslisregel:
EXPLAIN vermijdbaar werk toont (onnodige joins, late filtering, non-sargable predicaten).Het doel is geen “slimme SQL”, maar voorspelbaar kleinere tussenresultaten — precies de soort equivalence-preserving verbeteringen die Ullmans ideeën makkelijker maken om te herkennen.
Deze concepten zijn niet alleen voor databasebeheerders. Als je een applicatie uitbrengt, maak je database- en query-planningsbeslissingen of je het weet: schema-vorm, sleutelkeuzes, query-patronen en de data-accesslaag beïnvloeden allemaal wat de optimizer kan doen.
Als je een vibe-coding workflow gebruikt (bijvoorbeeld het genereren van een React + Go + PostgreSQL-app vanuit een chatinterface in Koder.ai), zijn Ullman-achtige mentale modellen een praktisch vangnet: je kunt het gegenereerde schema controleren op schone sleutels en relaties, de queries bekijken waarop je app vertrouwt, en prestaties valideren met EXPLAIN voordat problemen in productie verschijnen. Hoe sneller je kunt itereren op “query-intentie → plan → fix”, hoe meer waarde je krijgt van versnelde ontwikkeling.
Je hoeft theorie niet als een losse hobby te bestuderen. De snelste manier om te profiteren van Ullman-achtige fundamenten is genoeg leren om queryplannen vol vertrouwen te lezen — en daarna oefenen in je eigen database.
Zoek naar deze boeken en lectuuronderwerpen (geen affiliatie — gewoon breed geciteerde startpunten):
Begin klein en koppel elke stap aan iets dat je kunt waarnemen:
Kies 2–3 echte queries en iterereer:
IN naar EXISTS, duw predicaten eerder, verwijder onnodige kolommen, vergelijk resultaten.Gebruik duidelijke, plan-gebaseerde taal:
Dat is de praktische winst van Ullmans fundamenten: je krijgt een gedeelde woordenschat om prestaties uit te leggen — zonder te gokken.
Jeffrey Ullman heeft geholpen te formaliseren hoe databases de betekenis van queries beschrijven en hoe ze queries veilig kunnen transformeren naar sneller uitvoerbare vormen. Die fundering zie je elke keer dat een engine een query herschrijft, joins herordent of een andere uitvoering kiest terwijl het resultaat gelijk blijft.
Relationele algebra is een compacte set operatoren (selectie, projectie, join, unie, verschil) die precies beschrijven welke resultaten een query moet geven. Engines vertalen SQL vaak naar een algebra-achtige operatorboom zodat ze equivalentieregels (zoals filters naar voren schuiven) kunnen toepassen voordat ze een uitvoeringsstrategie kiezen.
Omdat optimalisatie afhankelijk is van het bewijzen dat een herschreven query hetzelfde resultaat oplevert. Equivalentieregels laten de optimizer dingen doen zoals:
WHERE-filters vóór een join plaatsenDeze wijzigingen kunnen de hoeveelheid werk drastisch verminderen zonder de betekenis te veranderen.
Een logisch plan beschrijft wat er moet gebeuren (filter, join, aggregaat) onafhankelijk van opslagdetails. Een fysiek plan kiest hoe dat uitgevoerd wordt (indexscan vs volledige scan, hash join vs nested loop, parallelisme, sorteerstrategieën). De meeste prestatieverschillen ontstaan door fysieke keuzes die mogelijk worden gemaakt door logische herschrijvingen.
Kosten-gebaseerde optimalisatie vergelijkt meerdere geldige plannen en kiest degene met de laagste geschatte kosten. Kosten worden meestal bepaald door praktische factoren zoals hoeveelheid verwerkte rijen, I/O, CPU en geheugen (bijvoorbeeld of een hash of sorteren naar schijf moet uitwijken).
Cardinaliteitschattning is de inschatting van de optimizer: “hoeveel rijen komt dit stapje eruit?” Die schattingen bepalen joinvolgorde, jointype en of een indexscan de moeite waard is. Wanneer schattingen verkeerd zijn (vaak door verouderde of ontbrekende statistieken) kun je plotselinge vertragingen, grote spills of verrassende planwisselingen krijgen.
Richt je op een paar signalen met hoge informatiewaarde:
Zie het plan als gecompileerde output: het laat zien wat de engine daadwerkelijk gekozen heeft.
Normalisatie vermindert gedupliceerde feiten en update-anomalieën, wat vaak resulteert in kleinere tabellen en indexen en betrouwbaardere joins. Denormalisatie kan toch de juiste keuze zijn voor analytics of herhaalde leesintensieve patronen, maar doe het doelbewust (met duidelijke verversregels en beheerde duplicatie) zodat correctheid niet wegzakt.
Schaalbaarheid vereist vaak een andere fysieke strategie terwijl de querybetekenis identiek blijft. Veelgebruikte middelen zijn:
Caching helpt herhaalde reads, maar lost geen probleem op wanneer een query te veel data moet aanraken of enorme tussenjoins produceert.