Kyselyn optimointi on 1) DBMS -toiminto , joka etsii optimaalisen kyselyn suoritussuunnitelman kaikista mahdollisista tietylle kyselylle, 2) prosessin kyselyn ja/tai tietokantarakenteen muuttamiseen laskentaresurssien käytön vähentämiseksi suoritettaessa kysely. DBMS voi saada saman tuloksen eri tavoilla ( query execution plans ), jotka voivat vaihdella merkittävästi sekä resurssikustannusten että suoritusajan suhteen. Optimointiongelmana on löytää optimaalinen tapa.
Relaatio-DBMS:ssä optimaalinen kyselyn suoritussuunnitelma on sellainen sarja, jossa relaatioalgebra-operaattoreita sovelletaan alku- ja välirelaatioihin, joka tietokannan tietyssä nykyisessä tilassa (sen rakenne ja sisältö) voidaan suorittaa käyttämällä mahdollisimman vähän laskentaresursseja. .
Tällä hetkellä tunnetaan kaksi strategiaa optimaalisen suunnitelman löytämiseksi:
Lisäksi jotkin DBMS-järjestelmät antavat ohjelmoijalle mahdollisuuden puuttua optimaalisen suunnitelman etsimiseen vaihtelevasti, minimaalisesta vaikutuksesta täysin ja selkeästi käytettävän kyselysuunnitelman määrittämiseen.
Kyselyn suoritussuunnitelmia verrataan useiden tekijöiden perusteella (toteutukset vaihtelevat DBMS:n mukaan), mukaan lukien:
Yleensä liittäminen tehdään sisäkkäisissä silmukoissa . Tämä algoritmi voi kuitenkin olla vähemmän tehokas kuin erikoisalgoritmit. Esimerkiksi, jos yhdistettävillä taulukoilla on indeksit liitettävillä kentillä tai yksi tai molemmat taulukot ovat tarpeeksi pieniä lajitettavaksi muistiin, silloin tutkitaan mahdollisuutta suorittaa yhdistäminen .
Kuten jo todettiin, optimoinnin ydin on löytää kustannusfunktion minimi permutointitaulukoista. Strategiasta riippumatta optimoijan on kyettävä analysoimaan mielivaltaisen permutoinnin kustannukset, kun taas itse permutaatiot analyysiä varten tarjotaan toisella algoritmilla. Tutkittava permutaatiojoukko voi poiketa koko permutaatioavaruudesta. Tämän perusteella optimoijan yleistetty algoritmi voidaan kirjoittaa seuraavasti:
Teoriassa brute-force-strategiaa käytettäessä kyselyn optimoija tutkii kaikkien alkuperäisten hakutaulukoiden koko permutaatioavaruuden ja vertaa yhdistettyjä liitoskustannusarvioita jokaiselle permutaatiolle. Käytännössä System R :tä suunniteltaessa ehdotettiin, että tutkimustila rajoitetaan vain vasen liitoksiin, jolloin kyselyä suoritettaessa yhtä taulukoista esitetään aina levyllä oleva kuva. Ei-vasen liitosten tutkiminen on järkevää, jos liitoksissa olevat taulukot sijaitsevat useammassa kuin yhdessä solmussa.
Jokaisen taulukon osalta kussakin permutaatiossa indeksien käyttömahdollisuus arvioidaan tilastollisesti. Permutaatio, jolla on vähimmäispistemäärä, on lopullinen kyselyn suoritussuunnitelma.
Algoritmeja kaikkien permutaatioiden luomiseksi käsitellään Donald Knuthin "Tietokoneohjelmoinnin taiteen" osan 2 neljännessä osassa (katso bibliografia).
Suunnitelman kustannusarvio taulukoiden nykyisen permutoinnin perusteella /* * Kyselyn kustannusarvion tekeminen vastaavasti * kyselyssä olevien taulukoiden nykyinen järjestys * Funktio palauttaa arvon < 0, jos se päättää olla tekemättä kaikkia arviovaiheita, koska * tämän tilauksen hinta >> the_best_cost (jos_paras_kustannus > 0) * Toisessa tapauksessa se palauttaa arvioidut kustannukset (>=0) */ staattinen kelluke est_cost_order ( i4_t * res_row_num ) { MASK Riippuu = _AllTblMsk ; i4_t tbl_num , prdc_num , i , todellinen_num , SarakeNum ; float cost_all = 0,0 , rivin_määrä = 1,0 ; float ind_best_sel , sel ; SP_Ind_Info * cur_ind_info ; /* arvio taulukoiden skannauksen kustannuksista */ for ( tbl_num = 0 ; tbl_num < taulukoiden_määrä ; tbl_num ++ ) { ind_paras_sel = 1,0 ; todellinen_numero = cur_tbl_order [ tbl_num ]; TblAllBits [ tbl_num ] = Riippuu = BitOR ( Riippuu , TblBits [ real_num ]); /* taulukon init saadaksesi tietoja culumeista */ for ( i = 0 ; i < välilehtien_sarakkeen_numero [ todellinen_numero ]; i ++ ) col_stat [ i ]. Sel = 1,0 ; /* tarkistetaan tiedot nykyisen taulukon palvelupisteistä */ for ( prdc_num = 0 ; prdc_num < SPs_ lukumäärä ; prdc_num ++ ) if ( ! ( SPs [ prdc_num ]. flag ) /* tätä predikaattia ei vielä käytetty */ && CAN_BE_USED ( SPs [ prdc_num ]. Riippuu , Riippuu ) /* predikaattia voidaan käyttää nyt */ ) { SP :t [ prdc_num ]. lippu ++ ; cur_ind_info = ( SPs_indexes [ real_num ]) + prdc_num ; jos ( cur_ind_info -> Sel ) { /* tämä predikaatti on SP nykyiselle taulukolle */ SarakeNum = cur_ind_info -> SarakeNum ; if ( col_stat [ ColNum ]. Sel > cur_ind_info -> Sel ) { col_stat [ ColNum ]. Sel = cur_ind_info -> Sel ; if ( cur_ind_info -> IndExists /* on indeksi tämän SP:n sarakkeelle */ && col_stat [ ColNum ]. Sel < ind_best_sel ) ind_best_sel = col_stat [ ColNum ]. Sel ; } } } /* kaikkien yksinkertaisten predikaattien yhteisen selektiivisyyden löytäminen nykyiselle taulukolle */ for ( i = 0 , sel = 1.0 ; i < välilehtien_sarakkeen_numero [ todellinen_numero ]; i ++ ) sel *= col_stat [ i ]. Sel ; /* oletusselektiivisyyden lisääminen muille predikaateille */ for ( prdc_num = palvelupisteiden_määrä ; prdc_num < erojen_määrä ; prdc_num ++ ) if ( ! ( SPs [ prdc_num ]. flag ) /* tätä predikaattia ei vielä käytetty */ && CAN_BE_USED ( SPs [ prdc_num ]. Depend , Depend ) /* predikaattia voidaan käyttää nyt */ ) { SP :t [ prdc_num ]. lippu ++ ; sel *= DEFAULT_SEL ; } skannattujen_rivien_määrä [ tbl_num ] = rivien_määrä [ todellinen_määrä ] * ind_paras_sel * rivin_määrä ; /* skannattujen_rivien_määrä [i] - arvioitu i:nnestä taulukosta luettujen rivien määrä */ kustannus_kaikki += skannattujen_rivien_määrä [ tbl_num ] + OPEN_SCAN_COST * rivin_määrä ; rivin_määrä *= rivien_määrä [ todellinen_numero ] * sel ; } /* for tbl_num: taulukoiden käsittely */ for ( prdc_num = 0 ; prdc_num < erojen_määrä ; prdc_num ++ ) SP :t [ prdc_num ]. lippu = 0 ; /* kaikkien alikyselyiden kustannusten lisääminen */ for ( prdc_num = 0 ; prdc_num < erojen_määrä ; prdc_num ++ ) { for ( tbl_num = 0 ; tbl_num < taulukoiden_määrä ; tbl_num ++ ) if ( CAN_BE_USED ( SPs [ prdc_num ]. SQ_deps , TblAllBits [ tbl_num ])) tauko ; assert ( tbl_num < taulukoiden_määrä ); /* tbl_num - viimeisen (järjestyksessä) taulukon numero * * johon viitataan predikaatissa */ cost_all += SP [ prdc_num ]. SQ_cost * skannattujen_rivien_määrä [ tbl_num ]; } * res_row_num = ( rivin_numero < 1,0 ) ? 1 : (( rivin_numero < FLT_MAX_LNG ) ? ( i4_t ) rivin_numero : MAX_LNG ); palautuskustannukset_kaikki ; _ } /* est_cost_order */Tässä cur_tbl_order on edellisestä esimerkistä tuttu vektori, joka sisältää nykyisen taulukkojärjestyksen.
Kun kyselyn taulukkojen määrä kasvaa, mahdollisten permutaatioiden määrä kasvaa n:llä! , joten myös kunkin arvioinnin aika kasvaa suhteessa . Tämän vuoksi on ongelmallista optimoida kyselyitä useiden taulukkojen perusteella. Etsiessään ratkaisua tähän ongelmaan vuonna 1991 Kristin Bennett, Michael Ferris, Yannis Ioannidis ehdottivat geneettisen algoritmin käyttöä kyselyn optimointiin, joka antaa alioptimaalisen ratkaisun lineaarisessa ajassa.
Geneettistä algoritmia käytettäessä tarkastellaan vain osaa permutaatioavaruudesta. Kyselyyn osallistuvat taulukot on koodattu kromosomeihin. Ne mutatoituvat ja risteytyvät. Jokaisessa iteraatiossa suoritetaan kromosomien palautus, jotta saadaan taulukkojen mielekäs permutaatio ja kromosomivalikoima, joka antaa minimaaliset kustannusarviot. Valinnan seurauksena jäljelle jää vain ne kromosomit, jotka antavat kustannusfunktion arvon edelliseen iteraatioon verrattuna. Näin ollen kustannusfunktion paikallisten minimien tutkimus ja löytäminen tapahtuu. Oletetaan, että globaali minimi ei tarjoa merkittäviä etuja parhaaseen paikalliseen minimiin verrattuna. Algoritmia toistetaan useita iteraatioita, minkä jälkeen valitaan tehokkain ratkaisu.
Kyselyn suoritussuunnitelmia arvioitaessa tutkitaan vaihtoehtoisia tapoja suorittaa relaatioliitoksia. Kytkentämenetelmät eroavat tehokkuudestaan, mutta niillä on rajoituksia sovelluksissa.
Sisäkkäisten silmukoiden tapauksessa ulompi silmukka hakee kaikki rivit uloimmasta taulukosta ja kutsuu sisemmän silmukan jokaiselle löydetylle riville. Sisäsilmukka etsii rivejä sisäisestä taulukosta liitosehtojen ja ulomman silmukan tietojen perusteella. Silmukat voidaan upottaa mielivaltaisen määrän kertoja. Tässä tapauksessa sisäisestä silmukasta tulee seuraavan silmukan ulompi silmukka ja niin edelleen.
Arvioitaessa sisäkkäisten silmukoiden eri suoritusjärjestystä sisäisen silmukan kutsumisen minimoimiseksi on edullista, että ulompi silmukka skannaa vähemmän rivejä kuin sisempi.
Jokaiselle taulukolle indeksin valitsemiseksi ensin löydetään kaikki mahdolliset indeksit, joita voidaan käyttää tutkittavassa kyselyssä. Koska hakemiston avaimet ovat järjestyksessä, tehokas hakeminen siitä voidaan tehdä vain leksikografisessa järjestyksessä . Tässä suhteessa indeksin valinta perustuu indeksiin sisältyvien sarakkeiden rajoitusten olemassaoloon ensimmäisestä alkaen.
Jokaiselle indeksiin sisältyvälle sarakkeelle, ensimmäisestä alkaen, haetaan rajoituksia annetun taulukon koko rajoitusjoukosta, mukaan lukien liitosehdot. Jos indeksin ensimmäiselle sarakkeelle ei löydy rajoituksia, indeksiä ei käytetä (muuten koko indeksi pitäisi skannata). Jos seuraavalle sarakkeelle ei löydy rajoituksia, haku päättyy ja indeksi hyväksytään.
Toteutussuunnitelmia arvioitaessa tarkastellaan vaihtoehtoisia indeksijoukkoja, joita voidaan käyttää otantaan. Sisäkkäisten silmukoiden tapauksessa uloin silmukka ei voi käyttää indeksiä, jota rajoittaa vähintään yksi liitosehto, koska yksikään liitosehto ei ole täysin määritelty silmukan suoritettaessa. Sisäsilmukka ei voi käyttää indeksiä, jonka rajoitukset eivät ole yhteensopivia liitosehtojen kanssa.
Loput indeksit luokitellaan haettujen rivien lukumäärän ja avaimen pituuden mukaan. On selvää, että haettavien rivien määrä riippuu rajoituksista. Mitä pienempi haettujen rivien määrä on ja mitä lyhyempi avaimen pituus, sitä korkeampi sijoitus.
Otantassa käytetään korkeimman sijoituksen omaavaa indeksiä.
Joidenkin aggregointikyselyiden osalta koko indeksi voidaan skannata. Erityisesti:
Jos pyydetty hakujärjestys vastaa yhden tai useamman indeksin järjestystä, arvioidaan, voidaanko jokin näistä indekseistä skannata kokonaisuudessaan.
Jos hakemisto sisältää kaikki sarakkeet, jotka vaaditaan tuloksen tuottamiseen , taulukon tarkistusta ei tapahdu. Jos optimoija käyttää tätä tekijää, on mahdollista nopeuttaa hakua taulukosta erikoiskyselyissä sisällyttämällä indeksiin redundantteja sarakkeita, jotka haetaan suoraan avaimella haettaessa. Tätä kyselyiden nopeuttamistapaa tulee käyttää varoen.
Jos yhdistettävillä taulukoilla on indeksit vertailtavissa kentissä tai jos toinen tai molemmat taulukot ovat tarpeeksi pieniä lajitettavaksi muistiin, yhdistäminen voidaan suorittaa yhdistämällä. Molemmat lajitellut tietojoukot skannataan ja niistä haetaan samoja arvoja. Lajittelun ansiosta yhdistäminen on tehokkaampaa kuin sisäkkäiset silmukat suurilla tietomäärillä, mutta toteutussuunnitelma ei voi alkaa yhdistämisellä.
Taulukosta haettujen rivien lukumäärän arviota käytetään päätettäessä, suoritetaanko koko taulukkotarkistus indeksihaun sijaan. Päätös tehdään sillä perusteella, että jokainen levyltä luettava hakemistosivu sisältää yhden tai useamman paikannuksen ja yhden tai useamman taulukkosivun lukemisen. Koska hakemisto sisältää myös ei-lehtisiä sivuja, yli 0,1-1 % riveistä poimiminen taulukosta on yleensä tehokkaampaa suorittaa koko taulukon tarkistus.
Tarkempi arvio saadaan seuraavien indikaattoreiden perusteella:
DBMS yrittää järjestää yhden taulukon tietolohkojen tallennuksen peräkkäin eliminoidakseen täyden tarkistuksen paikannuskustannukset ( Oracle DBMS käyttää levytilan ennakkovarausta datatiedostoille). Täydellisen tarkistuksen tehokkuutta lisää myös luku eteenpäin . Ennakkolukutoiminnolla DBMS antaa samanaikaisesti lukukomentoja useille lohkoille ulkoiseen muistiin. Skannaus alkaa, kun jokin lohkoista on luettu. Samanaikaisesti jäljellä olevien lohkojen lukeminen jatkuu. Tehokkuus saavutetaan lukemisen ja skannauksen rinnakkaisuuden ansiosta.
Jos DBMS on käynnissä useilla prosessoreilla, lajittelut voidaan suorittaa rinnakkain vasteajan lyhentämiseksi. Tämän edellytyksenä on mahdollisuus sijoittaa kaikki haetut tiedot RAM-muistiin. Lajittelua varten poimitut tiedot jaetaan fragmenteiksi, joiden lukumäärä on yhtä suuri kuin prosessorien lukumäärä. Jokainen prosessori suorittaa lajittelun yhdelle fragmentista muista riippumatta. Viimeisessä vaiheessa lajitellut fragmentit yhdistetään tai yhdistäminen yhdistetään tietojen antamiseen DBMS-asiakkaalle.
Jos DBMS on käynnissä useissa solmuissa, jokainen kyselyn suorittamiseen osallistuva solmu suorittaa lajittelun rinnakkain. Sitten kukin solmu lähettää fragmenttinsa datan luovuttamisesta asiakkaalle vastaavalle solmulle, jossa vastaanotetut fragmentit yhdistetään.
RDBMS käyttää tilastoja arvioidakseen mahdollisen taulukosta haettavien rivien määrän . Tilastossa on taulukon jokaiselle sarakkeelle histogrammimuotoinen versio , jossa arvoasteikko sijaitsee vaakasuorassa ja sarakkeen korkeus ilmaisee arvion rivien lukumäärästä prosentteina rivien kokonaismäärästä.
Jos taulukosta haetaan rivejä, joiden sarakkeen C arvo on rajoituksella [V1, V2], voimme arvioida tähän väliin kuuluvien rivien lukumäärän. Algoritmi erotettavien rivien määrän arvioimiseksi on seuraava:
Pääsääntöisesti DBMS ei tiedä eikä voi tietää taulukon rivien tarkkaa määrää (jopa SELECT COUNT(*) FROM TABLE -kyselyssä ensisijainen indeksi tarkistetaan), koska tietokanta voi tallentaa useita kuvia samasta taulukosta. eri lukumäärällä rivejä samaan aikaan. Seuraavia tietoja käytetään rivien määrän arvioimiseen:
Tilastot voidaan tallentaa myös suoriteperusteisesti. Tässä tapauksessa jokainen intervalli sisältää kaikkien aikaisempien intervallien kokonaispistemäärän sekä oman pistemääränsä. Jotta saadaan estimaatti rajoitteen [V1, V2] rivien lukumäärästä, riittää, että vähennetään sen välin estimaatti, johon V1 osuu, estimaatista.
Tilastojen kerääminen histogrammien piirtämistä varten suoritetaan joko erityisillä DBMS -komennoilla tai DBMS :n taustaprosesseilla . Samalla, kun otetaan huomioon, että tietokanta voi sisältää merkittävän määrän tietoa, koko rivien yleisestä populaatiosta tehdään pienempi otos . Otoksen edustavuuden (luotettavuuden) arviointi voidaan tehdä esimerkiksi Kolmogorov-sopimuskriteerin mukaan .
Jos taulukon tiedot muuttuvat merkittävästi lyhyessä ajassa, tilastot eivät ole enää relevantteja ja optimoija tekee virheellisiä päätöksiä koko taulukon skannauksesta. Tietokannan käyttäytyminen tulee suunnitella siten, että tilastot pysyvät ajan tasalla, tai tilastopohjaista optimointia ei käytetä.
| Tietokanta | |
|---|---|
| Käsitteet |
|
| Objektit |
|
| Avaimet | |
| SQL | |
| Komponentit | |