Indeksu spožums un posts

Kas ir indekss?

Indeksi popularitātes ziņā droši vien ir nākošie objekti datubāzēm pēc tabulām. Tos bieži izmanto vietā un iespējams gandrīz tikpat bieži patiesībā lieto nevajadzīgi. Bet tātad vispirms būtu jāsaprot, kas tad tie ir un kāda aptuveni ir to uzbūve.

Parasti runājot par indeksiem vispirms tos saprot kā kokveidīgu struktūru, kuras pirmais un galvenais uzdevums ir ātri atrast datus tabulā, kuras dati, ja vien tā nav ļoti speciāla veida tabula, ir nesakārtoti. Nākošajā attēlā ir parādīta konceptuāla indeksa struktūra. Protams, ka reālajās implementācijās katrā DBVS tas ir mazliet atšķirīgi, bet ideja paliek viena un tā pati – koks, pa kuru ātri nonāk līdz nepieciešamajai vērtībai un tad taisnā ceļā izmantojot norādes dodas uz tabulu, no kuras var nolasīt konkrēto ierakstu. Nevajadzētu, protams, arī uztvert datu bloku skaitīšanu kā precīzu algoritmu, kas pie šīm vērtībām tā arī notiek, bet drīzāk kā konceptuālu ideju.

Indekss un tabula

Tātad, ja mēs meklējam vērtību “Kuldīga” (nosacījums WHERE pilsetas_nosaukums = ‘Kuldīga’) tabulā, tad mums ir divas iespējas:

• skanējam cauri visu tabulu (full scan), kurā dati ir nesakārtoti, un atrodam attiecīgo ierakstu. Šai piemērā tas nosacīti prasītu 6 tabulas bloku lasījumus.
• atrodam precīzu vērtību indeksā, kurā vērtības ir sakārtotas. Tur meklēšanas ceļš (attēlā augstāk iezīmēts ar raustītu līniju) ir šāds – iekavās attēlots nolasīto bloku skaits kopumā:
  • “Kuldīga” < “O”, kas ir indeksa saknes  blokā (root block), tātad jāiet pa kreisi. (1)
  • “Kuldīga” > “K”, kas ir zarā pa kreisi (branch block), tātad jaiet pa labi. (2)
  • Nākošā pa labi ir lapa (leaf block), kura satur vērtību “Kuldīga” un precīzu norādi uz tabulas ierakstu. (3)
  • Nolasam tabulas bloku ar vērtību “Kuldīga”. Esam kopumā nolasījuši 4 datu blokus, kas ir mazāk nekā lasot visus tabulas datus. (4)

Apskatīsim otru piemēru – gribam atrast visas pilsētas, kuru nosaukumi sākas ar R (nosacījums WHERE pilsetas_nosaukums LIKE ‘R%’). Vizuāli meklēšanas ceļš ir šāds.

Vairāku vērtību nolasīšana no indeksa

• Pilnas tabulas skans ir tāds pats kā iepriekš, tajā nekas nemainās.
• Savukārt meklēšana pēc indeksa (attēlā ar raustītām līnijām) būs šāda:
  • “R” > “O”, tātad jāiet pa labi. (1)
  • “R” < “T”, tātad jāiet pa kreisi. (2)
  • Indeksa lapā atrodam vērtību “Rēzekne”, kas atbilst nosacījumam. (3)
  • Pēc indeksa norādes precīzi atrodam ierakstu tabulā un nolasam šo bloku. (4)
  • Indeksa lapā atrodam vērtību “Rīga”, kas atbilst nosacījumam. (4)
  • Pēc indeksa norādes precīzi atrodam ierakstu tabulā un nolasam šo bloku. (5) Tātad kopsummā esam apmeklējuši 5 datu blokus, kas ir mazāk nekā 6 ko prasītu pilna tabulas skanēšana.

Pilnam komplektam arī trešais piemērs – gribam atrast pilsētas, kuru nosaukumi ir lielāki nekā “R” bet mazāki nekā “U” (nosacījums WHERE pilsetas_nosaukums BETWEEN ‘R’ AND ‘U’). Vizuāli tas izskatās šādi:

Vairāku vērtību nolasīšana no indeksa (arī vairākām indeksa lapām)

