Indeșii SQL explicați, Pt. 2

În prima lecție din SQL Indexes Explained , am învățat să folosim sortarea pentru a accelera recuperarea datelor. În timp ce execuția interogării noastre este mai rapidă după sortarea rândurilor, sortarea implică citirea fiecărui rând cel puțin o dată și mutarea lor. Acest lucru face ca metoda să fie mai lentă și mai puțin eficientă decât simpla citire secvențială a întregului tabel.

Concluzia logică pare să fie că ar trebui să menținem copii sortate — pe care le vom numi oficial indecși SQL , prefixați cu IX_ — ale unui tabel dat. Ar fi atunci aplicabili algoritmii de regăsire din primul articol și nu ar fi nevoie să sortăm tabelul înainte de a începe.

Indexul ca copie sortată a tabelului

Să aruncăm o privire asupra implementării literale a acestei idei, folosind din nou Google Sheets. Foaia noastră de calcul pentru rezervare devine o colecție de cinci foi care conțin aceleași date. Fiecare foaie este sortată în funcție de diferite seturi de coloane.

Exercițiile de aici sunt menite să fie mai puțin exigente decât în ​​articolul anterior tutorial de index SQL - pot fi făcute mai mult prin simțire decât prin cronometru și număr de rânduri. Unele exerciții vor părea foarte asemănătoare, dar de data aceasta explorăm:

1. Cum să preluați mai eficient datele atunci când utilizați indecși separati, mai degrabă decât tabele primare sortate
2. Cum se menține ordinea în fiecare index și tabel atunci când se modifică datele

Tutorialul anterior s-a concentrat pe citiri, dar în multe dinamice comune a datelor din lumea reală — inclusiv rezervările noastre la hotel — trebuie să luăm în considerare efectele indexării asupra performanței de scriere, atât pentru inserarea de date noi, cât și pentru actualizarea datelor existente.

Exercițiu preliminar: Anularea unei rezervări

Pentru a înțelege performanța indexului SQL folosind strategia tabelului sortat, sarcina dvs. este să ștergeți o rezervare pentru Clientul 12, din 22 august 2020, în Hotel 4. Rețineți că trebuie să eliminați un rând din toate copiile de tabelul și mențineți sortarea corectă.

Terminat? Ar trebui să fie clar că ideea de a păstra mai multe copii sortate ale tabelului nu este atât de bună pe cât părea. Dacă mai aveți îndoieli, puteți încerca și să reintroduceți rezervarea pe care tocmai ați șters-o sau să modificați data unei rezervări existente.

În timp ce copiile sortate ale tabelului permit o recuperare mai rapidă, așa cum am aflat tocmai acum, modificarea datelor este un coșmar. Ori de câte ori trebuie să adăugăm, să ștergem sau să actualizăm un rând existent, va trebui să recuperăm toate copiile tabelului, să găsim un rând și/sau locul în care ar trebui să fie adăugat sau mutat și, în final, să mutăm blocuri de date.

Indecși SQL folosind adrese de rând

Această foaie de calcul conține indici care utilizează o abordare diferită. Rândurile de index sunt încă sortate în funcție de criterii specifice, dar nu păstrăm toate celelalte informații din rândul de index. În schimb, păstrăm doar „adresa rândului”, adresa rândului din foaia Rezervări – reprezentând tabelul în sine – în coloana H.

Toate implementările RDBMS utilizează o capacitate la nivel de sistem de operare pentru a găsi rapid blocul de pe disc folosind o adresă fizică. Adresele de rând constau de obicei dintr-o adresă de bloc plus poziția rândului în bloc.

Să facem câteva exerciții pentru a afla cum funcționează acest design de index.

Exercițiul 1: Toate rezervările unui client

Ca și în primul articol, veți simula execuția următoarei interogări SQL:

 SELECT * FROM Reservations WHERE ClientID = 12;

Din nou, există două abordări rezonabile. Primul este pur și simplu să citească toate rândurile din tabelul Rezervări și să preia numai rândurile care corespund criteriilor:

 For each row from Reservations If Reservations.ClientID = 12 then write down Reservations.*

A doua abordare implică citirea datelor din foaia IX_ClientID și, pentru orice articol care corespunde criteriilor, găsirea unui rând în tabelul Rezervare pe baza valorii rowAddress:

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

Aici, expresia Get first row from este implementată printr-o buclă similară cu cele văzute în articolul anterior:

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

