Rezolvarea blocajelor cu indici și partiții SQL

În prima lecție din Explicarea indicilor SQL, am învățat că interogările SELECT sunt mai rapide atunci când datele sunt deja ordonate după valorile unor coloane specifice.

În a doua lecție, am învățat structura de bază a indicilor B-tree și cum să le folosim pentru a reduce volumul de date pe care le accesăm în timp ce executăm o interogare. De asemenea, ne-am dat seama cum să implementăm interogări care unesc mai multe tabele și cum indexurile pot accelera astfel de interogări.

De asemenea, am evidențiat două scenarii în care utilizarea indicilor în SQL este utilă. Când indecșii acoperă indecși, care conțin toate coloanele din interogare - din condițiile WHERE , condițiile JOIN și lista SELECT - evităm să citim în întregime tabelul corespunzător. Alternativ, indexurile pot ajuta atunci când reduc numărul de blocuri de date accesate la o mică parte din dimensiunea tabelului.

În caz contrar, este mai eficient să scanezi întregul tabel decât să citești dintr-un index și să sări aleatoriu înainte și înapoi la rândurile corespunzătoare ale tabelului.

Interogări de interval SQL

Interogările care pot profita de indici includ de obicei condiții care reduc semnificativ intervalul de valori posibile pe care una sau mai multe coloane le pot lua. Interogările de interval restricționează datele în funcție de condiții precum „valoarea coloanei A trebuie să fie între X și Y”.

Un bun exemplu în acest sens este interogarea din exercițiul 4 din a doua lecție:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

Aici avem două game. Primul este intervalul de date, perioada cuprinsă între 13 august 2020 și 14 august 2020. Al doilea este cel mai mic interval numeric posibil. Conditia este echivalenta cu r.HotelID BETWEEN 3 AND 3 .

Exercițiul 1: Perioade (interogări de date și intervale de timp)

Să adăugăm o coloană numită CheckInTime la tabelul Reservations . Puteți vedea exemple de date în această foaie de calcul. Observați că există un singur index care acoperă atât CheckInTime , cât și ClientId .

Scrieți o interogare care să returneze numele clienților care s-au înregistrat pe 15 august 2020.

Dezvoltatorii SQL neexperimentați scriu de obicei următoarea interogare:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE TO_DATE(r.CheckInTime, 'YYYY-MM-DD') = '2020-08-15';

Ei presupun că execuția interogării ar arăta astfel:

 Get first row from IX_CheckInTime_ClientID where TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' While found and TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName Get next row from IX_CheckInTime_ClientID

Problema este că nici un singur RDBMS la momentul scrierii acestui articol nu este capabil să genereze un astfel de plan de execuție. Ei văd TO_DATE (sintaxa Oracle) ca o funcție care transformă valoarea coloanei CheckInTime în ceva neindexat. Deci, planurile de execuție pe care tind să le genereze arată astfel:

 For each row from IX_CheckInTime_ClientID If TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' then Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName

Executarea acestui lucru ar fi mai rapidă decât citirea tuturor rândurilor din tabelul Reservations , deoarece rândul index este mai îngust decât rândul tabelului. Un rând mai mic înseamnă că mai puține blocuri ar trebui să fie accesate de pe disc.

Știm însă că primul plan de execuție ar fi mult mai eficient. Pentru a convinge RDBMS-ul nostru să folosească această abordare, trebuie să rescriem interogarea:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.CheckInTime >= TO_DATE('2020-08-15 00:00:00', 'YYYY-MM-DD HH:MI:SS') AND r.CheckInTime < TO_DATE('2020-08-16 00:00:00', 'YYYY-MM-DD HH:MI:SS');

Aceasta este o interogare adecvată, una pe care orice RDBMS bun o înțelege. RDBMS-ul nostru își dă seama că vrem date din tabelul Reservations în care valoarea CheckInTime — nu ceva derivat din aceasta — aparține unui interval bine definit. Planul de execuție pe care îl generează ar fi mai degrabă:

 Get first row from IX_CheckInTime_ClientID where CheckInTime >= '2020-08-15 00:00:00' While found and CheckInTime < '2020-08-16 00:00:00' Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName Get next row from IX_CheckInTime_ClientID

