04 maj 2025·8 min
Jeffrey Ullmans databasteori bakom snabba, skalbara frågor
Hur Jeffrey Ullmans kärnidéer driver moderna databaser: relationsalgebra, optimeringsregler, joins och kompilatorlik planering som hjälper system att skala.
Hur Jeffrey Ullmans kärnidéer driver moderna databaser: relationsalgebra, optimeringsregler, joins och kompilatorlik planering som hjälper system att skala.
De flesta som skriver SQL, bygger dashboards eller finjusterar en långsam fråga har haft nytta av Jeffrey Ullmans arbete—även om de aldrig hört hans namn. Ullman är en datavetare och pedagog vars forskning och läroböcker hjälpte till att definiera hur databaser beskriver data, resonerar om frågor och exekverar dem effektivt.
När en databasmotor omvandlar din SQL till något den kan köra snabbt, förlitar den sig på idéer som måste vara både precisa och anpassningsbara. Ullman hjälpte till att formalisera betydelsen av frågor (så systemet kan omskriva dem säkert) och kopplade ihop databastänkande med kompilatortänkande (så en fråga kan parsas, optimeras och översättas till exekverbara steg).
Det inflytandet är tyst eftersom det inte syns som en knapp i ditt BI-verktyg eller en synlig funktion i din molnkonsol. Det syns som:
JOINDen här texten använder Ullmans kärnidéer som en guidad rundtur i de databasinterna som är mest användbara i praktiken: hur relationsalgebra ligger under SQL, hur omskrivningar bevarar betydelse, varför kostnadsbaserade optimerare gör de val de gör, och hur join-algoritmer ofta avgör om ett jobb blir klart på sekunder eller timmar.
Vi tar också med några kompilatorlika begrepp—parsning, omskrivning och planering—eftersom databasmotorer beter sig mer som sofistikerade kompilatorer än många inser.
Ett snabbt löfte: vi håller diskussionen korrekt men undviker tung matematik. Målet är att ge mentala modeller du kan använda på jobbet nästa gång prestanda, skalning eller förvirrande frågebeteende dyker upp.
Om du någonsin skrivit en SQL-fråga och förväntat dig att den "bara betyder en sak", litar du på idéer som Jeffrey Ullman hjälpte popularisera och formalisera: en tydlig modell för data, plus precisa sätt att beskriva vad en fråga efterfrågar.
I grunden behandlar relationsmodellen data som tabeller (relationer). Varje tabell har rader (tupler) och kolumner (attribut). Det låter självklart nu, men det viktiga är den disciplin det skapar:
Denna inramning gör det möjligt att resonera om korrekthet och prestanda utan vagt prat. När du vet vad en tabell representerar och hur rader identifieras kan du förutse vad joins gör, vad dubbletter betyder och varför vissa filter ändrar resultat.
Ullmans undervisning använder ofta relationsalgebra som en sorts frågeräknare: en liten uppsättning operationer (select, project, join, union, difference) som du kan kombinera för att uttrycka vad du vill ha.
Varför det spelar roll för SQL: databaser översätter SQL till en algebraisk form och omsyrer den till en ekvivalent form. Två frågor som ser olika ut kan vara algebraiskt lika—det är så optimerare kan ändra join-ordning, skjuta ner filter eller ta bort överflödigt arbete samtidigt som betydelsen bevaras.
SQL är till stor del "vad", men motorer optimerar ofta med algebraiskt "hur".
SQL-dialekter varierar (Postgres vs. Snowflake vs. MySQL), men grunderna gör det inte. Att förstå nycklar, relationer och algebraisk ekvivalens hjälper dig se när en fråga är logiskt fel, när den bara är långsam och vilka ändringar som bevarar betydelsen mellan plattformar.
Relationsalgebra är "maten under" SQL: en liten uppsättning operatorer som beskriver det resultat du vill ha. Jeffrey Ullmans arbete hjälpte göra denna operatorvy skarp och lärbar—och det är fortfarande den mentala modell de flesta optimerare använder.
En databasfråga kan uttryckas som en pipeline av några byggstenar:
WHERE)SELECT col1, col2)JOIN ... ON ...)UNION)EXCEPT)Eftersom mängden är liten blir det lättare att resonera om korrekthet: om två algebraiska uttryck är ekvivalenta returnerar de samma tabell för varje giltigt databastillstånd.
Ta en bekant fråga:
SELECT c.name
FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE o.total > 100;
Konceptuellt är detta:
börja med en join av customers och orders: customers ⋈ orders
select bara orders över 100: σ(o.total > 100)(...)
project den kolumn du vill ha: π(c.name)(...)
Det är inte exakt den interna notation alla motorer använder, men det är rätt idé: SQL blir ett operatorträd.
Många olika träd kan betyda samma resultat. Till exempel kan filter ofta skjutas tidigare (tillämpa σ före en stor join) och projektioner kan ta bort oanvända kolumner tidigare (tillämpa π tidigare).
Dessa ekvivalensregler är vad som låter en databas omskriva din fråga till en billigare plan utan att ändra betydelsen. När du ser frågor som algebra slutar “optimering” vara magi och blir säker, regelstyrd omformning.
När du skriver SQL exekveras den inte "som skrivet". Den översätts till en frågeplan: en strukturerad representation av arbetet som ska göras.
En bra mental modell är ett träd av operatorer. Löven läser tabeller eller index; interna noder transformerar och kombinerar rader. Vanliga operatorer inkluderar scan, filter (selection), project (välj kolumner), join, group/aggregate och sort.
Databaser separerar vanligtvis planering i två lager:
Ullmans inflytande syns i betoningen på meningsbevarande transformationer: omforma den logiska planen på många sätt utan att ändra svaret, för att sedan välja en effektiv fysisk strategi.
Innan man väljer slutlig exekveringsmetod tillämpar optimerare algebraiska "städregler". Dessa omskrivningar ändrar inte resultat; de minskar onödigt arbete.
Vanliga exempel:
Anta att du vill ha orders för användare i ett land:
SELECT o.order_id, o.total
FROM users u
JOIN orders o ON o.user_id = u.id
WHERE u.country = 'CA';
En naiv tolkning skulle kunna join:a alla users med alla orders och sedan filtrera till Kanada. En meningsbevarande omskrivning skjuter ner filtret så att join:n berör färre rader:
country = 'CA'order_id och totalI planterm blir det att optimizern försöker förändra:
Join(Users, Orders) → Filter(country='CA') → Project(order_id,total)
till något närmare:
Filter(country='CA') on Users → Join(with Orders) → Project(order_id,total)
Samma svar. Mindre arbete.
Dessa omskrivningar är lätta att förbise eftersom du aldrig skriver dem—ändå är de en stor anledning till att samma SQL kan köra snabbt på en databas och långsamt på en annan.
När du kör en SQL-fråga överväger databasen flera giltiga sätt att få samma svar och väljer sedan det den tror blir billigast. Den processen kallas kostnadsbaserad optimering—och det är en av de mest praktiska platser där Ullman-lik teori syns i vardaglig prestanda.
En kostnadsmodell är ett poängsystem optimeraren använder för att jämföra alternativa planer. De flesta motorer uppskattar kostnad med några kärnresurser:
Modellen behöver inte vara perfekt; den behöver vara riktigare ofta nog för att välja bra planer.
Innan den kan poängsätta planer ställer optimeraren en fråga i varje steg: hur många rader kommer detta ge? Det är kardinalitetsestimering.
Om du filtrerar WHERE country = 'CA' uppskattar motorn vilken andel av tabellen som matchar. Om du joinar customers mot orders uppskattar den hur många par som matchar på join-nyckeln. Dessa radskattningar avgör om den föredrar indexscan framför full scan, hash join framför nested loop, eller om en sort blir liten eller enorm.
Optimerarens gissningar drivs av statistik: räkningar, värdefördelningar, andel null-värden och ibland korrelationer mellan kolumner.
När statistik är föråldrade eller saknas kan motorn missta sig på radantal med flera storleksordningar. En plan som ser billig ut på papper kan bli dyr i verkligheten—klassiska symptom är plötsliga förlängningar efter dataväxt, "slumpmässiga" planändringar eller joins som oväntat spillas till disk.
Bättre uppskattningar kräver ofta mer arbete: mer detaljerad statistik, sampling eller att utforska fler kandidatplaner. Men planering kostar tid, särskilt för komplexa frågor.
Så optimerare balanserar två mål:
Att förstå den avvägningen hjälper dig tolka EXPLAIN-utdata: optimeraren försöker inte vara listig—den vill vara förutsägbart korrekt under begränsad information.
Ullmans arbete hjälpte popularisera en enkel men kraftfull idé: SQL körs inte så mycket som den översätts till en exekveringsplan. Inget visar det bättre än joins. Två frågor som returnerar samma rader kan skilja sig enormt i körtid beroende på vilken join-algoritm motorn väljer—och i vilken ordning tabellerna joinas.
Nested loop join är konceptuellt enkel: för varje rad på vänstersidan hitta matchande rader på högersidan. Den kan vara snabb när vänstersidan är liten och högersidan har ett användbart index.
Hash join bygger en hashtabell från en input (ofta den mindre) och probas av den andra. Den är stark för stora, osorterade inputs med likhetsvillkor (t.ex. A.id = B.id), men kräver minne; spillning till disk kan radera fördelen.
Merge join går igenom två inputs i sorterad ordning. Den passar när båda sidor redan är ordnade (eller billigt sorterade), som när index kan leverera rader i join-nyckelordning.
Med tre eller fler tabeller exploderar antalet möjliga join-ordningar. Att joina två stora tabeller först kan skapa ett enormt mellanresultat som saktar ner allt annat. En bättre ordning börjar ofta med det mest selektiva filtret (färre rader) och joinar utåt för att hålla mellanresultat små.
Index gör mer än snabbar upp uppslag—de gör vissa join-strategier möjliga. Ett index på join-nyckeln kan förändra en kostsam nested loop till en snabb "seek per rad"-pattern. Om index saknas eller är otillgängliga kan motorn istället välja hash joins eller stora sorteringar för merge joins.
Databaser kör inte bara SQL. De kompilerar den. Ullmans inflytande spänner över både databasteori och kompilatortänk, och den kopplingen förklarar varför frågemotorer beter sig som språkverktygskedjor: de översätter, omskriver och optimerar innan de gör något arbete.
När du skickar en fråga liknar första steget en kompilators front-end. Motorn tokeniserar nyckelord och identifierare, kontrollerar grammatik och bygger ett parse tree (ofta förenklat till ett abstract syntax tree). Här fångas grundläggande fel: saknade kommatecken, tvetydiga kolumnnamn, ogiltiga grouping-regler.
En hjälpsam mental modell: SQL är ett programmeringsspråk vars "program" råkar beskriva dat relationer istället för loopar.
Kompilatorer konverterar syntax till en mellanrepresentation (IR). Databaser gör något liknande: de översätter SQL-syntax till logiska operatorer såsom:
GROUP BY)Denna logiska form ligger närmare relationsalgebra än SQL-text, vilket gör det lättare att resonera om betydelse och ekvivalens.
Kompilatoroptimeringar behåller programresultatet identiskt samtidigt som de gör exekveringen billigare. Databasoptimerare gör samma sak, med regelbaserade system som:
Detta är databasversionen av "dead code elimination": inte identiska tekniker, men samma filosofi—bevara semantik, minska kostnad.
Om din fråga är långsam, stirra inte bara på SQL. Titta på frågeplanen som du skulle granska kompilerad kod. En plan visar vad motorn faktiskt valde: join-ordning, index-användning och var tiden spenderas.
Praktisk slutsats: lär dig läsa EXPLAIN-utdata som en prestanda-"assembly-lista." Det förvandlar justering från gissning till bevisbaserad felsökning. För mer om att göra det till en vana, se /blog/practical-query-optimization-habits.
Bra frågeprestanda börjar ofta innan du skriver SQL. Ullmans schemadesignteori (särskilt normalisering) handlar om att strukturera data så att databasen kan hålla den korrekt, förutsägbar och effektiv när den växer.
Normalisering strävar efter att:
De här korrekthetsvinsterna översätts ofta till prestandavinster senare: färre duplicerade fält, mindre index och färre kostsamma uppdateringar.
Du behöver inte memorera bevis för att använda idéerna:
Denormalisering kan vara ett smart val när:
Nyckeln är att denormalisera med avsikt och med en process för att hålla dubbletter synkade.
Schemadesign formar vad optimeraren kan göra. Tydliga nycklar och foreign keys möjliggör bättre join-strategier, säkrare omskrivningar och mer exakta radskattningar. Samtidigt kan överdriven duplicering blåsa upp index och sakta ned skrivningar, och flervärdiga kolumner blockerar effektiva predikat. När datavolymer växer spelar dessa tidiga modellbeslut ofta större roll än mikrootimering av en enda fråga.
När ett system "skalar" handlar det sällan bara om att lägga till större maskiner. Ofta är det svåra att samma frågebetydelse måste bevaras medan motorn väljer en helt annan fysisk strategi för att hålla körtider förutsägbara. Ullmans fokus på formella ekvivalenser är precis vad som tillåter dessa strategiändringar utan att ändra resultat.
I små storlekar fungerar många planer. I skala kan skillnaden mellan att skanna en tabell, använda ett index eller använda ett förberäknat resultat vara skillnaden mellan sekunder och timmar. Teoridelen är viktig eftersom optimeraren behöver en säker uppsättning omskrivningsregler (t.ex. skjuta ner filter, omordna joins) som inte ändrar svaret—även om de radikalt ändrar arbetet som utförs.
Partitionering (efter datum, kund, region osv.) delar en logisk tabell i många fysiska delar. Det påverkar planeringen:
SQL-texten kan vara oförändrad, men den bästa planen beror nu på var raderna bor.
Materialiserade vyer är i praktiken "sparade subuttryck". Om motorn kan bevisa att din fråga matchar (eller kan omskrivas för att matcha) ett lagrat resultat kan den ersätta kostsamt arbete—som upprepade joins och aggregeringar—med en snabb uppslagning. Detta är relationsalgebratänk i praktiken: känna igen ekvivalens, återanvända resultat.
Caching kan snabba upp upprepade läsningar, men den räddar inte en fråga som måste skanna för mycket data, omfördela enorma mellanresultat eller beräkna en jättestor join. När skalproblem dyker upp är åtgärden ofta: minska mängden data som berörs (layout/partitionering), minska upprepad beräkning (materialiserade vyer) eller ändra planen—inte bara "lägg till cache."
Ullmans inflytande visar sig i ett enkelt mindset: behandla en långsam fråga som en avsikt som databasen fritt kan omskriva, kontrollera sedan vad den faktiskt bestämde sig för att göra. Du behöver inte vara teoretiker för att dra nytta—du behöver bara en upprepbar rutin.
Börja med de delar som normalt dominerar körtid:
Om du bara gör en sak, identifiera första operatorn där radantalet exploderar. Det är ofta roten till problemet.
De här är lätta att skriva och förvånansvärt kostsamma:
WHERE LOWER(email) = ... kan hindra indexanvändning (använd normaliserad kolumn eller funktionellt index om stöds).Relationsalgebra uppmuntrar två praktiska steg:
WHERE innan joins när det går för att krympa inputs.En bra hypotes låter som: "Denna join är dyr därför att vi joinar för många rader; om vi filtrerar orders till de senaste 30 dagarna först minskar join-inputen."
Använd en enkel beslutsregel:
EXPLAIN visar undvikbart arbete (onödiga joins, sen filtrering, icke-sargable predikat).Målet är inte "smart SQL" utan förutsägbara, mindre mellanresultat—exakt den typ av ekvivalensbevarande förbättring Ullmans idéer gör lättare att se.
Dessa koncept är inte bara för databasadministratörer. Om du levererar en applikation fattar du databas- och planeringsbeslut även om du inte tänker på det: schemaform, nyckelval, frågemönster och datalagret påverkar vad optimeraren kan göra.
Om du använder ett vibe-coding arbetsflöde (t.ex. generera en React + Go + PostgreSQL-app från en chatt i Koder.ai) är Ullman-liknande mentala modeller ett praktiskt säkerhetsnät: du kan granska det genererade schemat för rena nycklar och relationer, inspektera frågorna appen förlitar sig på och validera prestanda med EXPLAIN innan problem uppstår i produktion. Ju snabbare du kan iterera på "frågeavsikt → plan → åtgärd", desto mer värde får du av accelererad utveckling.
Du behöver inte "studera teori" som en separat hobby. Det snabbaste sättet att dra nytta av Ullman-liknande grunder är att lära dig precis tillräckligt för att läsa frågeplaner säkert—och sedan öva på din egen databas.
Sök efter dessa böcker och föreläsningsteman (ingen anknytning—bara välkända startpunkter):
Börja smått och koppla varje steg till något du kan observera:
Välj 2–3 verkliga frågor och iterera:
IN till EXISTS, skjut predikat tidigare, ta bort onödiga kolumner, jämför resultat.Använd tydligt, planbaserat språk:
Det är den praktiska vinsten av Ullmans grunder: du får ett gemensamt vokabulär för att förklara prestanda—utan att gissa.
Jeffrey Ullman hjälpte till att formalisera hur databaser representerar frågors betydelse och hur de säkert kan omvandla frågor till snabbare ekvivalenter. Den grunden syns varje gång en motor omskriver en fråga, ändrar join-ordningen eller väljer en annan exekveringsplan — samtidigt som den garanterar samma resultatmängd.
Relationsalgebra är en liten uppsättning operatorer (select, project, join, union, difference) som exakt beskriver vad en fråga ska returnera. Motorer översätter ofta SQL till en algebra-liknande operatorstruktur så att de kan tillämpa ekvivalensregler (t.ex. att skjuta ner filter tidigare) innan de väljer en exekveringsstrategi.
Eftersom optimering bygger på att bevisa att en omskriven fråga returnerar samma resultat. Ekvivalensregler låter optimeraren till exempel:
WHERE-filter före en joinDessa förändringar kan drastiskt minska arbetet utan att ändra betydelsen.
En logisk plan beskriver vad som behöver göras (filter, join, aggregate) oberoende av lagringsdetaljer. En fysisk plan väljer hur det ska köras (indexscan vs full scan, hash join vs nested loop, parallellism, sortstrategier). De största prestandaskillnaderna kommer ofta från de fysiska valen, som möjliggörs av logiska omskrivningar.
Kostnadsbaserad optimering jämför flera giltiga planer och väljer den med lägst uppskattad kostnad. Kostnader drivs vanligtvis av praktiska faktorer som antal rader som behandlas, I/O, CPU och minnesanvändning (inklusive om en hash eller sort måste spillas till disk).
Kardinalitetsestimering är optimerarens gissning på "hur många rader kommer detta steg producera?". De uppskattade raderna styr join-ordning, join-typ och om en indexscan är vettig. När uppskattningarna är fel (ofta på grund av utdaterade eller saknade statistik) kan du få plötsliga fördröjningar, stora spillningar eller oväntade planändringar.
Fokusera på några högnivåledtrådar:
Behandla planen som kompilerad kod: den visar vad motorn faktiskt bestämde sig för att göra.
Normalisering minskar duplicerade fakta och uppdateringsanomalier, vilket ofta betyder mindre tabeller och index och mer pålitliga joins. Denormalisering kan vara rätt för analytiska eller lästunga mönster, men bör ske med vetenskapliga regler (tydliga uppdateringsrutiner, känd redundans) så att korrektheten inte försämras över tid.
Skalning kräver ofta att man ändrar fysisk strategi utan att ändra frågans betydelse. Vanliga verktyg:
Cache hjälper för upprepade läsningar, men löser inte en fråga som måste röra för mycket data eller som producerar enorma mellanresultat.