Puteți găsi un rând cu o anumită rowAddress glisând în jos până când găsiți un rând sau folosind un filtru în coloana rowAddress.

Dacă ar fi doar câteva rezerve de returnat, abordarea folosind indexul ar fi mai bună. Cu toate acestea, cu sute – sau uneori chiar doar zeci – de rânduri care urmează să fie returnate, simpla folosire directă a tabelului Rezervări poate fi mai rapidă.

Volumul citirilor depinde de valoarea ClientID. Pentru cea mai mare valoare, trebuie să citiți întregul indice, în timp ce pentru cea mai mică valoare, este la începutul indicelui. Valoarea medie este jumătate din numărul de rânduri.

Vom reveni la acea parte mai târziu și vom prezenta o soluție eficientă. Deocamdată, să ne concentrăm asupra piesei după ce găsiți primul rând care corespunde criteriilor noastre.

Exercițiul 2: Numărul de rezervări care încep la o dată dată

Sarcina este de a număra numărul de check-inuri pe 16 august 2020, folosind noul design de index.

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16','YYYY-MM-DD');

Abordarea utilizării indexului adecvat pentru numărare este superioară unei scanări de tabel, indiferent de numărul de rânduri implicate. Motivul este că nu trebuie să accesăm deloc tabelul Rezervări - avem toate informațiile de care avem nevoie în index în sine:

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

Algoritmul este practic același cu cel care utilizează tabele sortate. Cu toate acestea, rândul index este mult mai scurt decât rândul tabelului, astfel încât RDBMS-ul nostru ar trebui să citească mai puține blocuri de date de pe disc.

Exercițiul 3: Ancheta penală (Lista de oaspeți dată hotelului și intervalului de date)

Să pregătim o listă cu oaspeții care au sosit la Hotel 3 în zilele de 13 și 14 august 2020.

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13','YYYY-MM-DD') AND TO_DATE('2020-08-14','YYYY-MM-DD') ) AND HotelID = 3;

Putem citi toate rândurile din tabelul Rezervări sau putem folosi unul dintre indecșii disponibili. După ce am făcut același exercițiu cu un tabel sortat după criterii specifice, am aflat că indexul IX_HotelID_DateFrom este cel mai eficient.

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

Putem proiecta un index și mai eficient?

Accesăm tabelul datorită valorii ClientID , singura informație de care avem nevoie pentru lista de invitați pe care o raportăm. Dacă includem acea valoare în indexul SQL, nu trebuie să accesăm deloc tabelul. Încercați să pregătiți o listă care citește doar doar un astfel de index, IX_HotelID_DateFrom_ClientID :

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

Când indexul conține toate informațiile necesare pentru executarea interogării, spunem că indexul acoperă interogarea.

Exercițiul 4: Lista numelor oaspeților în loc de ID-uri

O listă de identități de oaspeți ar fi inutilă pentru un ofițer de poliție care investighează o crimă. Trebuie să oferim nume:

 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;

Pentru a furniza o listă, pe lângă datele din tabelul Reservations , avem nevoie și de un tabel Clients care să conțină informații despre oaspeți, care pot fi găsite în această fișă Google.

Acest exercițiu este similar cu cel anterior, la fel și abordarea.

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

Expresia Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID poate fi implementată prin scanarea tabelului sau folosind indexul nostru. Dacă folosim o scanare a tabelului, pentru fiecare ClientID din bucla While , ar trebui să citim în medie jumătate de rânduri din tabelul Clients :

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

Implementarea indexului pe care am considerat-o până acum – să-i spunem o implementare a indexului „plată” – nu ar fi prea utilă. Ar trebui să citim același număr de rânduri (deși rânduri mai mici) din index, apoi să sărim la rândul din Clients folosind RowAddress :

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

Notă: aici, PK se referă la „cheia principală”, un termen pe care îl vom explora mai târziu în serie.

Există vreo modalitate de a realiza acest lucru fără a fi nevoie să citiți atât de multe rânduri? Da, pentru asta sunt exact indicii B-tree.

Indici de arbore echilibrat (arbore B).

Să împărțim rândurile din Clients_PK_Flat în blocuri cu patru rânduri și să creăm o listă care să conțină valoarea ultimului ClientID din blocul și adresa de la începutul blocului (coloana IndexRowAddress ). Structura de date a indexului bazei de date rezultată - o puteți găsi în foaia Clients_PK_2Levels. Încercați modul în care noua structură vă ajută să găsiți un client care are un ClientID de 28. Algoritmul ar trebui să arate astfel:

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