Asta ne dorim cu adevărat: să folosim nu numai indicele în sine, ci și faptul că este sortat.

Exercițiul 2: LIKE Cu un wildcard la început

De data aceasta, detectivul nostru vine la hotel cu informații vagi despre suspect: doar că numele de familie se termină cu „-fiu”. Detectivul vrea numele și prenumele tuturor acestor oaspeți:

 SELECT FirstName, LastName FROM Clients WHERE LastName LIKE '%son';

Pentru tabelul Clients și un index pe LastName , vom folosi această foaie de calcul. Notați rezultatele pe care le-ar returna interogarea. Gândiți-vă la diferite abordări pe care le puteți aplica.

Abordarea scanării tabelului

Cea mai simplă strategie este să citiți toate datele din tabel și să scrieți numele oaspeților atunci când numele lor de familie se termină cu „-fiul”:

 For each row from Clients If LastName like '%son' then write down FirstName, LastName

Aici, ar trebui să citim întregul tabel secvenţial.

Utilizarea unui index

Să încercăm să profităm de indexul din coloana LastName . Accesați foaia IX_LastName, utilizați-o pentru a găsi toți clienții care îndeplinesc criteriul dat și notați-le numele.

Se pare că trebuie să citiți întregul index pentru a găsi toți Anderson, Robinson și Thompson din tabel. Este mai bine decât să folosești o scanare a tabelului? Pe lângă citirea întregului index, mai trebuia să găsiți, pentru fiecare intrare care se potrivește, rândul corespunzător din tabel folosind valoarea rowAddress , apoi notați FirstName de acolo:

 For each row from IX_LastName If LastName like '%son' then Fetch Clients.* where RowAddress = IX_LastName.RowAddress Write down FirstName, LastName

Pentru noi, a fost mai simplu și mai rapid să citim tabelul secvenţial. Pentru RDBMS-ul nostru, ar depinde de procentul de rânduri care îndeplinesc criteriile. Dacă există doar o mână de Anderson, Robinson și Thompson într-un tabel mare, un RDBMS ar citi mai puține blocuri de date din intrări de index mult mai restrânse, chiar dacă trebuie să citească câteva blocuri din tabel atunci când este găsită o potrivire. În caz contrar, scanarea tabelului durează mai puțin.

Ordonarea datelor în index nu oferă niciun ajutor cu o astfel de interogare. Dimensiunea mai mică a rândului index poate fi de ajutor, dar numai uneori.

Exercițiul 3: LIKE Cu un wildcard la sfârșit

Data viitoare când vine detectivul nostru, trebuie să găsim toți clienții ale căror nume de familie încep cu „Rob-”.

 SELECT FirstName, LastName FROM Clients WHERE LastName LIKE 'Rob%';

Încercați să extrageți datele care corespund interogării din aceeași foaie de calcul.

Dacă ați folosit abordarea scanării tabelelor, ați ratat ocazia de a profita din plin de indexul IX_LastName . Este mult mai rapid să localizați prima intrare din index care începe cu „Rob-” (Roberts), să citiți rândurile ulterioare (atât LastName , cât și Robinsons) și să vă opriți când Numele de familie nu mai corespunde criteriului:

 Get first row from IX_LastName where LastName <= 'Rob' While found and LastName < 'Roc' Fetch Clients.* where rowAddress = IX_LastName.rowAddress Write down FirstName, LastName Get next from IX_LastName

În acest caz, după căutarea în arborele B pentru prima intrare, citim doar intrările care îndeplinesc criteriul. Încetăm să citim de îndată ce citim un nume care nu corespunde criteriului.

Abordarea problemelor de scalare a arborelui B

De obicei, atunci când implementăm o nouă bază de date, există câteva tabele de căutare populate și tabele tranzacționale goale. Sistemul funcționează fără probleme de la început, mai ales dacă am respectat bunele practici de proiectare a bazelor de date prin normalizarea tabelelor; crearea de chei primare, străine și unice; și suportarea cheilor străine cu indecșii corespunzători.