• Pilnas tabulas skans ir tāds pats kā iepriekš, tajā nekas nemainās.
• Savukārt meklēšana pēc indeksa (attēlā ar raustītām līnijām, pievērsiet uzmanību raustītajai līnijai starp lapām) būs šāda:
  • “R” > “O”, tātad jāiet pa labi. (1)
  • “R” < “T”, tātad jāiet pa kreisi. (2)
  • Indeksa lapā atrodam vērtību “Rēzekne”, kas atbilst nosacījumam. (3)
  • Pēc indeksa norādes precīzi atrodam ierakstu tabulā un nolasam šo bloku. (4)
  • Indeksa lapā atrodam vērtību “Rīga”, kas atbilst nosacījumam. (4)
  • Pēc indeksa norādes precīzi atrodam ierakstu tabulā un nolasam šo bloku. (5)
  • Šai indeksa lapā vairāk vērtību nav tāpēc jāiet uz nākošo lapu pa labi. Indeksa lapā atrodam vērtību “Talsi”, kas atbilst nosacījumam. (6)
  • Pēc indeksa norādes precīzi atrodam ierakstu tabulā un nolasam šo bloku. (7) Vairāk vērtību atbilstoši nosacījumiem nav. Tātad kopsummā esam apmeklējuši 7 datu blokus, kas ir vairāk nekā 6, ko prasītu pilna tabulas skanēšana, tātad šai gadījumā tabulas pilna skanēšana būtu lētāka nekā lasīšana indekss-tabula.

Indeksa izveides sintakse

CREATE [UNIQUE] INDEX <indeksa vārds>
ON <tabulas vārds> (<kolona1>[, <kolona2>[, ..., <kolonaN>]]); 

• Indeksam ir jāpiešķir <indeksa vārds>. Atkarībā no DBVS tam jābūt unikālam tabulas ietvaros (MySQLā piemēram), vai shēmas ietvaros (Oraclē).
• ON klauzā tiek norādīts kādai tabulai indekss tiek veidots.
• Iekavās var rakstīt vienu vai vairākas kolonas uz kurām indeksu veidot. Vairāku kolonu gadījumā tas būs kompozītais (composite) indekss.

Savukārt, lai tiktu vaļā no indeksa ir jaizmanto variācija par

DROP INDEX <indeksa vārds>

MySQLā tai vēl ON klauzā jānorāda tabulas vārds, kas gluži loģiski jo vienā datubāzē var būt vairāki indeksi ar vienādu vārdu, tāpēc jāprecizē tabula.

Indeksu piemēri un operācijas – indeksu spožums

Piemēriem izmantosim zemāk redzamo tabulu un datus, kā arī indeksu uz pilsētas nosaukuma. Tā kā Latvijā pilsētu nosaukumi ir unikāli, tad varam veidot unikālo indeksu. Iedzīvotāju skaits ņemts no Lielā pasaules atlanta.

CREATE TABLE pilsetas (
  id INTEGER PRIMARY KEY,
  pilsetas_nosaukums varchar(40),
  iedz_skaits INTEGER);
INSERT INTO pilsetas VALUES (1, 'Rīga', 719600);
INSERT INTO pilsetas VALUES (2, 'Kuldīga', 13000);
-- šī komanda ir specifiska Oracle un tās mērķis ir nodrošināt,
-- ka vienā datu blokā ir ne vairāk kā 2 ieraksti
-- (balstoties uz 2 jau ieliktajiem)
ALTER TABLE pilsetas MINIMIZE records_per_block;
INSERT INTO pilsetas VALUES (3, 'Talsi', 11400);
INSERT INTO pilsetas VALUES (4, 'Ventspils', 43400);
INSERT INTO pilsetas VALUES (5, 'Rēzekne', 35900);
INSERT INTO pilsetas VALUES (6, 'Daugavpils', 106100);
INSERT INTO pilsetas VALUES (7, 'Ogre', 26800);
INSERT INTO pilsetas VALUES (8, 'Valmiera', 27500);
INSERT INTO pilsetas VALUES (9, 'Cēsis', 18200);
INSERT INTO pilsetas VALUES (10, 'Krāslava', 10500);
INSERT INTO pilsetas VALUES (11, 'Bauska', 10200);
INSERT INTO pilsetas VALUES (12, 'Liepāja', 85300);
COMMIT;

