¿Debe un índice cubrir todas las columnas seleccionadas para que se pueda usar en ORDER BY?

15

En SO, alguien preguntó recientemente ¿Por qué ORDER BY no usa el índice?

La situación involucraba una simple tabla InnoDB en MySQL que comprende tres columnas y 10k filas. Una de las columnas, un número entero, estaba indexada, y el OP buscó recuperar toda su tabla ordenada en esa columna:

SELECT * FROM person ORDER BY age

Adjuntó el EXPLAINresultado que muestra que esta consulta se resolvió con un filesort(en lugar del índice) y preguntó por qué sería eso.

A pesar de la sugerencia que FORCE INDEX FOR ORDER BY (age) hace que se use el índice , alguien respondió (con comentarios de apoyo / votos a favor de otros) que un índice solo se usa para ordenar cuando las columnas seleccionadas se leen todas del índice (es decir, como normalmente se indicaría Using indexen elExtra columna de EXPLAINsalida). Más tarde se dio una explicación de que atravesar el índice y luego buscar columnas de la tabla da como resultado E / S aleatorias, que MySQL ve como más caras que a filesort.

Esto parece ir en contra del capítulo del manual sobre ORDER BYOptimización , que no solo transmite la fuerte impresión de que la satisfacción ORDER BYde un índice es preferible a realizar una clasificación adicional (de hecho, filesortes una combinación de clasificación rápida y clasificación combinada y, por lo tanto, debe tener un límite inferior de ; mientras camina por el índice en orden y busca en la mesa debería serΩ(nlog n)O(n) , por lo que esto tiene mucho sentido), pero también deja de mencionar esta supuesta "optimización" al tiempo que afirma:

Las siguientes consultas usan el índice para resolver la ORDER BYparte:

SELECT * FROM t1
  ORDER BY key_part1,key_part2,... ;

Para mi lectura, ese es precisamente el caso en esta situación (sin embargo, el índice no se estaba utilizando sin una pista explícita).

Mis preguntas son:

  • ¿Es realmente necesario que todas las columnas seleccionadas se indexen para que MySQL elija usar el índice?

    • Si es así, ¿dónde está esto documentado (si es que lo hay)?

    • Si no, ¿qué estaba pasando aquí?

mysql index innodb order-by eggyal
fuente

Respuestas:

14

¿Es realmente necesario que todas las columnas seleccionadas se indexen para que MySQL elija usar el índice?

Esta es una pregunta cargada porque hay factores que determinan si vale la pena usar un índice.

FACTOR # 1

Para cualquier índice dado, ¿cuál es la población clave? En otras palabras, ¿cuál es la cardinalidad (recuento distinto) de todas las tuplas registradas en el índice?

FACTOR # 2

¿Qué motor de almacenamiento estás usando? ¿Se puede acceder a todas las columnas necesarias desde un índice?

QUE SIGUE ???

Tomemos un ejemplo simple: una tabla que contiene dos valores (Masculino y Femenino)

Dejemos crear una tabla con una prueba para el uso del índice