După câteva luni sau ani, când volumul de date a crescut semnificativ complexitatea sistemului și a bazei de date, începem să observăm o degradare a performanței. Apar păreri despre motivul pentru care sistemul a încetinit și ce trebuie făcut în acest sens.

Opinia populară este adesea că dimensiunea bazei de date este principalul vinovat. Soluția pare să fie eliminarea datelor istorice de care nu avem nevoie zilnic și plasarea lor într-o bază de date separată pentru raportare și analiză.

Să explorăm mai întâi ipoteza principală.

Interogări în domeniul SQL: Timpul de execuție depinde de dimensiunea tabelului?

Luați în considerare o interogare tipică de interval dintr-un singur tabel:

 SELECT Column1, …, ColumnN FROM Table WHERE Column BETWEEN X AND Y;

Presupunând că există un index pe Column , planul optim de execuție este:

 Get first row from IX_Column where Column between X and Y While found and Column <= Y Fetch Table.* where rowAddress = IX_Column.rowAddress Write down Column1, …, ColumnN Get next row from IX_Column

Să numărăm blocurile pe care un RDBMS va trebui să le citească pentru a returna aceste date.

Partea Get first row este implementată de căutarea B-tree pe care am introdus-o în a doua lecție. Numărul de blocuri pe care trebuie să le citească este egal cu adâncimea arborelui B. După aceea, citim articolele ulterioare de la nivelul frunzei indexului.

Cu interogările OLTP, de obicei, toate rezultatele vor fi găsite într-un singur bloc de index (uneori două, dar rareori mai multe). În plus, pentru fiecare intrare de index, avem acces la un bloc din tabel pentru a găsi rândul corespunzător pe baza adresei acestuia. Unele rânduri de tabel ar putea fi în același bloc de tabel pe care l-am încărcat deja, dar pentru a simplifica estimarea, să presupunem că încărcăm un bloc nou de fiecare dată.

Deci formula este:

B = D + 1 + R

B este numărul total de blocuri citite, D este adâncimea arborelui B și R este numărul de rânduri returnate de interogare.

Singurul parametru care depinde de numărul de rânduri din tabel este D, adâncimea arborelui B.

Pentru a simplifica calculele și a face un punct, presupunem că 1.000 de intrări de index se încadrează într-un singur bloc. D = 1 atâta timp cât există mai puțin de 1.000 de rânduri în tabel. Pentru tabelele care conțin tranzacții comerciale, acesta ar putea fi cazul în prima zi lucrătoare după implementarea sistemului. În curând, adâncimea arborelui B va crește. Atâta timp cât există mai puțin de 1 milion de rânduri în tabel, indexul va consta din două niveluri.

Dacă suntem deranjați de timpii lenți de răspuns la baza de date și dăm vina pe volumul de date pentru acest lucru, rețineți că tabelele de tranzacții au adesea doar milioane de rânduri. Deoarece doar 1 milion de rânduri se potrivesc unui indice de arbore B cu două niveluri, adâncimea trebuie să fie de cel puțin trei. Adâncimea nu va crește până la patru decât dacă există mai mult de 1 miliard de rânduri în tabel. Acum avem o estimare mai precisă:

B = 4 + R

Dacă R este mic, scăderea adâncimii arborelui B înapoi la două ar accelera semnificativ interogarea. Când căutăm după o valoare a cheii primare sau unice, sistemul va citi patru blocuri în loc de cinci, ceea ce reprezintă o îmbunătățire cu 20%. Dacă interogarea returnează mai multe rânduri, este posibil ca îmbunătățirea să nu fie vizibilă. Problema este că, pentru multe aplicații, este posibil să nu putem susține operațiunile de afaceri necesare păstrând mai puțin de 1 milion de tranzacții în baza de date.

Deci concluzia pare să fie că dimensiunea mesei nu contează; cu alte cuvinte, mutarea datelor istorice este o pierdere de timp și resurse.

Dar nu atât de repede: să aflăm mai multe despre structura unui index B-tree și despre cum îl afectează modificările datelor.

Detalii de implementare a indexului B-tree

