Spørringsoptimalisering - Query optimization
Spørringsoptimalisering er en funksjon i mange relasjonsdatabasehåndteringssystemer og andre databaser som grafdatabaser . Den spørringsoptimisereren forsøk på å finne den mest effektive måten å utføre en gitt spørring ved å vurdere de mulige søket planer .
Vanligvis kan spørringsoptimereren ikke nås direkte av brukere: Når spørringer er sendt til databaseserveren og analysert av analysatoren, blir de deretter sendt til spørringsoptimereren der optimalisering skjer. Noen databasemotorer tillater imidlertid veiledning av spørringsoptimaliseringen med tips .
En forespørsel er en forespørsel om informasjon fra en database. Det kan være så enkelt som "finn adressen til en person med personnummer 123-45-6789" eller mer kompleks som "finn gjennomsnittslønnen for alle de ansatte gifte mennene i California mellom 30 og 39 år som tjener mindre enn ektefellene. " Resultatet av en forespørsel genereres ved å behandle radene i en database på en måte som gir den forespurte informasjonen. Siden databasestrukturer er komplekse, i de fleste tilfeller, og spesielt for ikke-veldig enkle søk, kan de nødvendige dataene for en forespørsel samles inn fra en database ved å få tilgang til den på forskjellige måter, gjennom forskjellige datastrukturer og i forskjellige ordre. Hver annen måte krever vanligvis forskjellig behandlingstid. Behandlingstiden for den samme spørringen kan ha stor variasjon, fra en brøkdel av et sekund til timer, avhengig av valgt metode. Hensikten med spørringsoptimalisering, som er en automatisert prosess, er å finne måten å behandle en gitt spørring på minimum tid. Den store mulige variansen i tid rettferdiggjør utførelse av spørringsoptimalisering, selv om det å finne den eksakte optimale spørringsplanen blant alle muligheter vanligvis er veldig komplekst, tidkrevende i seg selv, kan være for kostbart og ofte praktisk talt umulig. Dermed prøver spørringsoptimalisering vanligvis å tilnærme det optimale ved å sammenligne flere fornuftige alternativer for å gi en "god nok" plan i rimelig tid som vanligvis ikke avviker mye fra det best mulige resultatet.
Generelle hensyn
Det er en avveining mellom mengden tid brukt på å finne ut den beste spørringsplanen og kvaliteten på valget; Optimizer velger kanskje ikke det beste svaret alene. Ulike kvaliteter til databasesystemer har forskjellige måter å balansere disse to på. Kostnadsbaserte spørringsoptimerere evaluerer ressursfotavtrykket til ulike spørringsplaner og bruker dette som grunnlag for planvalg. Disse tildeler en estimert "kostnad" til hver mulig spørringsplan, og velger planen med den minste kostnaden. Kostnader brukes til å estimere kjøretidskostnadene ved evaluering av spørringen, når det gjelder antall I/O -operasjoner som kreves, CPU -banelengde , mengde diskbufferplass, disklagringstjenestetid og sammenkoblingsbruk mellom enheter av parallellitet og andre faktorer bestemt fra datalisten . Settet med spørringsplaner som blir undersøkt, dannes ved å undersøke de mulige tilgangsbanene (f.eks. Primærindekstilgang, sekundær indekstilgang, full filskanning) og ulike relasjonelle tabellforbindelsesteknikker (f.eks. Flette sammenføyning , hash -sammenføyning , produktkopling ). Søkerommet kan bli ganske stort avhengig av kompleksiteten til SQL -spørringen. Det er to typer optimalisering. Disse består av logisk optimalisering - som genererer en sekvens av relasjonsalgebra for å løse spørringen - og fysisk optimalisering - som brukes til å bestemme virkemåten for å utføre hver operasjon.
Gjennomføring
De fleste spørringsoptimaliserere representerer spørringsplaner som et tre med "plannoder". En plannode innkapsler en enkelt operasjon som er nødvendig for å utføre spørringen. Nodene er arrangert som et tre, der mellomliggende resultater flyter fra bunnen av treet til toppen. Hver node har null eller flere underordnede noder - det er noder hvis utgang mates som input til den overordnede noden. For eksempel vil en sammenføyningsnode ha to barnnoder, som representerer de to sammenføyningsoperandene, mens en sorteringsnode ville ha en enkelt barneknode (inngangen som skal sorteres). Bladene på treet er noder som gir resultater ved å skanne disken, for eksempel ved å utføre en indeksskanning eller en sekvensiell skanning.
Bli med å bestille
Utførelsen av en spørringsplan bestemmes i stor grad av rekkefølgen tabellene er sammenføyd. For eksempel, ved sammenføyning av 3 tabeller A, B, C med henholdsvis 10 rader, 10 000 rader og 1 000 000 rader, kan det ta flere spørreplaner som går sammen med B og C mer enn en blir først med A og C. De fleste forespørgselsoptimaliserere bestemmer koblingsrekkefølgen via en dynamisk programmeringsalgoritme som ble utviklet av IBMs System R -databaseprosjekt. Denne algoritmen fungerer i to trinn:
- Først beregnes alle måter å få tilgang til hver relasjon i spørringen. Hver relasjon i spørringen kan nås via en sekvensiell skanning. Hvis det er en indeks på en relasjon som kan brukes til å svare på et predikat i spørringen, kan en indeksskanning også brukes. For hver relasjon registrerer optimalisatoren den billigste måten å skanne relasjonen på, samt den billigste måten å skanne relasjonen som produserer poster i en bestemt sortert rekkefølge.
- Optimisatoren vurderer deretter å kombinere hvert par relasjoner som det finnes en sammenhengstilstand for. For hvert par vil optimalisatoren vurdere de tilgjengelige koblingsalgoritmene som er implementert av DBMS . Det vil bevare den billigste måten å slutte seg til hvert par relasjoner, i tillegg til den billigste måten å bli med hvert par av relasjoner som produserer sin produksjon i henhold til en bestemt sorteringsrekkefølge.
- Deretter beregnes alle tre-relasjons-spørringsplanene ved å koble hver to-relasjonsplan produsert av forrige fase med de resterende relasjonene i spørringen.
Sorteringsrekkefølge kan unngå en redundant sorteringsoperasjon senere i behandlingen av spørringen. For det andre kan en bestemt sorteringsrekkefølge fremskynde en påfølgende sammenføyning fordi den klynger dataene på en bestemt måte.
Spørringsplanlegging for nestede SQL -spørringer
En SQL -spørring til et moderne relasjons -DBMS gjør mer enn bare valg og sammenføyninger. Spesielt hekker SQL-forespørsler ofte flere lag med SPJ- blokker (Select-Project-Join), ved hjelp av grupper etter , eksisterer , og eksisterer ikke . I noen tilfeller kan slike nestede SQL-forespørsler flates ut til en select-project-join-spørring, men ikke alltid. Spørringsplaner for nestede SQL -spørringer kan også velges ved hjelp av den samme dynamiske programmeringsalgoritmen som brukes for å bli med, men dette kan føre til en enorm eskalering i spørringens optimaliseringstid. Så noen databasesystemer bruker en alternativ regelbasert tilnærming som bruker en spørringsgrafmodell.
Kostnadsoverslag
Et av de vanskeligste problemene med spørringsoptimalisering er å nøyaktig estimere kostnadene ved alternative spørringsplaner. Optimaliserere koster spørringsplaner ved hjelp av en matematisk modell for utførelse av spørringskostnader som i stor grad er avhengig av estimater av kardinaliteten , eller antall tupler, som flyter gjennom hver kant i en spørringsplan. Estimering av kardinalitet avhenger igjen av estimater av valgfaktoren for predikater i spørringen. Tradisjonelt estimerer databasesystemer selektivitet gjennom ganske detaljert statistikk over verdifordelingen i hver kolonne, for eksempel histogrammer . Denne teknikken fungerer godt for estimering av selektivitetene til individuelle predikater. Imidlertid har mange spørsmål konjunksjoner av predikater som . Spørringsforutsigelser er ofte sterkt korrelert (for eksempel antyder ), og det er veldig vanskelig å estimere selektiviteten til konjunktet generelt. Dårlige kardinalitetsestimater og uoppdaget korrelasjon er en av hovedårsakene til at spørringsoptimaliserere velger dårlige spørringsplaner. Dette er en grunn til at en databaseadministrator regelmessig bør oppdatere databasestatistikken, spesielt etter store datalast/-laster.
select count(*) from R where R.make='Honda' and R.model='Accord'model='Accord'make='Honda'
Utvidelser
Klassisk spørringsoptimalisering forutsetter at spørringsplaner sammenlignes i henhold til en enkelt kostnadsberegning, vanligvis utførelsestid, og at kostnaden for hver spørringsplan kan beregnes uten usikkerhet. Begge forutsetningene blir noen ganger brutt i praksis, og flere utvidelser av klassisk spørringsoptimalisering har blitt studert i forskningslitteraturen som overvinner disse begrensningene. Disse utvidede problemvariantene er forskjellige i hvordan de modellerer kostnaden for enkeltforespørselsplaner og når det gjelder optimaliseringsmål.
Parametrisk spørringsoptimalisering
Klassisk spørringsoptimalisering knytter hver spørringsplan til en skalar kostnadsverdi. Parametrisk spørringsoptimalisering forutsetter at spørringsplankostnaden avhenger av parametere hvis verdier er ukjente ved optimaliseringstidspunktet. Slike parametere kan for eksempel representere selektiviteten til forespørsler som ikke er spesifisert fullt ut ved optimaliseringstidspunktet, men som vil bli gitt ved utførelsestidspunktet. Parametrisk spørringsoptimalisering forbinder derfor hver spørringsplan med en kostnadsfunksjon som kartlegger fra et flerdimensjonalt parameterrom til et endimensjonalt kostnadsrom.
Målet med optimalisering er vanligvis å generere alle spørringsplaner som kan være optimale for noen av de mulige parameterverdikombinasjonene. Dette gir et sett med relevante spørringsplaner. Ved kjøretid velges den beste planen ut av settet når de sanne parameterverdiene blir kjent. Fordelen med parametrisk spørringsoptimalisering er at optimalisering (som generelt er en veldig kostbar operasjon) unngås ved kjøretid.
Optimalisering av flere mål
Det er ofte andre kostnadsberegninger i tillegg til gjennomføringstid som er relevante for å sammenligne spørringsplaner. I et cloud computing -scenario, for eksempel, bør man sammenligne spørringsplaner ikke bare når det gjelder hvor lang tid de tar å utføre, men også når det gjelder hvor mye penger utførelsen deres koster. Eller i sammenheng med omtrentlig spørringsoptimalisering, er det mulig å utføre spørringsplaner på tilfeldig utvalgte prøver av inndataene for å oppnå omtrentlige resultater med redusert overføringsoverhead. I slike tilfeller må alternative spørringsplaner sammenlignes når det gjelder gjennomføringstid, men også når det gjelder presisjon eller pålitelighet for dataene de genererer.
Flerobjektiv spørringsoptimalisering modellerer kostnaden for en spørringsplan som en kostnadsvektor hvor hver vektorkomponent representerer kostnad i henhold til en annen kostnadsberegning. Klassisk spørringsoptimalisering kan betraktes som et spesielt tilfelle av multi-objektiv spørringsoptimalisering der dimensjonen til kostnadsområdet (dvs. antall kostnadsvektorkomponenter) er én.
Ulike kostnadsberegninger kan komme i konflikt med hverandre (f.eks. Kan det være en plan med minimal gjennomføringstid og en annen plan med minimale monetære utførelsesgebyrer i et cloud computing -scenario). Derfor kan målet med optimalisering ikke være å finne en spørringsplan som minimerer alle kostnadsberegninger, men må være å finne en spørringsplan som realiserer det beste kompromisset mellom forskjellige kostnadsberegninger. Hva det beste kompromisset er, avhenger av brukerpreferanser (f.eks. Noen brukere foretrekker kanskje en billigere plan mens andre foretrekker en raskere plan i et skyscenario). Målet med optimalisering er derfor enten å finne den beste spørringsplanen basert på noen spesifikasjoner av brukerpreferanser gitt som input til optimalisatoren (f.eks. Kan brukere definere vekter mellom forskjellige kostnadsberegninger for å uttrykke relativ betydning eller definere harde kostnadsgrenser på visse beregninger) eller for å generere en tilnærming til settet med pareto-optimale spørringsplaner (dvs. planer slik at ingen annen plan har bedre kostnader i henhold til alle beregninger) slik at brukeren kan velge den foretrukne kostnadsavveining ut av det plansettet.
Flerobjektiv parametrisk spørringsoptimalisering
Multi-objektiv parametrisk spørringsoptimalisering generaliserer parametrisk og multi-objektiv spørringsoptimalisering. Planer sammenlignes i henhold til flere kostnadsberegninger, og plankostnader kan avhenge av parametere hvis verdier er ukjente ved optimaliseringstidspunktet. Kostnaden for en spørringsplan er derfor modellert som en funksjon fra et flerdimensjonalt parameterrom til et flerdimensjonalt kostnadsrom. Målet med optimalisering er å generere settet med spørringsplaner som kan være optimale for hver mulig kombinasjon av parameterverdier og brukerpreferanser.
En rekke verktøy viser spørringsutførelsesplaner for å vise hvilke operasjoner som har høyest behandlingskostnad. Microsoft SMS, ApexSQLPlan, Hana og Tableau er noen eksempler. Å fikse disse problemene som finnes i disse planene, kan barbere titalls prosent gjennomføringstid, og i noen tilfeller kutte todimensjonale søk til lineære.
En av de viktigste og enkleste sjekklistene for optimalisering er å bruke operasjoner som de fleste RDMS er designet for å utføre effektivt. Se Sargable .
