Preskoči na glavni sadržaj

MySQL indeksi — 15 pitanja zaredom, izdrži!

Jian Tianluo de Xiao Nanhai (Dečak koji kupi puževe)Posao i intervju2666 reči9 minuta

Predgovor

Zdravo svima, ja sam Tianluo.

Sezona intervjua se brzo bliži, pa sam pripremio 15 pitanja o indeksima; verujem da će vam nakon čitanja sigurno pomoći.

1. Šta je indeks?

  • Indeks je struktura podataka koja može da poveća efikasnost upita nad bazom. Može se uporediti sa sadržajem rečnika — pomaže vam da brzo pronađete odgovarajući zapis.
  • Indeks se obično čuva u fajlu na disku i zauzima fizički prostor.
  • Kao što se kaže — voda može da nosi lađu, ali i da je potopi. Umeren broj indeksa povećava efikasnost upita, dok previše indeksa utiče na umetanje i ažuriranje u tabelama baze.

2. Koje tipove indeksa ima MySQL?

Aspekt strukture podataka

  • Indeks B+-stabla: svi podaci se čuvaju u listovima, složenost je O(logn), pogodan za opsežne upite.
  • Heš indeks: pogodan za upite po jednakosti, visoke efikasnosti pretrage — stiže do rezultata u jednom koraku.
  • Indeks celog teksta (full-text): i MyISAM i InnoDB podržavaju indeks celog teksta; obično se kreira nad tekstualnim tipovima char, text, varchar.
  • R-Tree indeks: služi za kreiranje SPATIAL indeksa nad GIS tipovima podataka.

Aspekt fizičkog čuvanja

  • Klasterizovani indeks: klasterizovani indeks jeste indeks kreiran nad primarnim ključem; u listovima se čuvaju podaci iz tabele (skladišni motor Innodb).
  • Neklasterizovani indeks: neklasterizovani indeks jeste indeks kreiran nad ne-primarnim ključem; u listovima se čuvaju primarni ključ i kolona indeksa (skladišni motor Innodb).

Logički aspekt

  • Indeks primarnog ključa: posebna vrsta jedinstvenog indeksa, ne dozvoljava null vrednosti.
  • Običan indeks: osnovni tip indeksa u MySQL-u, dozvoljava null vrednosti i ponavljajuće vrednosti.
  • Združeni (kompozitni) indeks: indeks kreiran nad više polja; pri upotrebi se poštuje princip najlevljeg prefiksa.
  • Jedinstveni indeks: vrednosti u indeksiranoj koloni moraju biti jedinstvene, ali se dozvoljava null.
  • Prostorni indeks: posle MySQL5.7 podržan je prostorni indeks; u tom pogledu se poštuju pravila geometrijskog modela podataka OpenGIS.

3. Kada indeks prestaje da važi (ne koristi se)?

  • Uslov upita sadrži or, što može dovesti do toga da indeks prestane da važi.
  • Ako je tip polja niska, u where obavezno se stavi pod navodnike, inače indeks prestaje da važi.
  • like džoker-znakovi mogu dovesti do toga da indeks prestane da važi.
  • Kod združenog indeksa, ako kolona uslova u upitu nije prva kolona tog združenog indeksa, indeks prestaje da važi.
  • Upotreba ugrađene mysql funkcije nad indeksiranom kolonom — indeks prestaje da važi.
  • Operacija nad indeksiranom kolonom (npr. +,-,*,/) — indeks prestaje da važi.
  • Upotreba nad indeksiranim poljem (!=, <>, not in) može dovesti do toga da indeks prestane da važi.
  • Upotreba is null, is not null nad indeksiranim poljem može dovesti do toga da indeks prestane da važi.
  • Kod upita sa levim ili desnim spajanjem, ako povezane kolone imaju različit format kodiranja, to može dovesti do toga da indeks prestane da važi.
  • Ako mysql proceni da je skeniranje cele tabele brže od korišćenja indeksa, neće koristiti indeks.

4. U kojim slučajevima ne treba praviti indeks?

  • Tabele sa malo podataka nisu pogodne za dodavanje indeksa.
  • Ni one koje se često ažuriraju nisu pogodne za dodavanje indeksa.
  • Polja niske selektivnosti nisu pogodna za indeks (npr. pol).
  • Polja koja se ne koriste iza where, group by, order by i sl. ne treba indeksirati.
  • Kada već postoje suvišni indeksi (npr. već postoji združeni indeks a,b, pa ne treba posebno praviti i indeks nad a).

5. Zašto B+-stablo, a ne binarno stablo?

Ovo pitanje se može posmatrati iz nekoliko aspekata: da li je upit dovoljno brz, da li je efikasnost stabilna, koliko podataka se čuva, i koliko puta se pristupa disku — zašto ne obično binarno stablo, zašto ne izbalansirano binarno stablo, zašto ne B-stablo, baš B+-stablo?