În acoperirea noastră a indicilor arborelui B din a doua lecție, am văzut că toate nivelurile unui arbore echilibrat sunt ordonate (fizic) după valorile coloanei cheie. Cu toate acestea, atunci când dorim să inserăm, să actualizăm sau să ștergem un articol, de multe ori trebuie să mutăm o cantitate mare de date pentru a păstra ordinea.

Să presupunem că inserăm în mijlocul unui bloc care se întâmplă să fie plin. Trebuie să împărțim blocul, să rearanjam datele și, uneori, chiar să actualizăm datele la un alt nivel de arbore B, indicând cel curent.

Pentru a face astfel de cazuri mai eficiente, fiecare element index conține pointeri către rândurile precedente și următoare, făcându-l dublu legat. Pentru inserare în general, aceasta înseamnă că scriem elementele noi cât mai aproape de cele precedente și corectăm indicatoarele.

Când trebuie să împărțim și un bloc, trebuie să scriem un nou element în nivelul B-tree anterior. Aceasta este doar o chestiune de corectare a altor câteva indicatoare - nu este nevoie să rescrieți porțiuni mari din arbore. După o divizare, ambele blocuri de date sunt aproximativ pe jumătate pline. În funcție de locul în care există spațiu liber pe disc, blocurile „învecinate” ar putea fi destul de îndepărtate din punct de vedere fizic.

După ceva timp, fragmentarea indexului crește și încetinirea execuției interogării devine vizibilă. Cu un RDBMS care execută interogări așa cum le-am descris, asumarea ordinii și a proximității articolelor devine din ce în ce mai puțin corectă, ceea ce duce la mult mai multe citiri. În cel mai rău caz, cu toate blocurile de date fiind pe jumătate goale, sistemul trebuie să citească de două ori mai multe blocuri.

Întreținerea indicelui B-tree

Leacul pentru aceasta este defragmentarea indexului (sau „reindexarea”). Fiecare RDBMS oferă o caracteristică pentru a recrea un întreg index; după reindexare, indexurile sunt din nou ordonate fizic.

Reindexarea este o operațiune destul de rapidă, chiar dacă citește și scrie un volum mare de date. RDBMS-urile moderne oferă de obicei două moduri de reindexare, cel mai rapid necesitând blocarea tabelelor în timpul procesării. Oricum ar fi, este de preferat să reindexați în orele de vârf. În caz contrar, procesarea ar putea încetini performanța bazei de date.

Ștergerea datelor istorice

Când avem tabele cu miliarde sau chiar sute de milioane de rânduri, s-ar putea să nu fie fezabilă finalizarea unei operațiuni de reindexare în timpul orelor de vârf.

Pentru a evita această situație, mutarea datelor istorice dintr-o bază de date OLTP ar putea fi soluția. Cu toate acestea, dacă pur și simplu ștergem rândurile care sunt mai vechi decât un anumit prag, facem indici și mai fragmentați și trebuie să-i reindexăm și mai frecvent.

Partiționare SQL pentru salvare?

Există o modalitate de a evita fragmentarea cauzată de eliminarea datelor istorice, păstrând doar tranzacțiile „active” în baza de date de producție. Ideea pe care o implementează toate RDBMS-urile majore este de a împărți un tabel în bucăți mai mici (numite partiții ) și de a oferi capacitatea de a le adăuga, de a le elimina și chiar de a le comuta între tabele (de exemplu, de la un tabel activ la unul istoric cu același structura).

Să aruncăm o privire la tabelul Reservations așa cum este partiționat în această foaie de calcul. Tabelul este împărțit pe lună, cu numele partițiilor mapate la perioade de date și alte foi de calcul. Pentru a vedea cum se execută o interogare pe un tabel partiționat, vom face câteva exerciții.

Exercițiul 4: Interogare de partiție în SQL

Din foaia de calcul de mai sus, încercați să extrageți datele solicitate de următoarea interogare, fără a utiliza niciun index:

 SELECT HotelID, ReservationID, ClientID, DateFrom, DateTo FROM Reservations WHERE DateFrom BETWEEN TO_DATE('2021-03-01','YYYY-MM-DD') AND TO_DATE('2021-03-03');