Piemēru pielietošana Oracle DBVS

Pagaidām, kamēr mums indeksa nav, paskatamies, cik datu bloki tiek nolasīti. Šim mērķim izmantosim SQL*Plus komandu autotrace. Es atstāšu tikai tos rezultātus, kas ir svarīgi šim piemēram, patiesībā izpildes statistika tiek ģenerēta vairāk.

SQL> set autot on
SQL> SELECT * FROM pilsetas
  2  WHERE pilsetas_nosaukums = 'Kuldīga';
        ID PILSETAS_NOSAUKUMS                       IEDZ_SKAITS
---------- ---------------------------------------- -----------
         2 Kuldīga                                        13000
-------------------------------------------------------------------
| Id  | Operation         | Name     | Rows  | Bytes | Cost (%CPU)|
-------------------------------------------------------------------
|   0 | SELECT STATEMENT  |          |     1 |    48 |     3   (0)|
|*  1 |  TABLE ACCESS FULL| PILSETAS |     1 |    48 |     3   (0)|
-------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter("PILSETAS_NOSAUKUMS"='Kuldīga')
Statistics
----------------------------------------------------------
          16 consistent gets
          1  rows processed

Tagad izveidojam indeksu un pievēršama uzmanību izpildes plāna izmaiņām un datu bloku nolasījumiem (consistent gets).

SQL> CREATE UNIQUE INDEX pils_nos_idx
  2  ON pilsetas (pilsetas_nosaukums);
SQL> SELECT * FROM pilsetas
  2  WHERE pilsetas_nosaukums = 'Kuldīga';
        ID PILSETAS_NOSAUKUMS                       IEDZ_SKAITS
---------- ---------------------------------------- -----------
         2 Kuldīga                                        13000
--------------------------------------------------------------------
|Id|Operation                   |Name        |Rows|Bytes|Cost(%CPU)|
--------------------------------------------------------------------
| 0|SELECT STATEMENT            |            |  1 |   48|    1  (0)|
| 1| TABLE ACCESS BY INDEX ROWID|PILSETAS    |  1 |   48|    1  (0)|
|*2|  INDEX UNIQUE SCAN         |PILS_NOS_IDX|  1 |     |    0  (0)|
--------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("PILSETAS_NOSAUKUMS"='Kuldīga')
Statistics
----------------------------------------------------------
          2  consistent gets
          1  rows processed

Tagad skatamies, kas notiek, ja atlasam vērtības no otrā piemēra.

SQL> SELECT * FROM pilsetas
  2  WHERE pilsetas_nosaukums like 'R%';
        ID PILSETAS_NOSAUKUMS                       IEDZ_SKAITS
---------- ---------------------------------------- -----------
         5 Rēzekne                                        35900
         1 Rīga                                          719600
---------------------------------------------------------------------
|Id|Operation                   |Name        |Rows |Bytes|Cost(%CPU)|
---------------------------------------------------------------------
| 0|SELECT STATEMENT            |            |    2|   96|    3  (0)|
| 1| TABLE ACCESS BY INDEX ROWID|PILSETAS    |    2|   96|    3  (0)|
|*2|  INDEX RANGE SCAN          |PILS_NOS_IDX|    2|     |    1  (0)|
---------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("PILSETAS_NOSAUKUMS" LIKE 'R%')
       filter("PILSETAS_NOSAUKUMS" LIKE 'R%')
Statistics
----------------------------------------------------------
          4  consistent gets
          2  rows processed

Pēdējo gadījumu nesākšu drukāt šeit, jo tas 99% lasītāju būs apnicīgi, vienkārši vienā tabuliņā apkopošu rezultātus.

Statistika	full scan jebkuram filtram	unique scan =’Kuldīga’	range scan like ‘R%’	range scan BETWEEN ‘R’ AND ‘U’
Atlasīto ierakstu skaits	1	1	2	3
consistent gets	16	2	4	5

Tātad kāda morale? Bez indeksa izmantošanas mēs dabūjam 16 datu bloku lasījumus jebkurā gadījumā, pat atlasot vienu ierakstu. Savukārt, ja mums ir unikālais indekss, tad ir divas pamatoperācijas:

• INDEX UNIQUE SCAN – tiek izmantota tad, ja DBVS zin, ka tiks atlasīts ne vairāk kā 1 ieraksts. Var protams, atlasīt arī o.  Vispārīgā gadījumā ļoti grūti izdomāt kādu efektīvāku operāciju.
• INDEX RANGE SCAN – tiek izmantota tad, ja izmantojot indeksu ir jānolasa vairākas vērtības pēc kārtas. Šai gadījumā, ja skanēšana ir relatīvi īsa, tad tas var būt efektīvāk nekā pilns tabulas skans, savukārt, ja indeksa skanēšana ir gara, tad tā var būt arī neefektīvāka nekā pilna tabulas skanēšana.

Piemēru pielietošana MySQL DBVS

Paskatamies kā šie paši plāni izskatīsies MySQLā. Pirmajā gadījumā, kad indeksa vēl nav:

mysql> explain SELECT * FROM pilsetas
    -> WHERE pilsetas_nosaukums = 'Kuldiga';
+--+-----------+---------+----+-------------+----+----+----+
|id|select_type|table    |type|possible_keys|key |ref |rows|
+--+-----------+---------+----+-------------+----+----+----+
| 1|SIMPLE     |pilsetas |ALL |NULL         |NULL|NULL|12  |
+--+-----------+---------+----+-------------+----+----+----+
+-----------+
|Extra      |
+-----------+
|Using where|
+-----------+

Kā redzams tajā bija type = ALL, kas viena ieraksta atlasei par neko labu neliecina. Extra kolona arī liecina par to, ka tiek lietots papildus filtrs.

Savukārt, unikālais indeksa skans izskatās šādi. Pievērsiet uzmanību type kolonai un to, ka mums parādās key (indekss), kas tiek izmantots.

mysql> explain SELECT * FROM pilsetas
    -> WHERE pilsetas_nosaukums = 'Kuldīga';
+--+-----------+--------+-----+-------------+------------+-----+----+
|id|select_type|table   |type |possible_keys|key         |ref  |rows|
+--+-----------+--------+-----+-------------+------------+-----+----+
| 1|SIMPLE     |pilsetas|const|pils_nos_idx |pils_nos_idx|const|   1|
+--+-----------+--------+-----+-------------+------------+-----+----+

Savukārt vairāku vērtību nolasīšana no indeksa izskatās šādi. Kā redzams šeit type=range un key palicis tas pats, kā arī parādījusies garum gara Extra kolona, kur parādās vēl divas papildus optimizācijas. Par katru no tām var lasīt MySQL dokumentācijā.

mysql> explain SELECT * FROM pilsetas
    -> WHERE pilsetas_nosaukums like 'R%';
+--+-----------+--------+-----+-------------+------------+----+----+
|id|select_type|table   |type |possible_keys|key         |ref |rows|
+--+-----------+--------+-----+-------------+------------+----+----+
| 1|SIMPLE     |pilsetas|range|pils_nos_idx |pils_nos_idx|NULL|   2|
+--+-----------+--------+-----+-------------+------------+----+----+
+-------------------------------+
|Extra                          |
+-------------------------------+
|Using index condition;Using MRR|
+-------------------------------+

MySQLā diemžēl man neizdodas dabūt nolasītos blokus, jo vienīgais man zināmais rīks MySQL profiler, par ko rakstīju iepriekšējā rakstā, kas to varētu darīt, Windows OSā to nerāda. Taču lielākiem vaicājumiem, kur patiešām ir būtiska atšķirība, Jūs noteikti varat izmantot šo rīku mērījumiem.

Ļoti bieži indeksi tiek uzskatīti par panaceju ar ko atrisināt visas DBVS problēmas – pieliksim kādu klāt un viss būs kārtībā.

Indeksu posts