Zašto ne obično binarno stablo?

Ako se binarno stablo degeneriše u povezanu listu, to odgovara skeniranju cele tabele. Izbalansirano binarno stablo je, u poređenju sa binarnim stablom pretrage, stabilnije u efikasnosti pretrage i ukupno brže.

Zašto ne izbalansirano binarno stablo?

Znamo da je pretraga podataka u memoriji znatno brža nego na disku. Ako se stablo kao struktura podataka koristi za indeks, onda pri svakoj pretrazi podataka sa diska treba pročitati jedan čvor — tzv. disk blok. Ali izbalansirano binarno stablo u svakom čvoru čuva samo jedan ključ i podatak, dok B-stablo može da sačuva više podataka čvorova i smanji visinu stabla, pa se broj pristupa disku smanji i pretraga postaje brža.

Zašto onda B+-stablo, a ne B-stablo?

  • B+-stablo u čvorovima koji nisu listovi ne čuva podatke, već samo ključeve, dok čvor B-stabla čuva i ključeve i podatke. Podrazumevana veličina stranice u innodb-u je 16 KB; ako se podaci ne čuvaju, čuva se više ključeva, red stabla (broj podređenih čvorova čvora) biva veći, a stablo niže i "deblje", pa se broj IO pristupa disku pri pretrazi ponovo smanjuje i pretraga podataka postaje brža.
  • Svi podaci indeksa B+-stabla čuvaju se u listovima, i to po redosledu, povezani povezanom listom. Tako B+-stablo čini opsežnu pretragu, pretragu sa sortiranjem, pretragu sa grupisanjem i pretragu sa uklanjanjem duplikata izuzetno jednostavnim.

6. Jedan proces pretrage kroz indeksno B+-stablo

Pretpostavimo sledeću strukturu tabele, uz inicijalizovanih nekoliko redova podataka.