Probabil v-ați dat seama că trebuie mai întâi să vă uitați la foaia de mapare a partițiilor și să găsiți partiția care conține rezervări din martie 2021. După aceea, ați deschis partiția corespunzătoare, ați citit secvențial datele și ați filtrat rândurile care nu au satisfăcut condiție.

Deși simplu, probabil că nu ți-a plăcut să păstrezi atât de puține rânduri după ce ai citit atât de multe. Citirea partiției din martie a fost mai bună decât citirea întregului tabel de rezervare, dar totuși nu este ideală. Dar indici?

Indici globali

RDBMS-urile ne permit să creăm un index global pentru a acoperi toate partițiile unui tabel partiționat. Dar nu există nicio diferență între modul în care funcționează indexurile globale și cele obișnuite dedesubt: indexurile globali nu sunt conștienți de partiție. Astfel, interogările CRUD care utilizează un index global nu implică harta partițiilor pentru tabelul său.

Trebuie să actualizăm harta partiției doar atunci când aruncăm o întreagă partiție. Apoi trebuie să eliminăm orice rând din index care indică partiția eliminată. Asta înseamnă că întregul indice global trebuie reconstruit.

O fereastră de întrerupere rămâne necesară deoarece indecșii nu pot fi utilizați până când elementele învechite nu sunt eliminate. Dacă putem abandona în mod regulat partițiile, limitând numărul celor active, atunci operația de reindexare s-ar putea încadra în fereastra de întrerupere. Prin urmare, utilizarea partițiilor ajută la problema inițială prin scurtarea timpului necesar pentru sarcinile de întreținere, inclusiv întreținerea indicilor globali.

Dar dacă tot nu ne putem permite întreruperea?

Indici partiționați la nivel global

Această strategie rezolvă această problemă: pur și simplu partițiem indexul în același mod în care partițiem tabelul. În foile de calcul la care se leagă foaia de calcul de partiție, fiecare partiție conține porțiunea sa din tabelul Reservations și o foaie de index numită IX_DateFrom, ambele partiționate de DateFrom .

Pentru a executa interogarea din exercițiul 4, un RDBMS ar privi mai întâi o hartă de partiții index și ar identifica ce partiții conțin date din interval. (În cazul nostru, este doar o partiție de index.) După aceea, va folosi căutări în arborele B, va trece la nivelul frunzei și, în sfârșit, va accesa tabelul folosind adresa de rând corespunzătoare.

Când aruncăm o partiție dintr-un tabel, este suficient să aruncăm partiția corespunzătoare din index. Nu este necesar niciun timp de nefuncționare.

Indici locali

Principalul dezavantaj al indicilor partiționați global este că trebuie să avem grijă să aruncăm atât tabelul, cât și partiția de index corespunzătoare. Există doar un mic cost suplimentar asociat cu citirea și menținerea hărții partițiilor de index în sine.

Indicii locali implică o abordare similară, dar ușor diferită. În loc să partiționăm un singur index global, creăm un index local în interiorul fiecărei partiții de tabel. Procedând astfel, indecșii locali împărtășesc principalul avantaj al indicilor partiționați la nivel global, adică, fără timp de nefuncționare, evitând în același timp dezavantajele acestora.

Pare o soluție perfectă. Dar înainte de a sărbători, să investigăm posibilul plan de execuție a câtorva interogări.

Exercițiul 5: Index partiționat local

Încercați să rulați din nou interogarea, de data aceasta folosind indexul partiționat local pe DateFrom .

Probabil ați folosit acest plan de execuție:

 For all partitions where [StartDateFrom, StartDateTo) intersects ['2021-03-01', '2021-03-03'] Get first row from IX_DateFrom where DateFrom between '2021-03-01' and '2021-03-03' While found and DateFrom < '2021-03-04' Fetch Reservations.* where RowAddress = IX_DateFrom.RowAddress Write down HotelID, ReservationID, ClientID, DateFrom, DateTo Get next row from IX_DateFrom