Diemžēl, kā katrai lietai, arī indeksiem ir savas ēnas puses. Pati pirmā un galvenā ēna ir indekss varbūt var uzlabot SELECT vaicājumu ātrdarbību, bet tas noteikti palēninās INSERT, UPDATE, DELETE un MERGE ātrdarbību. Parastā tradicionālā kaudzes (heap) tabulā ir vienalga, kur ieraksts nonāk. Indeksā katrai vērtībai ir sava precīza vieta, tāpēc pirmkārt tā ir jāieliek divās vietās, otrkārt var gadīties, ka to vajadzīgajā vietā nevar ielikt, jo tur trūkst vietas un ir jāveic papildus darbības (tātad papildus diska noslodze), lai to varētu izdarīt. Jo vairāk indeksu tabulā būs, jo dārgāk izmaksās to uzturēšana. Tādējādi var pienākt brīdis, kad potenciālais ieguvums SELECT vaicājumos ir mazāks nekā zaudējusm pārējos datu manipulēšanas vaicājumos.

Tātad liekam jaunu ierakstu klāt (INSERT), mainam viena ieraksta visas kolonas ieskaitot primāro atslēgu (UPDATE) un dzēšam vienu ierakstu (DELETE) un skatamies, kā mainās raksturīgās statistikas. Lai būtu skaidrāk redzama atšķirība, apkopošu rezultātus tabuliņā.

Statistika	bez neviena indeksa	ar 1 indeksu (primary key)	ar 2 indeksiem (PK, nosaukums)	ar 3 indeksiem (PK, nos., iedz. sk.)
INSERT
db block gets	3	5	7	9
consistent gets	1	1	1	1
redo size	252	508	724	936
UPDATE
db block gets	1	5	9	15
consistent gets	16	1	1	1
redo size	332	748	1172	1644
DELETE
db block gets	2	4	6	8
consistent gets	16	1	1	1
redo size	296	500	708	908

Tātad daži secinājumi skatoties uz šiem skaitļiem:

• Priekš INSERT katra indeksa pielikšana prasa aizvien vairāk lasīt/rakstīt datu blokus (db block gets + consistent gets), 3 indeksu gadījumā tas jau ir vairāk kā 2reiz vairāk nekā bez indeksiem.
• Priekš UPDATE un DELETE neviens indekss (jo es dzēsu pēc id lauka) nozīmē tabulas pilnu skanēšanu tāpēc bez neviena indeksa tas prasa vairāk datu bloku lasīšanas.
• UPDATE un DELETE pieliekot primāro indeksu ir būtisks lasīšanas samazinājums (consistent gets) , tai pašā laikā rakstīšana (db block gets) aug. Kā redzams UPDATE tas aug sevišķi strauji, jo indeksā vērtības ir nepieciešams dzēst un pēc tam likt atkal klāt.
• Ar katru jaunu indeksu aug redo size – rakstījumi, kas nodrošina atrites (rollback) operāciju. Tas sevišķi uzskatāmi ir UPDATE, jo šeit arī indeksu blokiem ir jānodrošina šīs izmaiņas.
• No šīm papildus IO operācijām nav iespējams nekādā citā veidā izbēgt, kā vien, vai nu neveidojot indeksus, vai nerakstot datus tabulā. Tātad galvenais uzdevums ir indeksu skaitu minimizēt un veidot tikai tos, kas patiešām ir nepieciešami. 

Kopsavilkums

• Indeksi var ļoti būtiski iespaidot ātrdarbību. Diemžēl abos virzienos – gan sliktā, gan labā nozīmē.
• Indeksi ir kā zāles, ko nevajag pārdozēt. Pārdozēšana var radīt reālas problēmas.
• Šei ir apskatītas tikai ļoti nedaudzas un pašas pamatlietas no indeksu iezīmēm un operācijām. Katrā DBVS vēl var būt burtiski padsmitiem citu.
• Atkārtojot savā vidē šeit minētos piemērus, Jums var nākties redzēt citus skaitļus, bet tendencēm gan būtu jābūt tādām kā šeit minēts.

Tālākā lasāmviela

• Pārskats par indeksiem Oracle dokumentācijā;
• Richard Foote blogs (Oracle) – emuārs, kurā indeksi tiek secēti un iztirzāti visos sīkumos;
• Julian Dyke prezentācijas (Oracle) – šai gadījumā interesantas varētu būt Index Internals un Bitmap Index Internals;
• Kā MySQL lieto indeksus – no MySQL dokumentācijas;
• Ieskats SQL Server indeksos.