CREATE TABLE `employee` (
  `id` int(11) NOT NULL,
  `name` varchar(255) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `date` datetime DEFAULT NULL,
  `sex` int(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_age` (`age`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

insert into employee values(100,'Xiao Lun',43,'2021-01-20','0');
insert into employee values(200,'Junjie',48,'2021-01-21','0');
insert into employee values(300,'Ziqi',36,'2020-01-21','1');
insert into employee values(400,'Lihong',32,'2020-01-21','0');
insert into employee values(500,'Yixun',37,'2020-01-21','1');
insert into employee values(600,'Xiao Jun',49,'2021-01-21','0');
insert into employee values(700,'Xiao Yan',28,'2021-01-21','1');

Koliko je operacija pretrage stabla potrebno da bi se izvršio ovaj SQL upit? Možete nacrtati odgovarajuću strukturu indeksnog stabla.

select * from Temployee where age=32;

Zapravo, možete prvo nacrtati strukturu indeksnog stabla običnog indeksa idx_age, koja grubo izgleda ovako:

Zatim nacrtajte indeks primarnog ključa id; prvo nacrtajmo strukturu klasterizovanog indeksa, koja izgleda ovako:

Približan tok izvršavanja ovog SQL upita je sledeći:

  • Pretražuje se indeksno stablo idx_age: disk blok 1 se učita u memoriju, pošto je 32<43 ide se levom granom, i na disku se traži adresa disk bloka 2.
  • Disk blok 2 se učita u memoriju, pošto je 32<36 ide se levom granom, i na disku se traži adresa disk bloka 4.
  • Disk blok 4 se učita u memoriju, u memoriji se nastavlja obilazak, pronalazi se zapis sa age=32 i uzima se id = 400.
  • Po dobijanju id=400 vraća se na indeksno stablo primarnog ključa id.
  • Pretražuje se indeksno stablo primarnog ključa id: disk blok 1 se učita u memoriju, pošto je 300<400<500 bira se srednja grana, i na disku se traži adresa disk bloka 3.
  • Iako je u disk bloku 3 pronađen id=400, to nije list, pa se nastavlja nadole. Na disku se traži adresa disk bloka 8.
  • Disk blok 8 se učita u memoriju, obilazi se u memoriji, pronalazi se zapis sa id=400, uzima se red R4 i time je gotovo.

7. Šta je povratak na tabelu (huibiao)? Kako ga smanjiti?

Kada podaci upita ne mogu da se pronađu u indeksnom stablu, potrebno je vratiti se u indeksno stablo primarnog ključa da bi se pribavili — taj proces se zove povratak na tabelu (huibiao).

Na primer, SQL upit iz odeljka 6:

select * from Temployee where age=32;

Zahteva sve kolone podataka, što običan indeks idx_age ne može da zadovolji; potrebno je uzeti vrednost primarnog ključa id, pa se vratiti u indeks primarnog ključa id i pribaviti podatke — to je povratak na tabelu.

8. Šta je pokrivajući indeks?

Ako u SQL upitu select * promenimo u select id, age, zapravo nije potreban povratak na tabelu. Jer se vrednosti id i age već nalaze u listovima indeksnog stabla idx_age — i tu nastupa pojam pokrivajućeg indeksa.

Pokrivajući indeks znači da se kolone koje select vraća mogu pribaviti već iz indeksa, bez povratka na tabelu; drugim rečima, kolone upita mora da pokriva napravljeni indeks.

9. Nešto o principu najlevljeg prefiksa indeksa

Princip najlevljeg prefiksa indeksa može se odnositi na najlevljih N polja združenog indeksa. Na primer, ako napravite kompozitni indeks (a,b,c), to zapravo odgovara kreiranju tri indeksa — (a), (a,b), (a,b,c) — što znatno povećava mogućnost ponovne upotrebe indeksa.

Naravno, najlevlji prefiks može biti i najlevljih M karaktera indeksa niske. Na primer, vaše stablo običnog indeksa izgleda ovako:

Ovaj SQL: select * from employee where name like 'X%' order by age desc; takođe pogađa indeks.

10. Da li ste čuli za indeks pushdown? Šta je indeks pushdown?

Imamo ovaj SQL:

select * from employee where name like 'X%' and age=28 and sex='0';

gde su name i age združeni indeks (idx_name_age).

Pre MySQL 5.6, u indeksnom stablu idx_name_age pronalaze se svi čije ime počinje slovom "X", uzima se njihov primarni ključ id, zatim se vraća na tabelu i pronalaze redovi, pa se tek porede uzrast, pol i ostale kolone. Vidi sliku:

Nekima je možda čudno — zar idx_name_age (name, age) nije združeni indeks? Zašto, pošto se izaberu oni koji sadrže "X", ne iskoristiti priliku i pogledati uzrast age pre povratka na tabelu, zar nije efikasnije? Zato je MySQL 5.6 uveo optimizaciju indeks pushdown-a (ICP): tokom obilaska indeksa može se prvo oceniti polje sadržano u indeksu i direktno odfiltrirati zapisi koji ne ispunjavaju uslov, čime se smanjuje broj povrataka na tabelu.

Dakle, posle verzije MySQL 5.6, pošto se izaberu oni koji sadrže "X", usput se filtrira age=28.

11. Kako dodati indeks na veliku tabelu

Ako tabela ima desetine miliona redova, kako joj dodati indeks?

Treba znati jedno: prilikom dodavanja indeksa tabeli ona se zaključava. Ukoliko se ne radi pažljivo, može doći do incidenta u produkciji. Mogu se razmotriti sledeći postupci:

  1. Prvo se kreira nova tabela B iste strukture podataka kao originalna A.
  2. Novoj tabeli B dodaju se potrebni novi indeksi.
  3. Podaci iz originalne tabele A izvezu se u novu tabelu B.
  4. Novoj tabeli B se uradi rename u ime originalne tabele A, a originalna A dobije drugo ime.

12. Kako saznati da li upit koristi indeks?

Sa explain se pregleda plan izvršavanja SQL-a — tako se vidi da li je pogođen indeks.

Kada se explain koristi uz SQL, MySQL prikazuje informacije optimizatora o planu izvršavanja iskaza.

Uglavnom treba obratiti pažnju na type, rows, filtered, extra, key.

1.2.1 type

type označava tip spajanja i važan je pokazatelj izvršavanja indeksa. Performanse od najbolje ka najgoroj: system > const > eq_ref > ref > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL.

  • system: ovaj tip zahteva da tabela ima samo jedan red; to je specijalan slučaj tipa const i retko se javlja.
  • const: podatak se pronalazi jednim pristupom indeksu; obično se koristi kad je uslov primarni ili jedinstveni ključ — ta vrsta skeniranja je izuzetno efikasna i vrlo brza.
  • eq_ref: često se koristi za skeniranje primarnim ili jedinstvenim ključem; obično označava upit spajanja preko primarnog ključa.
  • ref: često se koristi za skeniranje ne-primarnim i ne-jedinstvenim ključem.
  • ref_or_null: slično kao ref, s tim što MySQL dodatno pretražuje i redove koji sadrže NULL.
  • index_merge: koristi optimizaciju spajanja indeksa; upit koristi dva ili više indeksa.
  • unique_subquery: slično kao eq_ref, uslov koristi in podupit.
  • index_subquery: za razliku od unique_subquery, koristi se za ne-jedinstvene indekse i može vratiti ponavljajuće vrednosti.
  • range: često se koristi za opsežne upite, npr. between ... and ili in i sl.
  • index: skeniranje celog indeksa.
  • ALL: skeniranje cele tabele.

1.2.2 rows

Ova kolona predstavlja broj redova koje MySQL, po proceni, mora pročitati da bi našao tražene zapise. Za InnoDB tabele taj broj je procena i ne mora biti tačan.

1.2.3 filtered

Ova kolona je procenat — udeo redova u tabeli koji ispunjavaju uslov. Prosto rečeno, ovo polje označava udeo preostalih zapisa koji ispunjavaju uslov, nakon što se podaci koje vrati skladišni motor profiltriraju.

1.2.4 extra

Ovo polje sadrži dodatne informacije o tome kako MySQL raščlanjuje upit; obično se javljaju ove vrednosti:

  • Using filesort: znači sortiranje po fajlu; obično se javlja kada navedeno sortiranje ne odgovara sortiranju indeksa. Često se viđa u iskazima order by.
  • Using index: označava da li je korišćen pokrivajući indeks.
  • Using temporary: označava da li je korišćena privremena tabela — performanse su jako loše i to treba posebno optimizovati. Često se viđa u iskazima group by ili union.
  • Using where: označava da je za filtriranje korišćen uslov where.
  • Using index condition: indeks pushdown (ICP) dodat u MySQL 5.6; filtriranje podataka se obavlja u sloju skladišnog motora umesto u sloju servisa, čime se iskorišćavaju postojeći podaci indeksa da bi se smanjio obim podataka pri povratku na tabelu.

1.2.5 key

Ova kolona označava stvarno korišćeni indeks. Obično se posmatra zajedno sa kolonom possible_keys.

13. Koja je razlika između Hash indeksa i B+-stabla? Kako odlučujete pri dizajnu indeksa?

  • B+-stablo može da radi opsežne upite, Hash indeks ne može.
  • B+-stablo podržava princip najlevljeg prefiksa združenog indeksa, Hash indeks ne podržava.
  • B+-stablo podržava sortiranje order by, Hash indeks ne podržava.
  • Hash indeks je efikasniji od B+-stabla kod upita po jednakosti. (Ali ako indeksna kolona ima mnogo ponavljajućih vrednosti, Hash kolizija mu smanjuje efikasnost.)
  • Kod B+-stabla, kada se za mutnu pretragu koristi like, pozicija iza like (npr. % na početku) može imati ulogu optimizacije; Hash indeks uopšte ne može da radi mutnu pretragu.

14. Koje su prednosti i mane indeksa?

Prednosti:

  • Indeks može da ubrza pretragu podataka i skrati vreme upita.
  • Jedinstveni indeks može da garantuje jedinstvenost podataka u svakom redu tabele baze.

Mane:

  • Kreiranje i održavanje indeksa zahteva vreme.
  • Indeks zauzima fizički prostor; pored prostora koji zauzima tabela, svaki indeks zauzima i određeni dodatni fizički prostor.
  • Pri dodavanju, brisanju i izmeni podataka u tabeli, indeks se takođe dinamički održava.

15. Razlika između klasterizovanog i neklasterizovanog indeksa

Klasterizovani indeks nije zasebna vrsta indeksa, već način čuvanja podataka. On označava indeks čija se struktura čuva zajedno sa podacima. Neklasterizovani indeks jeste indeks čija se struktura čuva odvojeno od podataka.

Dalje ćemo razmotriti po različitim skladišnim motorima.

U skladišnom motoru InnoDB baze MySQL, najveća razlika između klasterizovanog i neklasterizovanog indeksa jeste da li list čuva ceo red zapisa. List klasterizovanog indeksa čuva ceo red, dok list neklasterizovanog indeksa čuva informaciju o primarnom ključu, pa neklasterizovani indeks obično zahteva i povratak na tabelu.

  • Tabela može imati samo jedan klasterizovani indeks (jer je klasterizovani indeks u pravilu indeks primarnog ključa), dok neklasterizovanih indeksa može biti više.
  • Uopšteno, u poređenju sa neklasterizovanim, klasterizovani indeks je efikasniji u upitu jer ne zahteva povratak na tabelu.

A u skladišnom motoru MyISAM, i indeks primarnog ključa i obični indeks su neklasterizovani, jer su podaci i indeksi razdvojeni, pa listovi jednom adresom ukazuju na stvarne podatke tabele.

Podržite lajkom, hvala vam~

Referentni link: https://mp.weixin.qq.com/s?__biz=Mzg3NzU5NTIwNg==&mid=2247503690&idx=1&sn=73655f41a98f21217468115888aeeceb&chksm=cf221063f855997590d48e605ac3cadbad14f4e91b71acf471a520a9ed9be2a9f2e2c5b64450#rd | Izvor: Jian Tianluo de Xiao Nanhai (Dečak koji kupi puževe), priredio: Chenmo Wang Er