Suntem norocoși că toate datele aparțin unei singure partiții, așa că a trebuit să parcurgem un singur index local. Dacă perioada ar fi de șase luni, ar trebui să citim șase indici locali.

Exercițiul 6: În contrast

Sarcina dvs. este să utilizați din nou harta partiției Rezervări, de data aceasta pentru a face o listă cu perioadele în care Clientul 124 a vizitat Hotelul 1:

 SELECT DateFrom, DateTo FROM Reservations WHERE ClientID = 124 AND HotelID = 1;

Aici putem vedea principalul dezavantaj al indicilor locali. A trebuit să citim foaia de index local IX_HotelID_CientID din fiecare partiție a tabelului Reservations :

 For all partitions Get first row from IX_HotelID_ClientID where ClientID = 124 and HotelID = 1 While found and ClientID = 124 and HotelID = 1 Fetch Reservations.* where RowAddress = IX_HotelID_ClientID.RowAddress Write down DateFrom, DateTo Get next row from IX_HotelID_ClientID

Această execuție ar citi în mod clar mai multe blocuri și ar dura mai mult timp decât dacă tabelul nu ar fi partiționat.

Deci, deși am găsit o modalitate de a menține starea de sănătate a indicilor noștri în perioada de vârf, strategia a făcut, de asemenea, unele dintre interogările noastre mai lente.

Dacă modelul nostru de afaceri ne permite să păstrăm un număr mic de partiții sau cel puțin cele mai frecvente interogări conțin criterii care să permită RDBMS să citească doar una sau două partiții, această soluție ar putea fi cea de care avem nevoie. În caz contrar, ar fi mai bine să evităm partiționarea și să lucrăm la îmbunătățirea modelului de date, a indexurilor și a interogărilor și la îmbunătățirea serverului bazei de date.

Indecși în SQL: Ce să învățați în continuare

Acesta este sfârșitul călătoriei noastre. În SQL Indexes Explained, m-am concentrat pe implementarea indexului care este comună tuturor RDBMS-urilor moderne. De asemenea, m-am concentrat pe subiecte de care sunt interesați dezvoltatorii de aplicații, în detrimentul subiectelor care privesc de obicei administratorii de baze de date. Acesta din urmă ar face bine să cerceteze impactul factorului de umplere asupra fragmentării indexului, dar oamenii din ambele roluri vor găsi probabil util să citească mai multe despre:

• Memorarea în cache a datelor și a indexului
• Structuri de index non-B-tree, cum ar fi indici hash, GiST, bitmap și coloane
• Indecși grupați (cunoscut sub numele de tabele organizate pe index în Oracle)
• Indici funcționali
• Indici parțiali

Abordarea partiționării pe care am discutat-o ​​este partiționarea în intervale . Este cel mai folosit tip de partiționare, dar există și altele, cum ar fi partiționarea hash și partiționarea listă. De asemenea, unele RDBMS oferă opțiunea de mai multe niveluri de partiționare.

În cele din urmă, dezvoltatorii SQL ar face bine să exploreze alte subiecte importante legate de execuția interogărilor RDBMS - mai întâi, analizarea interogărilor, apoi compilarea planului de execuție bazat pe costuri, stocarea în cache și reutilizarea.

Pentru cele patru RDMBS cu care am experiență, recomand aceste resurse ca următorii pași:

Oracol

• Prezentare generală a Optimizer
• Indici și tabele organizate pe index
• Gestionarea indicilor
• Prezentare generală a partițiilor
• Ghid de partiţionare
• Întreabă-l pe Tom

PostgreSQL

• Procesarea interogărilor
• Indecși în PostgreSQL
• Indecși în PostgreSQL (documentație oficială)
• Managementul tamponului
• Partiționarea tabelului
• Ghid de partiţionare

Microsoft SQL Server

• Arhitectura de procesare a interogărilor
• Indici
• Tabele și indici partiționați

MySQL/MariaDB

• Înțelegerea planului de execuție a interogărilor
• Optimizare și indici
• Partiționare - Noțiuni de bază
• Partitionare - Documentatie
• Documentație MariaDB: optimizarea interogărilor și indici