Frågeoptimering - Query optimization
Frågeoptimering är en funktion i många relationsdatabashanteringssystem och andra databaser, till exempel grafdatabaser . Den Frågeoptimeraren försök att bestämma det mest effektiva sättet att utföra en viss fråga genom att betrakta de möjliga frågeplaner .
I allmänhet kan sökfrågeoptimeraren inte nås direkt av användare: när frågor har skickats till databasservern och analyserats av parsern skickas de sedan till frågeoptimeraren där optimering sker. Vissa databasmotorer tillåter emellertid att styra frågeoptimeraren med tips .
En fråga är en begäran om information från en databas. Det kan vara så enkelt som "hitta adressen till en person med personnummer 123-45-6789" eller mer komplex som "hitta genomsnittslönen för alla anställda gifta män i Kalifornien mellan 30 och 39 år som tjänar mindre än deras makar. " Resultatet av en fråga genereras genom att bearbeta raderna i en databas på ett sätt som ger den begärda informationen. Eftersom databasstrukturer är komplexa, i de flesta fall, och särskilt för inte mycket enkla frågor, kan den data som behövs för en fråga samlas in från en databas genom att komma åt den på olika sätt, genom olika datastrukturer och i olika ordningar. Varje olika sätt kräver vanligtvis olika behandlingstider. Bearbetningstider för samma fråga kan ha stor variation, från en bråkdel av en sekund till timmar, beroende på den valda metoden. Syftet med frågeoptimering, som är en automatiserad process, är att hitta sättet att bearbeta en viss fråga på minsta tid. Den stora möjliga tidsvariansen motiverar att utföra frågeoptimering, men att hitta den exakta optimala frågeplanen bland alla möjligheter är vanligtvis mycket komplex, tidskrävande i sig, kan vara för kostsamt och ofta praktiskt taget omöjligt. Således försöker optimering av frågor vanligtvis närma sig det optimala genom att jämföra flera sunt förnuftsalternativ för att inom rimlig tid ge en "tillräckligt bra" plan som vanligtvis inte avviker mycket från bästa möjliga resultat.
Allmänna överväganden
Det finns en avvägning mellan hur mycket tid som läggs på att räkna ut den bästa sökplanen och kvaliteten på valet. optimeraren kanske inte väljer det bästa svaret på egen hand. Olika egenskaper hos databashanteringssystem har olika sätt att balansera dessa två. Kostnadsbaserade sökoptimeringar utvärderar resursavtrycket för olika frågeplaner och använder detta som grund för planval. Dessa tilldelar en beräknad "kostnad" till varje möjlig sökplan och väljer planen med den minsta kostnaden. Kostnader används för att uppskatta drifttiden för utvärdering av frågan, vad gäller antalet I/O -operationer som krävs, CPU -sökvägens längd , mängden diskbuffertutrymme, lagringstiden för disklagring och förbindelseanvändning mellan enheter av parallellitet och andra faktorer som bestäms från dataledboken . Uppsättningen av frågeplaner som undersöks bildas genom att undersöka de möjliga åtkomstvägarna (t.ex. primärindexåtkomst, sekundär indexåtkomst, fullständig filskanning) och olika relationella tabellföreningstekniker (t.ex. sammanslagning , sammanfogning , produktanslutning ). Sökutrymmet kan bli ganska stort beroende på komplexiteten i SQL -frågan. Det finns två typer av optimering. Dessa består av logisk optimering - som genererar en sekvens av relationsalgebra för att lösa frågan - och fysisk optimering - som används för att bestämma hur man utför varje operation.
Genomförande
De flesta frågeoptimerare representerar frågeplaner som ett träd med "plannoder". En plannod inkapslar en enda operation som krävs för att köra frågan. Noderna är arrangerade som ett träd, där mellanresultat flödar från trädets botten till toppen. Varje nod har noll eller fler underordnade noder - det är noder vars utmatning matas som inmatning till föräldernoden. Till exempel kommer en kopplingsnod att ha två underordnade noder, som representerar de två kopplingsoperanderna, medan en sorteringsnod skulle ha en enda barnnod (ingången som ska sorteras). Trädets blad är noder som ger resultat genom att skanna disken, till exempel genom att utföra en indexskanning eller en sekventiell genomsökning.
Gå med i beställningen
Utförandet av en frågeplan bestäms till stor del av den ordning tabellerna sammanfogas. Till exempel, när du sammanfogar tre tabeller A, B, C med storlek 10 rader, 10 000 rader respektive 1 000 000 rader, kan en frågeplan som först går med B och C ta flera storleksordningar mer tid att utföra än en som går först med A och C. De flesta frågeoptimeringar avgör anslutningsordning via en dynamisk programmeringsalgoritm som banbrytas av IBM: s System R -databasprojekt. Denna algoritm fungerar i två steg:
- Först beräknas alla sätt att komma åt varje relation i frågan. Varje relation i frågan kan nås via en sekventiell genomsökning. Om det finns ett index på en relation som kan användas för att besvara ett predikat i frågan kan en indexskanning också användas. För varje relation registrerar optimeraren det billigaste sättet att skanna relationen, liksom det billigaste sättet att skanna relationen som producerar poster i en viss sorterad ordning.
- Optimiseraren överväger sedan att kombinera varje par av relationer för vilka ett sammanfogningsvillkor finns. För varje par kommer optimeraren att överväga de tillgängliga kopplingsalgoritmerna som implementerats av DBMS . Det kommer att bevara det billigaste sättet att ansluta varje par av relationer, förutom det billigaste sättet att ansluta varje par av relationer som producerar dess produktion enligt en viss sorteringsordning.
- Därefter beräknas alla trerelationsfrågeplaner genom att gå med varje tvårelationsplan som producerades av föregående fas med de återstående relationerna i frågan.
Sorteringsordning kan undvika en redundant sortering senare vid bearbetning av frågan. För det andra kan en viss sorteringsordning påskynda en efterföljande sammanfogning eftersom den kluster data på ett visst sätt.
Frågeplanering för kapslade SQL -frågor
En SQL -fråga till ett modernt relationsdatabas gör mer än bara val och kopplingar. I synnerhet nestar SQL-frågor ofta flera lager av SPJ- block (Select-Project-Join), med hjälp av gruppera efter , existerar och finns inte . I vissa fall kan sådana kapslade SQL-frågor plattas till en select-project-join-fråga, men inte alltid. Frågeplaner för kapslade SQL -frågor kan också väljas med samma dynamiska programmeringsalgoritm som används för kopplingsbeställning, men detta kan leda till en enorm eskalering av frågestimeringstiden. Så vissa databashanteringssystem använder ett alternativt regelbaserat tillvägagångssätt som använder en frågediagrammodell.
Kostnadsuppskattning
Ett av de svåraste problemen vid frågeoptimering är att noggrant uppskatta kostnaderna för alternativa sökplaner. Optimörer kostar frågeplaner med hjälp av en matematisk modell för kostnader för genomförande av frågor som i hög grad är beroende av uppskattningar av kardinaliteten eller antalet dubbletter som flödar genom varje kant i en frågeplan. Uppskattning av kardinalitet beror i sin tur på uppskattningar av valfaktorn för predikat i frågan. Traditionellt uppskattar databassystem selektiviteter genom ganska detaljerad statistik över fördelningen av värden i varje kolumn, till exempel histogram . Denna teknik fungerar bra för att uppskatta selektiviteten hos enskilda predikat. Men många frågor har konjunktioner av predikat såsom . Frågepredikat är ofta starkt korrelerade (till exempel antyder ), och det är mycket svårt att uppskatta konjunktivens selektivitet i allmänhet. Dåliga kardinalitetsuppskattningar och ofångad korrelation är en av de främsta orsakerna till att sökoptimeringar väljer dåliga sökplaner. Detta är en anledning till att en databasadministratör regelbundet bör uppdatera databasstatistiken, särskilt efter stora dataladdningar/lossningar.
select count(*) from R where R.make='Honda' and R.model='Accord'model='Accord'make='Honda'
Tillägg
Klassisk frågeoptimering förutsätter att frågeplaner jämförs enligt en enda kostnadsmätvärde, vanligtvis genomförandetid, och att kostnaden för varje frågeplan kan beräknas utan osäkerhet. Båda antagandena kränks ibland i praktiken och flera utökningar av klassisk sökoptimering har studerats i forskningslitteraturen som övervinner dessa begränsningar. Dessa utökade problemvarianter skiljer sig åt i hur de modellerar kostnaden för enkelförfrågningsplaner och när det gäller deras optimeringsmål.
Parametrisk sökoptimering
Klassisk sökoptimering associerar varje sökplan med ett skalärt kostnadsvärde. Parametrisk frågeoptimering förutsätter att frågan plankostnad beror på parametrar vars värden är okända vid optimeringstidpunkten. Sådana parametrar kan till exempel representera selektiviteten hos frågepredikat som inte är fullständigt specificerade vid optimeringstid men kommer att tillhandahållas vid exekveringstidpunkten. Parametrisk frågeoptimering associerar därför varje frågeplan med en kostnadsfunktion som kartlägger från ett flerdimensionellt parameterutrymme till ett endimensionellt kostnadsutrymme.
Målet med optimering är vanligtvis att generera alla frågeplaner som kan vara optimala för någon av de möjliga parametervärdekombinationerna. Detta ger en uppsättning relevanta frågeplaner. Vid körning väljs den bästa planen ur den uppsättningen när de sanna parametervärdena blir kända. Fördelen med parametrisk frågeoptimering är att optimering (som i allmänhet är en mycket dyr operation) undviks vid körning.
Flerobjektiv förfrågan optimering
Det finns ofta andra kostnadsstatistik utöver körningstiden som är relevanta för att jämföra frågeplaner. I ett molnbaserat scenario till exempel bör man jämföra frågeformulär, inte bara när det gäller hur mycket tid de tar att utföra utan också när det gäller hur mycket pengar deras utförande kostar. Eller i samband med ungefärlig frågeoptimering är det möjligt att exekvera frågeplaner på slumpmässigt utvalda sampel av inmatningsdata för att få ungefärliga resultat med reducerad exekveringskostnad. I sådana fall måste alternativa sökplaner jämföras med avseende på deras körningstid men också när det gäller precisionen eller tillförlitligheten för de data de genererar.
Flerobjektiv frågeoptimering modellerar kostnaden för en sökplan som en kostnadsvektor där varje vektorkomponent representerar kostnad enligt en annan kostnadsmätning. Klassisk frågeoptimering kan betraktas som ett speciellt fall av flerobjektfrågeoptimering där kostnadens utrymme (dvs antalet kostnadsvektorkomponenter) är en.
Olika kostnadsstatistik kan komma i konflikt med varandra (t.ex. kan det finnas en plan med minimal körningstid och en annan plan med minimala monetära avgifter i ett molntjänstscenario). Därför kan optimeringsmålet inte vara att hitta en frågeplan som minimerar alla kostnadsmätvärden utan måste vara att hitta en frågeplan som uppnår den bästa kompromissen mellan olika kostnadsstatistik. Vad den bästa kompromissen är beror på användarens preferenser (t.ex. kan vissa användare föredra en billigare plan medan andra föredrar en snabbare plan i ett molnscenario). Målet med optimering är därför antingen att hitta den bästa sökplanen baserat på någon specifikation av användarpreferenser som ingång till optimeraren (t.ex. kan användare definiera vikter mellan olika kostnadsmätvärden för att uttrycka relativ betydelse eller definiera hårda kostnadsgränser för vissa mätvärden) eller för att generera en approximation av uppsättningen Pareto-optimala frågeplaner (dvs. planer så att ingen annan plan har bättre kostnad enligt alla mått) så att användaren kan välja den föredragna kostnadsavvägningen ur den planuppsättningen.
Flerobjektiv parametrisk sökoptimering
Flerobjektiv parametrisk sökoptimering generaliserar parametrisk och målinriktad sökoptimering. Planer jämförs med flera kostnadsmätvärden och plankostnader kan bero på parametrar vars värden är okända vid optimeringstidpunkten. Kostnaden för en frågeplan modelleras därför som en funktion från ett flerdimensionellt parameterutrymme till ett mångdimensionellt kostnadsutrymme. Målet med optimeringen är att generera uppsättningen av frågeplaner som kan vara optimala för varje möjlig kombination av parametervärden och användarinställningar.
Ett antal verktyg visar frågeförsökningsplaner för att visa vilka operationer som har den högsta behandlingskostnaden. Microsoft SMS, ApexSQLPlan, Hana och Tableau är några exempel. Att åtgärda dessa problem som finns i dessa planer kan raka tiotals procents körningstid, och i vissa fall kan du skära tvådimensionella sökningar till linjära.
En av de primära och enklaste checklistorna för optimering är att använda operationer som de flesta RDMS är utformade för att utföra effektivt. Se Sargable .