USE test
DROP TABLE IF EXISTS mf;
CREATE TABLE mf
(
    id int not null auto_increment,
    gender char(1),
    primary key (id),
    key (gender)
) ENGINE=InnODB;
INSERT INTO mf (gender) VALUES
('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
('M'),('M'),('M'),('M'),('F'),('F'),('M'),('M'),
('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
('F'),('M'),('M'),('M'),('M'),('M'),('M'),('M');
ANALYZE TABLE mf;
EXPLAIN SELECT gender FROM mf WHERE gender='F';
EXPLAIN SELECT gender FROM mf WHERE gender='M';
EXPLAIN SELECT id FROM mf WHERE gender='F';
EXPLAIN SELECT id FROM mf WHERE gender='M';

PRUEBA InnoDB

mysql> USE test
Database changed
mysql> DROP TABLE IF EXISTS mf;
Query OK, 0 rows affected (0.00 sec)

mysql> CREATE TABLE mf
    -> (
    ->     id int not null auto_increment,
    ->     gender char(1),
    ->     primary key (id),
    ->     key (gender)
    -> ) ENGINE=InnoDB;
Query OK, 0 rows affected (0.07 sec)

mysql> INSERT INTO mf (gender) VALUES
    -> ('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
    -> ('M'),('M'),('M'),('M'),('F'),('F'),('M'),('M'),
    -> ('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
    -> ('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
    -> ('F'),('M'),('M'),('M'),('M'),('M'),('M'),('M');
Query OK, 40 rows affected (0.06 sec)
Records: 40  Duplicates: 0  Warnings: 0

mysql> ANALYZE TABLE mf;
+---------+---------+----------+----------+
| Table   | Op      | Msg_type | Msg_text |
+---------+---------+----------+----------+
| test.mf | analyze | status   | OK       |
+---------+---------+----------+----------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT gender FROM mf WHERE gender='F';
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |    3 | Using where; Using index |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT gender FROM mf WHERE gender='M';
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |   37 | Using where; Using index |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT id FROM mf WHERE gender='F';
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |    3 | Using where; Using index |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT id FROM mf WHERE gender='M';
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |   37 | Using where; Using index |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

mysql>

PRUEBA MyISAM

mysql> USE test
Database changed
mysql> DROP TABLE IF EXISTS mf;
Query OK, 0 rows affected (0.00 sec)

mysql> CREATE TABLE mf
    -> (
    ->     id int not null auto_increment,
    ->     gender char(1),
    ->     primary key (id),
    ->     key (gender)
    -> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.05 sec)

mysql> INSERT INTO mf (gender) VALUES
    -> ('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
    -> ('M'),('M'),('M'),('M'),('F'),('F'),('M'),('M'),
    -> ('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
    -> ('M'),('M'),('M'),('M'),('M'),('M'),('M'),('M'),
    -> ('F'),('M'),('M'),('M'),('M'),('M'),('M'),('M');
Query OK, 40 rows affected (0.00 sec)
Records: 40  Duplicates: 0  Warnings: 0

mysql> ANALYZE TABLE mf;
+---------+---------+----------+----------+
| Table   | Op      | Msg_type | Msg_text |
+---------+---------+----------+----------+
| test.mf | analyze | status   | OK       |
+---------+---------+----------+----------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT gender FROM mf WHERE gender='F';
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |    3 | Using where; Using index |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT gender FROM mf WHERE gender='M';
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |   36 | Using where; Using index |
+----+-------------+-------+------+---------------+--------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT id FROM mf WHERE gender='F';
+----+-------------+-------+------+---------------+--------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra       |
+----+-------------+-------+------+---------------+--------+---------+-------+------+-------------+
|  1 | SIMPLE      | mf    | ref  | gender        | gender | 2       | const |    3 | Using where |
+----+-------------+-------+------+---------------+--------+---------+-------+------+-------------+
1 row in set (0.00 sec)

mysql> EXPLAIN SELECT id FROM mf WHERE gender='M';
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | mf    | ALL  | gender        | NULL | NULL    | NULL |   40 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)

mysql>

Análisis para InnoDB

Cuando los datos se cargaron como InnoDB, tenga en cuenta que los cuatro EXPLAINplanes utilizaron el genderíndice. Los EXPLAINplanes tercero y cuarto utilizaron el genderíndice a pesar de que los datos solicitados eran id. ¿Por qué? Porque idestá en PRIMARY KEYy todos los índices secundarios tienen punteros de referencia de regreso a PRIMARY KEY(a través de gen_clust_index ).

Análisis para MyISAM

Cuando los datos se cargaron como MyISAM, tenga en cuenta que los primeros tres EXPLAINplanes utilizaron el genderíndice. En el cuarto EXPLAINplan, el Optimizador de consultas decidió no utilizar ningún índice. Optó por un escaneo completo de la tabla en su lugar. ¿Por qué?

Independientemente de DBMS, los optimizadores de consultas funcionan con una regla general muy simple: si se analiza un índice como candidato para realizar la búsqueda y el Optimizador de consultas calcula que debe buscar más del 5% del número total de filas en la tabla:

  • se realiza una exploración completa del índice si todas las columnas necesarias para la recuperación están en el índice seleccionado
  • una exploración de tabla completa de lo contrario

CONCLUSIÓN

Si no tiene índices de cobertura adecuados, o si la población clave para cualquier tupla es más del 5% de la tabla, deben suceder seis cosas:

  1. Darse cuenta de que debe perfilar las consultas
  2. Encuentra todos WHERE, GROUP BYy el orden BY` cláusulas de esas consultas
  3. Formule índices en este orden
    • WHERE columnas de cláusula con valores estáticos
    • GROUP BY columnas
    • ORDER BY columnas
  4. Evite escaneos de tabla completa (consultas que carecen de una WHEREcláusula sensata )
  5. Evite poblaciones de clave incorrecta (o al menos guarde en caché esas poblaciones de clave incorrecta)
  6. Decidir sobre el mejor motor de almacenamiento de MySQL ( InnoDB o MyISAM ) de las Tablas

He escrito sobre esta regla general del 5% en el pasado:

ACTUALIZACIÓN 2012-11-14 13:05 EDT

Eché un vistazo a tu pregunta y a la publicación SO original . Entonces, pensé en lo Analysis for InnoDBque mencioné antes. Coincide con la personmesa. ¿Por qué?

Para ambas mesas mfyperson

  • El motor de almacenamiento es InnoDB
  • La clave primaria es id
  • El acceso a la tabla es por índice secundario
  • Si la tabla fuera MyISAM, veríamos un EXPLAINplan completamente diferente

Ahora, mira a la consulta de la cuestión SO: select * from person order by age\G. Como no hay WHEREcláusula, usted solicitó explícitamente un escaneo completo de la tabla . El orden de clasificación predeterminado de la tabla sería por id(PRIMARY KEY) debido a su auto_increment y el gen_clust_index (también conocido como Clustered Index) está ordenado por rowid interno . Cuando ordenó por el índice, tenga en cuenta que los índices secundarios de InnoDB tienen el rowid adjunto a cada entrada de índice. Esto produce la necesidad interna de acceso completo a las filas cada vez.

Configurar ORDER BYen una tabla InnoDB puede ser una tarea bastante desalentadora si ignora estos hechos sobre cómo se organizan los índices de InnoDB.

Volviendo a esa consulta SO, ya que explícitamente exigió un escaneo completo de la tabla , en mi humilde opinión, MySQL Query Optimizer hizo lo correcto (o al menos, eligió el camino de menor resistencia). Cuando se trata de InnoDB y la consulta SO, es mucho más fácil realizar un escaneo completo de la tabla y luego algunos en filesortlugar de hacer un escaneo de índice completo y una búsqueda de fila a través del gen_clust_index para cada entrada de índice secundario.

No soy partidario del uso de Index Hints porque ignora el plan EXPLAIN. No obstante, si realmente conoce sus datos mejor que InnoDB, tendrá que recurrir a Indicaciones de índice, especialmente con consultas que no tienen WHEREcláusula.

ACTUALIZACIÓN 2012-11-14 14:21 EDT

De acuerdo con el libro Understanding MySQL Internals

ingrese la descripción de la imagen aquí

El párrafo 7 de la página 202 dice lo siguiente:

Los datos se almacenan en una estructura especial llamada índice agrupado , que es un árbol B con la clave primaria que actúa como el valor clave, y el registro real (en lugar de un puntero) en la parte de datos. Por lo tanto, cada tabla InnoDB debe tener una clave primaria. Si no se proporciona uno, se agrega una columna de ID de fila especial que normalmente no es visible para el usuario para que actúe como clave principal. Una clave secundaria almacenará el valor de la clave primaria que identifica el registro. El código del árbol B se puede encontrar en innobase / btr / btr0btr.c .

Es por eso que dije antes: es mucho más fácil realizar un escaneo completo de la tabla y luego ordenar algunos archivos en lugar de hacer un escaneo de índice completo y una búsqueda de fila a través del gen_clust_index para cada entrada de índice secundaria . InnoDB va a hacer una búsqueda de doble índice cada vez . Eso suena un poco brutal, pero esos son solo los hechos. Nuevamente, tenga en cuenta la falta de WHEREcláusula. Esto, en sí mismo, es una pista para que MySQL Query Optimizer haga un escaneo completo de la tabla.

RolandoMySQLDBA
fuente
Rolando, gracias por una respuesta tan minuciosa y detallada. Sin embargo, no parece ser relevante para seleccionar índices FOR ORDER BY(que es el caso específico en esta pregunta). La pregunta decía que en este caso el motor de almacenamiento era InnoDB(y la pregunta SO original muestra que las 10k filas están distribuidas de manera bastante uniforme en 8 elementos, la cardinalidad tampoco debería ser un problema aquí). Lamentablemente, no creo que esto responda la pregunta.
eggyal
Esto es interesante, ya que la primera parte también fue mi primer instinto (no tenía una buena cardinalidad, por lo que mysql decidió usar el escaneo completo). Pero cuanto más leía, esa regla no parecía aplicarse al orden por optimización. ¿Está seguro de que ordena por clave primaria para índices agrupados innodb? Esta publicación indica que la clave principal se agrega al final, entonces, ¿no estaría el tipo en las columnas explícitas del índice? En resumen, ¡todavía estoy perplejo!
Derek Downey
1
El filesortOptimizador de consultas decidió la selección por una simple razón: carece de conocimiento previo de los datos que tiene. Si su elección de usar pistas de índice (basado en el problema # 2) le brinda un tiempo de ejecución satisfactorio, entonces, por todos los medios, hágalo. La respuesta que proporcioné fue solo un ejercicio académico para mostrar cuán temperamental puede ser el MySQL Query Optimizer, así como sugerir cursos de acción.
RolandoMySQLDBA
1
He leído y releído esta y otras publicaciones, y solo puedo estar de acuerdo en que esto tiene que ver con el pedido innodb en la clave principal, ya que estamos seleccionando todos (y no un índice de cobertura). Me sorprende que no se mencione esta rareza específica de InnoDB en la página del documento de optimización ORDER BY. De todos modos, +1 a Rolando
Derek Downey
1
@eggyal Esto fue escrito esta semana. Observe el mismo plan EXPLAIN y la exploración completa demorará más si el conjunto de datos no cabe en la memoria.
Derek Downey el
0

Adaptado (con permiso) de la respuesta de Denis a otra pregunta sobre SO:

Dado que la consulta obtendrá todos los registros (o casi todos), por lo general, es mejor que no tenga ningún índice. La razón de esto es que en realidad cuesta algo leer un índice.

A medida que avanza por toda la tabla, leer secuencialmente la tabla y ordenar sus filas en la memoria puede ser su plan más barato. Si solo necesita unas pocas filas y la mayoría coincidirá con la cláusula where, buscar el índice más pequeño será suficiente.

Para entender por qué, imagine la E / S del disco involucrada.

Supongamos que desea toda la tabla sin un índice. Para hacer esto, lee data_page1, data_page2, data_page3, etc., visitando las distintas páginas del disco involucradas en orden, hasta llegar al final de la tabla. Luego, clasifica y regresa.

Si desea las 5 filas superiores sin un índice, leería secuencialmente toda la tabla como antes, mientras ordena en montón las 5 filas superiores. Es cierto que eso es mucha lectura y clasificación para un puñado de filas.

Supongamos, ahora, que desea toda la tabla con un índice. Para hacer esto, lea index_page1, index_page2, etc., secuencialmente. Esto lo lleva a visitar, digamos, data_page3, luego data_page1, luego data_page3 nuevamente, luego data_page2, etc., en un orden completamente aleatorio (aquel por el cual las filas ordenadas aparecen en los datos). El IO involucrado hace que sea más barato simplemente leer todo el desorden secuencialmente y clasificar la bolsa de mano en la memoria.

Si simplemente desea las 5 primeras filas de una tabla indexada, en contraste, usar el índice se convierte en la estrategia correcta. En el peor de los casos, carga 5 páginas de datos en la memoria y continúa.

Un buen planificador de consultas SQL, por cierto, tomará una decisión sobre si usar un índice o no en función de cuán fragmentados estén sus datos. Si buscar filas en orden significa hacer zoom de un lado a otro de la tabla, un buen planificador puede decidir que no vale la pena usar el índice. Por el contrario, si la tabla se agrupa usando ese mismo índice, se garantiza que las filas estén en orden, lo que aumenta la probabilidad de que se use.

Pero luego, si une la misma consulta con otra tabla y esa otra tabla tiene una cláusula where extremadamente selectiva que puede usar un índice pequeño, el planificador podría decidir que en realidad es mejor, por ejemplo, buscar todos los ID de las filas etiquetadas como foohash unirse a las tablas y ordenarlas en memoria.

eggyal
fuente