Revisió de 22:39, 14 feb 2022

Contingut

1 Introducció
2 B-TREE, arbre binari de cerca
3 Els índex a MySQL
4 Veure els index definits sobre una taula

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:

https://www.youtube.com/watch?v=mTMrszfrNtI

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

@@ Línia 1: / Línia 1: @@
-<pre>
+__TOC__
-https://www.section.io/engineering-education/mysql-query-optimization-using-indexes-with-examples/
+=Introducció=
-https://dev.mysql.com/doc/refman/8.0/en/create-index.html
+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.
-https://dev.mysql.com/doc/refman/8.0/en/mysql-indexes.html
+=B-TREE, arbre binari de cerca=
+Tenim els següents municipis:
+DAN, MIT, LUR, BAT, CRE, ZAT, PRI, SAT, FOR, CAL, NOL, EBR, TRO
-SHOW INDEX FROM yourtable;
+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:
-mysql> show index from bd;
+BAT, CAL, CRE, DAN, EBR, FCR, LUR, MIT, NOL, PRI, SAT, TRO, ZAT
-+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
-| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
-+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
-| bd    |          0 | PRIMARY  |            1 | id_bd       | A         |          10 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
-+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
+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).
-B-tree
+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).
-A tree data structure that is popular for use in database indexes. The structure is kept sorted at all times, enabling fast lookup for exact matches (equals operator) and ranges (for example, greater than, less than, and BETWEEN operators). This type of index is available for most storage engines, such as InnoDB and MyISAM.
+<pre>
+                     LUR
+                /            \
+          DAN                     PRI
+        /     \                 /       \
+    CAL        EBR         MIT             TRO
+   /    \         \            \          /    \
+BAT      CRE      FCR          NOL      SAT     ZAT
+</pre>
+É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.
-Exemple: municipis
+Podem respondre a les següents preguntes:
-posar un índex a municipis.municipi
+*Quin camí hem de seguir per cercar el mínim? Resposta: LUR -> DAN -> CAL -> BAT
-i fer un order by municipi
+*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
-http://www.btechsmartclass.com/data_structures/b-trees.html
+Aquest algorisme de cerca és molt més eficient (log(N)), i és el que s'acostuma a utilitzar en les bases de dades.
-To see indexes for all tables within a specific schema you can use the STATISTICS table from INFORMATION_SCHEMA:
+Si t'interessa pots mirar per exemple el següent video:
+*https://www.youtube.com/watch?v=mTMrszfrNtI
-SELECT DISTINCT
+=Els índex a MySQL=
-    TABLE_NAME,
+*https://www.section.io/engineering-education/mysql-query-optimization-using-indexes-with-examples/
-    INDEX_NAME
+*https://dev.mysql.com/doc/refman/8.0/en/create-index.html
-FROM INFORMATION_SCHEMA.STATISTICS
+*https://dev.mysql.com/doc/refman/8.0/en/mysql-indexes.html
-WHERE TABLE_SCHEMA = 'your_schema';
-use information_schema;
+Treballarem sobre la taula ''municipis.municipi''.
-SELECT * FROM statistics;
-</pre>
+Per veure els índex que tenim definits sobre aquesta taula:
 <pre>
-https://www.youtube.com/watch?v=mTMrszfrNtI
 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         |        8380 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
+| 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       |
 +-----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
-row in set (0,01 sec)
+</pre>
+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:
+<pre>
+select municipi from municipis where municipi like 'A%';
 select municipi from municipis order by municipi desc;
+</pre>
+Si tinguéssim un índex sobre el camp ''municipi'' acceleraríem aquesta consulta.
+<pre>
+mysql> select municipi from municipis order by municipi desc;
 rows in set (0,01 sec)
+</pre>
+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:
-EXPLAIN ANALYZE select municipi from municipis order by municipi desc;
+<pre>
+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)
+</pre>
+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
-són 12 ms (2.268 + 10.132)
+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:
+<pre>
 CREATE INDEX municipi_idx ON municipis (municipi);
 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         |        8380 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
 | municipis |          1 | municipi_idx |            1 | municipi    | A         |        8114 |     NULL |   NULL | YES  | BTREE      |         |               | YES     | NULL       |
-+-----------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
 rows in set (0,01 sec)
+</pre>
+Veiem que s'ha creat un índex nou de tipus ''BTREE'' (arbre binari).
-select municipi from municipis order by municipi desc;
+<pre>
+mysql> select municipi from municipis order by municipi desc;
 rows in set (0,00 sec)
+</pre>
-EXPLAIN ANALYZE select municipi from municipis order by municipi desc;
+Aquests 0,00 sec ja indica que ha anat més ràpid, però fem el ''EXPLAIN'' per veure-ho bé:
+<pre>
+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)
+</pre>
+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'''.
-són 4.6 ms. Per tant, són unes 3 vegades més ràpid.
+Podem tornar a eliminar l'índex:
+<pre>
-Actual time to get first row (in milliseconds)
+mysql> DROP INDEX municipi_idx ON municipis;
-Actual time to get all rows (in milliseconds)
-Actual number of rows read
-Actual number of loops
-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)
+</pre>
+Torna a trigar de l'ordre de 12 ms
-Torna a trigar de l'ordre de 12 ms
+=Veure els index definits sobre una taula=
+Ja hem vist la comanda:
+<pre>
+mysql> SHOW INDEX FROM municipis;
+</pre>
+Altres maneres de veure-ho:
+<pre>
+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 |
++------------+--------------+
 </pre>
+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.
 {{Autor}}, febrer 2022

Diferència entre revisions de la pàgina «Creació d'índex. Optimització de consultes»

Revisió de 22:39, 14 feb 2022

Contingut

Introducció

B-TREE, arbre binari de cerca

Els índex a MySQL

Veure els index definits sobre una taula

Menú de navegació

Eines de l'usuari

Espais de noms

Variants

Vistes

Més

Cerca

Navegació

Institut Jaume Balmes

Màquines recreatives

CNC

Informàtica musical

joanillo.org Planet

Eines