Creació d'índex. Optimització de consultes

De wikijoan
Salta a la navegació Salta a la cerca

Introducció

Fins ara no hem treballat amb els índex. Ara ens preocuparem de com podem accelerar la rapidesa de les nostres cerques, definit els índex adequats sobre les taules.

B-TREE, arbre binari de cerca

Tenim els següents municipis:

DAN, MIT, LUR, BAT, CRE, ZAT, PRI, SAT, FOR, CAL, NOL, EBR, TRO

La solució més ràpida i fàcil per crear un índex que ens ajudi a fer una cerca d'aquests municipis és crear un vector ordenat:

BAT, CAL, CRE, DAN, EBR, FCR, LUR, MIT, NOL, PRI, SAT, TRO, ZAT

Aquest vector contesta molt bé a les preguntes:

  • Quin és el primer municipi (per ordre alfabètic)
  • Fer una llista ordenada de municipis per ordre alfabètic.

Però si vull mirar quins municipis comencen per N, he de recórrer tota la llista fins la posició N. La teoria diu que aquesta cerca és d'ordre N (on N és el número de valors). O també es diu que cercar en aquesta llista té un cost lineal (com més valors hi ha, més costa fer la cerca).

Els arbres B-TREE (ABC, arbres binaris de cerca o ABB, árboles binarios de búsqueda) milloren molt el temps de cerca (log(N)), sobretot quan l'arbre està ben balancejat. Anem a construir l'arbre (per construir l'arbre tenim un cost inicial de temps).

                     LUR
                /            \
          DAN                     PRI
        /     \                 /       \
    CAL        EBR         MIT             TRO
   /    \         \            \          /    \
BAT      CRE      FCR          NOL      SAT     ZAT

És un arbre binari. Cada clau (que representa un municipi) es divideix en dues. I les sub-branques són alhora branques que segueixen la mateixa regla. Hem agafat el primer valor (LUR) perquè és el que està al mig, i a partir d'ell podem fer un arbre balancejat.

Podem respondre a les següents preguntes:

  • Quin camí hem de seguir per cercar el mínim? Resposta: LUR -> DAN -> CAL -> BAT
  • Quin camí hem de seguir per cercar el màxim? Resposta: LUR -> PRI -> TRO -> ZAT
  • Quin camí hem de seguir per cercar els que comencen per N? Resposta: LUR -> PRI -> MIT -> NOL

Aquest algorisme de cerca és molt més eficient (log(N)), i és el que s'acostuma a utilitzar en les bases de dades.

Si t'interessa pots mirar per exemple el següent video:

Els índex a MySQL

Treballarem sobre la taula municipis.municipi.

Per veure els índex que tenim definits sobre aquesta taula:

mysql> SHOW INDEX FROM municipis;
+-----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table     | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+-----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| municipis |          0 | PRIMARY  |            1 | id_mun      | A         |        8256 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| municipis |          1 | id_prov  |            1 | id_prov     | A         |          52 |     NULL |   NULL | YES  | BTREE      |         |               | YES     | NULL       |
+-----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+

Veiem que tenin dos índex, que són la clau primària id_mun i la clau forània id_prov, que es van crear automàticament. Això és normal, i és que sobre les claus primàries i forànies sempre es creen index. I és que si fem una consulta combinada entre les taules municipis i provincies (inner join, usint (id_prov)), el fet de què id_prov de les dues taules sigui índex fa que la consulta vagi més ràpida.

Imaginem que moltes vegades fem cerques sobre els noms dels municipis, tan senzill com ara:

select municipi from municipis where municipi like 'A%';
select municipi from municipis order by municipi desc;

Si tinguéssim un índex sobre el camp municipi acceleraríem aquesta consulta.

mysql> select municipi from municipis order by municipi desc;
8131 rows in set (0,01 sec)

Veiem que aquesta consulta triga de l'ordre de 10ms, però això no és molt precís. Per saber què triga fer aquesta consulta tenim la comanda EXPLAIN:

mysql> EXPLAIN ANALYZE select municipi from municipis order by municipi desc;

| -> Sort: municipis.municipi DESC  (cost=843.75 rows=8380) (actual time=9.648..10.132 rows=8131 loops=1)
    -> Table scan on municipis  (cost=843.75 rows=8380) (actual time=0.059..2.268 rows=8131 loops=1)

La informació que ens dóna és:

  • Actual time to get first row (in milliseconds): 0.059 i 9.648 ms
  • Actual time to get all rows (in milliseconds): 9.648 i 10.132 ms
  • Actual number of rows read: 8131 + 8131
  • Actual number of loops: 1 + 1

Veiem que aquesta consulta ha trigat uns 12 ms (2.268 + 10.132), i que per obtenir el resultat s'ha hagut de processar dues vegades: primer fer una select normal, i després ordenar-la.

Per crear un índex és molt fàcil:

CREATE INDEX municipi_idx ON municipis (municipi);

mysql> SHOW INDEX FROM municipis;
...
| municipis |          1 | municipi_idx |            1 | municipi    | A         |        8114 |     NULL |   NULL | YES  | BTREE      |         |               | YES     | NULL       |
2 rows in set (0,01 sec)

Veiem que s'ha creat un índex nou de tipus BTREE (arbre binari).

mysql> select municipi from municipis order by municipi desc;
8131 rows in set (0,00 sec)

Aquests 0,00 sec ja indica que ha anat més ràpid, però fem el EXPLAIN per veure-ho bé:

mysql> EXPLAIN ANALYZE select municipi from municipis order by municipi desc;
-> Index scan on municipis using municipi_idx (reverse)  (cost=843.75 rows=8380) (actual time=0.077..4.682 rows=8131 loops=1)

S'ha trobat la solució amb un sol treball, i el temps és de 4.6 ms. Per tant, són unes 3 vegades més ràpid.

Podem tornar a eliminar l'índex:

mysql> DROP INDEX municipi_idx ON municipis;

EXPLAIN ANALYZE select municipi from municipis order by municipi desc;
| -> Sort: municipis.municipi DESC  (cost=843.75 rows=8380) (actual time=8.231..8.570 rows=8131 loops=1)
    -> Table scan on municipis  (cost=843.75 rows=8380) (actual time=0.101..1.969 rows=8131 loops=1)

Torna a trigar de l'ordre de 12 ms

Veure els index definits sobre una taula

Ja hem vist la comanda:

mysql> SHOW INDEX FROM municipis;

Altres maneres de veure-ho:

SELECT DISTINCT
    TABLE_NAME,
    INDEX_NAME
FROM INFORMATION_SCHEMA.STATISTICS
WHERE TABLE_SCHEMA = 'municipis';

+------------+--------------+
| TABLE_NAME | INDEX_NAME   |
+------------+--------------+
| comunitats | PRIMARY      |
| municipis  | id_prov      |
| municipis  | PRIMARY      |
| provincies | id_com       |
| provincies | PRIMARY      |
| municipis  | municipi_idx |
+------------+--------------+

Fixem-nos que hem accedit a la base de dades INFORMATION_SCHEMA i a la seva taula STATISTICS. Dins de la base de dades information_schema és on es guarda tot el diccionari de dades.


creat per Joan Quintana Compte, febrer 2022