Optimizarea interogării este 1) o funcție DBMS care caută planul optim de execuție a interogării dintre toate posibilele pentru o anumită interogare, 2) procesul de modificare a unei interogări și/sau a structurii bazei de date pentru a reduce utilizarea resurselor de calcul la executarea unei interogări. interogare. Același rezultat poate fi obținut de SGBD în moduri diferite ( planuri de execuție a interogărilor ), care pot diferi semnificativ atât în ceea ce privește costurile resurselor, cât și timpul de execuție. Problema de optimizare este găsirea modului optim.
Într-un SGBD relațional, planul optim de execuție a interogării este o astfel de secvență de aplicare a operatorilor de algebră relațională la relațiile inițiale și intermediare care, pentru o anumită stare curentă a bazei de date (structura și conținutul acesteia), poate fi realizată cu utilizarea minimă a resurselor de calcul. .
În prezent, sunt cunoscute două strategii pentru găsirea planului optim:
De asemenea, unele SGBD-uri permit programatorului să intervină în căutarea planului optim în diferite grade, de la influență minimă până la specificarea completă și clară ce plan de interogare să folosească.
Planurile de execuție a interogărilor sunt comparate pe baza unei varietăți de factori (implementarea variază în funcție de SGBD), inclusiv:
În general, îmbinarea se face în bucle imbricate . Cu toate acestea, acest algoritm poate fi mai puțin eficient decât algoritmii specializați. De exemplu, dacă tabelele care urmează să fie îmbinate au indici pe câmpurile care se îmbină sau unul sau ambele tabele sunt suficient de mici pentru a fi sortate în memorie, atunci este investigată posibilitatea de a efectua îmbinări .
După cum sa menționat deja, esența optimizării este găsirea minimului funcției de cost din tabelele de permutare. Indiferent de strategie, optimizatorul trebuie să fie capabil să analizeze costul unei permutări arbitrare, în timp ce permutările în sine pentru analiză sunt furnizate de un alt algoritm. Setul de permutări studiat poate diferi de întregul spațiu de permutare. Pe baza acestui lucru, algoritmul generalizat al optimizatorului poate fi scris după cum urmează:
În teorie, atunci când se utilizează o strategie de forță brută, optimizatorul de interogări examinează întregul spațiu de permutare al tuturor tabelelor de preluare originale și compară estimările combinate ale costurilor de îmbinare pentru fiecare permutare. În practică, atunci când a fost proiectat System R , s-a propus să se limiteze spațiul de investigare doar la îmbinări din stânga, astfel încât atunci când se execută o interogare, unul dintre tabele să fie întotdeauna reprezentat de o imagine pe disc. Examinarea îmbinărilor non-stânga are sens dacă tabelele din îmbinări sunt situate pe mai multe noduri.
Pentru fiecare tabel din fiecare dintre permutări, se evaluează statistic posibilitatea utilizării indicilor. Permutarea cu scorul minim este planul final de execuție a interogării.
Algoritmii pentru generarea tuturor permutărilor sunt discutați în al patrulea volum al secțiunii 2 din „Arta programarii pe computer” de Donald Knuth (vezi bibliografia).
Estimarea costului planului pe baza permutării curente a tabelelor /* * Efectuarea unei estimări a costului interogării în consecință * ordinea curentă a tabelelor în interogare * Funcția returnează valoarea < 0 dacă decide să nu * efectueze toți pașii estimării deoarece costul * acestei comenzi >> the_best_cost (dacă the_best_cost > 0) * În alt caz, returnează costul estimat (>=0) */ plutitor static est_cost_order ( i4_t * res_row_num ) { MASK Depend = _AllTblMsk ; i4_t tbl_num , prdc_num , i , real_num , ColNum ; float cost_all = 0,0 , row_num = 1,0 ; float ind_best_sel , sel ; SP_Ind_Info * cur_ind_info ; /* estimarea costului scanării tabelelor */ pentru ( tbl_num = 0 ; tbl_num < număr_de_tablete ; tbl_num ++ ) { ind_best_sel = 1,0 ; real_num = cur_tbl_order [ tbl_num ]; TblAllBits [ tbl_num ] = Depend = BiTOR ( Depend , TblBits [ real_num ]); /* init of array pentru informații despre culums */ pentru ( i = 0 ; i < tab_col_num [ real_num ]; i ++ ) col_stat [ i ]. Sel = 1,0 ; /* verificarea informațiilor despre SP pentru tabelul curent */ pentru ( prdc_num = 0 ; prdc_num < number_of_SPs ; prdc_num ++ ) if ( ! ( SPs [ prdc_num ]. flag ) /* acest predicat nu a fost încă folosit */ && CAN_BE_USED ( SPs [ prdc_num ]. Depinde , Depinde ) /* predicatul poate fi folosit acum */ ) { SP- uri [ prdc_num ]. steag ++ ; cur_ind_info = ( SPs_indexes [ real_num ]) + prdc_num ; if ( cur_ind_info -> Sel ) { /* acest predicat este SP pentru tabelul curent */ ColNum = cur_ind_info -> ColNum ; if ( col_stat [ ColNum ]. Sel > cur_ind_info -> Sel ) { col_stat [ ColNum ]. Sel = cur_ind_info -> Sel ; if ( cur_ind_info -> IndExists /* există index pentru coloana acestui SP */ && col_stat [ ColNum ]. Sel < ind_best_sel ) ind_best_sel = col_stat [ ColNum ]. Sel ; } } } /* găsirea selectivității comune a tuturor predicatelor simple pentru tabelul curent */ pentru ( i = 0 , sel = 1,0 ; i < tab_col_num [ real_num ]; i ++ ) sel *= col_stat [ i ]. Sel ; /* adăugarea selectivității implicite pentru restul predicatelor */ pentru ( prdc_num = number_of_SPs ; prdc_num < number_of_disjuncts ; prdc_num ++ ) if ( ! ( SPs [ prdc_num ]. flag ) /* acest predicat nu a fost încă folosit */ && CAN_BE_USED ( SPs [ prdc_num ]. Depend , Depend ) /* predicatul poate fi folosit acum */ ) { SP- uri [ prdc_num ]. steag ++ ; sel *= DEFAULT_SEL ; } number_of_scanned_rows [ tbl_num ] = number_of_rows [ real_num ] * ind_best_sel * row_num ; /* number_of_scanned_rows [i] - numărul estimat de rânduri citite din i-lea tabel */ cost_all += number_of_scanned_rows [ tbl_num ] + OPEN_SCAN_COST * row_num ; row_num *= number_of_rows [ real_num ] * sel ; } /* pentru tbl_num: gestionarea tabelelor */ pentru ( prdc_num = 0 ; prdc_num < number_of_disjuncts ; prdc_num ++ ) SP- uri [ prdc_num ]. steag = 0 ; /* adăugarea costului tuturor subinterogărilor */ pentru ( prdc_num = 0 ; prdc_num < number_of_disjuncts ; prdc_num ++ ) { pentru ( tbl_num = 0 ; tbl_num < număr_de_tablete ; tbl_num ++ ) if ( CAN_BE_USED ( SPs [ prdc_num ]. SQ_deps , TblAllBits [ tbl_num ])) rupe ; assert ( numar_tbl < numar_tabele ); /* tbl_num - numărul ultimului (în ordine) tabel * * care este referit în predicat */ cost_all += SP -uri [ prdc_num ]. SQ_cost * număr_de_rânduri_scanate [ tbl_num ]; } * res_row_num = ( row_num < 1.0 ) ? 1 : (( row_num < FLT_MAX_LNG ) ? ( i4_t ) row_num : MAX_LNG ); return cost_all ; } /* est_cost_order */Aici cur_tbl_order este un vector familiar din exemplul anterior care conține ordinea curentă a tabelului.
Pe măsură ce numărul de tabele din interogare crește, numărul de permutări posibile crește cu n! , prin urmare, timpul de evaluare pentru fiecare dintre ele crește proporțional și . Acest lucru face problematică optimizarea interogărilor bazate pe un număr mare de tabele. În căutarea unei soluții la această problemă, în 1991 Kristin Bennett, Michael Ferris, Yannis Ioannidis au propus utilizarea unui algoritm genetic pentru optimizarea interogărilor, care oferă o soluție suboptimă în timp liniar.
Când se utilizează un algoritm genetic, este examinată doar o parte a spațiului de permutare. Tabelele care participă la interogare sunt codificate în cromozomi. Sunt mutați și încrucișați. La fiecare iterație, recuperarea cromozomilor este efectuată pentru a obține o permutare semnificativă a tabelelor și o selecție de cromozomi care oferă estimări minime de cost. Ca urmare a selecției, rămân doar acei cromozomi care dau o valoare mai mică a funcției de cost comparativ cu iterația anterioară. Astfel, are loc cercetarea și găsirea minimelor locale ale funcției de cost. Se presupune că minimul global nu oferă avantaje semnificative față de cel mai bun minim local. Algoritmul se repetă pentru mai multe iterații, după care se selectează cea mai eficientă soluție.
Atunci când se evaluează planurile de execuție a interogărilor, sunt explorate modalități alternative de realizare a îmbinărilor relaționale. Metodele de realizare a conexiunilor diferă ca eficiență, dar au limitări în aplicare.
În cazul buclelor imbricate, bucla exterioară preia toate rândurile din tabelul exterior și apelează bucla interioară pentru fiecare rând găsit. Bucla interioară caută rânduri în tabelul interior pe baza condițiilor de îmbinare și a datelor buclei exterioare. Buclele pot fi imbricate de un număr arbitrar de ori. În acest caz, bucla interioară devine bucla exterioară pentru bucla următoare și așa mai departe.
Când se evaluează diferitele ordine de execuție ale buclelor imbricate, pentru a minimiza supraîncărcarea apelării buclei interioare, este de preferat ca bucla exterioară să scaneze mai puține rânduri decât cea interioară.
Pentru a selecta un index pentru fiecare tabel, în primul rând, se găsesc toți indicii potențiali care pot fi utilizați în interogarea în studiu. Deoarece cheile dintr-un index sunt ordonate, preluarea eficientă din acesta se poate face numai în ordine lexicografică . În acest sens, alegerea unui index se bazează pe prezența unor restricții pentru coloanele incluse în index, începând de la prima.
Pentru fiecare coloană inclusă în index, începând de la prima, se caută constrângeri din întregul set de constrângeri pentru tabelul dat, inclusiv condițiile de îmbinare. Dacă nu pot fi găsite constrângeri pentru prima coloană a indexului, atunci indexul nu este utilizat (altfel ar trebui scanat întregul index). Dacă nu pot fi găsite constrângeri pentru următoarea coloană, atunci căutarea se încheie și indexul este acceptat.
La evaluarea planurilor de execuție, se examinează seturi alternative de indici care pot fi utilizați pentru eșantionare. În cazul buclelor imbricate, bucla cea mai exterioară nu poate folosi niciun index care este constrâns de cel puțin o condiție de îmbinare, deoarece niciuna dintre condițiile de îmbinare nu este complet definită atunci când se execută bucla. Bucla interioară nu poate folosi niciun index cu restricții care sunt incompatibile cu condițiile de îmbinare.
Indicii rămași sunt clasați după numărul de rânduri preluate și lungimea cheii. Evident, numărul de rânduri recuperate depinde de limite. Cu cât numărul de rânduri recuperate este mai mic și cu cât lungimea cheii este mai mică, cu atât rangul este mai mare.
Pentru eșantionare se utilizează indicele cu cel mai înalt clasament.
Pentru unele interogări de agregare, întregul index poate fi scanat. În special:
Dacă ordinea de preluare solicitată se potrivește cu ordinea unuia sau mai multor indecși , atunci se evaluează dacă unul dintre acești indecși poate fi scanat în întregime.
Dacă indexul conține toate coloanele necesare pentru a produce rezultatul , atunci nu are loc nicio scanare a tabelului. Dacă optimizatorul folosește acest factor, atunci este posibil să se accelereze preluarea din tabel pentru interogări specializate prin includerea coloanelor redundante în index, care vor fi preluate direct la căutarea după cheie. Această metodă de accelerare a interogărilor trebuie utilizată cu grijă.
Dacă tabelele care se unesc au indici pe câmpurile comparate sau dacă unul sau ambele tabele sunt suficient de mici pentru a fi sortate în memorie, atunci îmbinarea poate fi efectuată folosind o îmbinare. Ambele seturi de date sortate sunt scanate și căutate pentru aceleași valori. Datorită sortării, îmbinarea este mai eficientă decât buclele imbricate pe cantități mari de date, dar planul de execuție nu poate începe cu o îmbinare.
O estimare a numărului de rânduri extrase dintr-un tabel este utilizată pentru a decide dacă se efectuează o scanare completă a tabelului în loc de acces la index. Decizia este luată pe baza faptului că fiecare pagină index citită de pe disc implică 1 sau mai multe poziționări și 1 sau mai multe citiri de pagină de tabel. Deoarece indexul conține și pagini fără frunze, extragerea a mai mult de 0,1-1% din rândurile din tabel este de obicei mai eficientă pentru a efectua o scanare completă a tabelului.
O evaluare mai precisă va fi obținută pe baza următorilor indicatori:
SGBD-ul încearcă să organizeze secvenţial stocarea blocurilor de date dintr-un tabel pentru a elimina supraîncărcarea de poziţionare a unei scanări complete ( Oracle DBMS utilizează pre-alocarea de spaţiu pe disc pentru fişierele de date). Eficiența unei scanări complete este, de asemenea, crescută prin citirea înainte . Cu read-ahead , DBMS emite simultan comenzi de citire către mai multe blocuri către memoria externă. Scanarea începe când oricare dintre blocuri este citit. În același timp, citirea blocurilor rămase continuă. Eficiența este atinsă datorită paralelismului citirii și scanării.
Dacă DBMS rulează pe mai multe procesoare, atunci sortările pot fi efectuate în paralel pentru a reduce timpul de răspuns. O condiție prealabilă pentru aceasta este capacitatea de a plasa toate datele preluate în RAM. Pentru a efectua sortarea, datele extrase sunt împărțite în fragmente, al căror număr este egal cu numărul de procesoare. Fiecare dintre procesoare realizează sortarea pe unul dintre fragmente independent de celelalte. La pasul final, fragmentele sortate sunt îmbinate sau îmbinarea este combinată cu emiterea de date către clientul DBMS.
Dacă SGBD rulează pe mai multe noduri, atunci sortarea este efectuată în paralel de către fiecare dintre nodurile implicate în execuția interogării. Apoi fiecare dintre noduri își trimite fragmentul la nodul responsabil cu emiterea de date către client, unde fragmentele primite sunt îmbinate.
RDBMS folosește statistici pentru a estima numărul potențial de rânduri care trebuie extrase dintr-un tabel . Statistica are forma de histograme pentru fiecare coloană a tabelului, unde scara de valori este situată orizontal, iar înălțimea coloanei indică estimarea numărului de rânduri ca procent din numărul total de rânduri.
Astfel, dacă din tabel sunt preluate rânduri cu valoarea coloanei C cu constrângerea [V1, V2], atunci putem estima numărul de rânduri care se încadrează în acest interval. Algoritmul pentru estimarea numărului de rânduri de extras este următorul:
De regulă, SGBD nu știe și nu poate ști numărul exact de rânduri din tabel (chiar și pentru interogarea SELECT COUNT(*) FROM TABLE, indexul primar este scanat), deoarece baza de date poate stoca mai multe imagini ale aceluiași tabel. cu un număr diferit de rânduri în același timp. . Următoarele date sunt utilizate pentru a estima numărul de rânduri:
Statisticile pot fi stocate și pe bază de angajamente. În acest caz, fiecare interval conține scorul total al tuturor intervalelor anterioare plus propriul său scor. Pentru a obține o estimare a numărului de rânduri pentru constrângerea [V1, V2], este suficient din estimarea intervalului în care se încadrează V2, să scădem estimarea intervalului în care se încadrează V1.
Colectarea statisticilor pentru trasarea histogramelor este realizată fie prin comenzi speciale DBMS , fie prin procese de fundal DBMS . În același timp, având în vedere faptul că baza de date poate conține o cantitate semnificativă de date, se face un eșantion mai mic din întreaga populație generală de rânduri. Evaluarea reprezentativității (fiabilității) eșantionului poate fi efectuată, de exemplu, conform criteriului acordului Kolmogorov .
Dacă datele din tabel se modifică semnificativ într-o perioadă scurtă de timp, atunci statisticile nu mai sunt relevante și optimizatorul ia decizii incorecte cu privire la scanarea completă a tabelului. Comportamentul bazei de date ar trebui să fie planificat pentru a menține statisticile actualizate sau pentru a nu utiliza optimizarea bazată pe statistici.
| Bază de date | |
|---|---|
| Concepte |
|
| Obiecte |
|
| Chei | |
| SQL |
|
| Componente | |