Probabil v-ați dat seama că putem adăuga un alt nivel. Nivelul 1 este format din patru rânduri, după cum puteți vedea în fila IX_Clients_PK. Pentru a găsi numele oaspetelui cu un ClientID de 28, trebuie să citiți trei blocuri (noduri) de date - unul pe nivel - din structura cheii primare și, în final, să sari la rândul Clienți cu adresa 42.

Structura acestui index SQL se numește arbore echilibrat. Arborele este echilibrat atunci când calea de la nodul rădăcină la fiecare nod de la nivelul frunzei are aceeași lungime, așa-numita adâncime a arborelui B. În cazul nostru, adâncimea este de trei.

De acum înainte, vom considera că fiecare index are o structură B-tree, chiar dacă foile noastre de calcul conțin doar intrări la nivel de frunză. Cele mai importante lucruri de știut despre arborele B sunt:

• Structura indexului B-tree este cel mai frecvent utilizat indice de către toate RDBMS-urile majore de pe piață.
• Toate nivelurile unui arbore echilibrat sunt ordonate după valorile coloanei cheie.
• Datele sunt citite de pe disc în blocuri.
• Un nod B-tree conține unul sau mai multe blocuri.
• Cel mai important factor care afectează performanța interogării este numărul de blocuri citite de pe disc.
• Numărul de elemente din fiecare nou nivel de arbore B, începând cu rădăcină și terminând la nivelul frunzei, crește exponențial.

Exercițiul 5: Ancheta penală, Partea a II-a

Acum, inspectorul de poliție caută o listă cu numele oaspeților corespunzători, datele sosirii și numele hotelurilor din toate hotelurile din orașul A.

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

Abordarea 1

Dacă folosim indexul IX_DateFrom_HotelID_ClientID , atunci pentru fiecare rând din intervalul de date, ar trebui să accesăm tabelul Hoteluri și să verificăm dacă hotelul este din orașul A. Dacă este, ar trebui să accesăm și tabelul Clienți pentru a citiți numele clientului.

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Abordarea 2

Utilizarea IX_HotelID_DateFrom_ClientID ne oferă un plan de execuție mai eficient.

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Din tabelul Hotels , găsim toate hotelurile din orașul A. Cunoscând ID-ul acestor hoteluri, putem citi articolele ulterioare din indexul IX_HotelID_DateFrom_ClientID . În acest fel, după ce găsim primul rând din nivelul frunzei arborelui B pentru fiecare hotel și dată, nu citim rezervările de la hotelurile din afara orașului A.

Aici, putem vedea că atunci când avem un index al bazei de date care este adecvat pentru obiectivele noastre, o unire suplimentară poate face o interogare mai rapidă.

Structura arborelui B și modul în care este actualizată ori de câte ori un rând este inserat, actualizat sau șters vor fi abordate mai detaliat atunci când explic motivația partiționării și impactul acesteia. Ideea este că putem considera această operație rapidă ori de câte ori folosim un index.

Interogarea index în SQL: detaliile fac diferența

Când vine vorba de indici și baze de date, lucrul la nivel de limbaj SQL ascunde într-o oarecare măsură detaliile de implementare. Aceste exerciții sunt menite să vă ajute să înțelegeți cum funcționează planurile de execuție atunci când utilizați diferiți indici SQL. După ce ați citit articolul, sper că veți putea ghici cel mai bun plan de execuție având în vedere indecșii disponibili și indecșii de proiectare care ar face o interogare cât mai rapidă și eficientă posibil.

În următoarea parte a acestei serii, vom folosi și extinde abilitățile nou dobândite pentru a investiga și înțelege cele mai comune bune practici și anti-modele în utilizarea indicilor în SQL. Am o listă de bune și bune practici pe care vreau să le abordez în partea următoare, dar pentru a face următorul articol mai relevant pentru nevoile și experiența dvs., vă rugăm să nu ezitați să postați propriile întrebări la care ați dori să vi se răspundă .

În partea finală a SQL Indexes Explained , vom afla, de asemenea, despre partiționarea tabelelor și a indexurilor, motivele corecte și greșite pentru utilizarea acesteia și impactul acestuia asupra performanței interogărilor și întreținerea bazei de date.