Um índice deve cobrir todas as colunas selecionadas para que seja usado para ORDER BY?

15

Na SO, alguém perguntou recentemente Por que ORDER BY não está usando o índice?

A situação envolvia uma tabela simples do InnoDB no MySQL, composta por três colunas e 10 mil linhas. Uma das colunas, um número inteiro, foi indexada - e o OP procurou recuperar sua tabela inteira classificada nessa coluna:

SELECT * FROM person ORDER BY age

Ele anexou a EXPLAINsaída mostrando que essa consulta foi resolvida com um filesort(e não o índice) e perguntou por que isso seria.

Apesar da dica que faz FORCE INDEX FOR ORDER BY (age) com que o índice seja usado , alguém respondeu (com comentários / upvotes de terceiros) que um índice é usado apenas para classificação quando todas as colunas selecionadas são lidas no índice (ou seja, como normalmente seria indicado Using indexna Extracoluna de EXPLAINsaída). Mais tarde, foi dada uma explicação de que percorrer o índice e buscar colunas da tabela resulta em E / S aleatória, que o MySQL vê como mais cara que a filesort.

Isso parece ir direto para o capítulo manual sobre ORDER BYOtimização , que não apenas transmite a forte impressão de que a satisfação ORDER BYde um índice é preferível à realização de uma classificação adicional (de fato, filesorté uma combinação de quicksort e mergesort e, portanto, deve ter um limite inferior de ; enquanto percorria o índice em ordem e procurava a tabela, o que faz todo o sentido), mas também deixa de mencionar essa suposta "otimização", além de afirmar:Ω(nlog n)O(n)

As consultas a seguir usam o índice para resolver a ORDER BYpeça:

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

A meu ver, é precisamente o caso nessa situação (ainda assim, o índice não estava sendo usado sem uma dica explícita).

Minhas perguntas são:

  • É realmente necessário que todas as colunas selecionadas sejam indexadas para que o MySQL opte por usar o índice?

    • Em caso afirmativo, onde isso está documentado (se houver)?

    • Se não, o que estava acontecendo aqui?

mysql index innodb order-by eggyal
fonte

Respostas:

14

É realmente necessário que todas as colunas selecionadas sejam indexadas para que o MySQL opte por usar o índice?

Esta é uma pergunta carregada, porque existem fatores que determinam se vale a pena usar um índice.

FATOR 1

Para qualquer índice, qual é a população principal? Em outras palavras, qual é a cardinalidade (contagem distinta) de todas as tuplas registradas no índice?

FATOR 2

Qual mecanismo de armazenamento você está usando? Todas as colunas necessárias são acessíveis a partir de um índice?

QUAL É O PRÓXIMO ???

Vamos dar um exemplo simples: uma tabela que contém dois valores (masculino e feminino)

Vamos criar uma tabela com um teste para uso do í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';

TEST 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>

TESTE 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álise para InnoDB

Quando os dados foram carregados como InnoDB, observe que todos os quatro EXPLAINplanos usaram o genderíndice. O terceiro e o quarto EXPLAINplanos usavam o genderíndice, apesar dos dados solicitados id. Por quê? Porque idestá no PRIMARY KEYe todos os índices secundários têm ponteiros de referência de volta para PRIMARY KEY(via gen_clust_index ).

Análise para MyISAM

Quando os dados foram carregados como MyISAM, observe que os três primeiros EXPLAINplanos usaram o genderíndice. No quarto EXPLAINplano, o Query Optimizer decidiu não usar um índice. Optou por uma verificação completa da tabela. Por quê?

Independentemente do DBMS, o Query Optimizers opera com uma regra prática muito simples: se um índice estiver sendo exibido como candidato a ser usado para realizar a pesquisa, o Query Optimizer calcula que ele deve pesquisar mais de 5% do número total de linhas na tabela:

  • uma verificação completa do índice é feita se todas as colunas necessárias para recuperação estiverem no índice selecionado
  • uma verificação completa da tabela, caso contrário

CONCLUSÃO

Se você não possui índices de cobertura adequados ou se a população-chave de uma determinada tupla é superior a 5% da tabela, seis coisas devem acontecer:

  1. Venha para a conclusão de que você deve criar um perfil das consultas
  2. Localizar todos WHERE, GROUP BYea ordem BY` cláusulas dessas consultas
  3. Formule índices nesta ordem
    • WHERE colunas de cláusula com valores estáticos
    • GROUP BY colunas
    • ORDER BY colunas
  4. Evitar verificações completas da tabela (consultas sem uma WHEREcláusula sensata )
  5. Evite populações de chaves ruins (ou pelo menos armazene em cache essas populações de chaves ruins)
  6. Decida o melhor mecanismo de armazenamento MySQL ( InnoDB ou MyISAM ) para as tabelas

Eu escrevi sobre essa regra prática de 5% no passado:

UPDATE 2012-11-14 13:05 EDT

Analisamos sua pergunta e a postagem original do SO . Então, pensei sobre o Analysis for InnoDBque mencionei antes. Isso coincide com a personmesa. Por quê?

Para ambas as tabelas mfeperson

  • O mecanismo de armazenamento é o InnoDB
  • Chave primária é id
  • O acesso à tabela é por índice secundário
  • Se a tabela fosse MyISAM, veríamos um EXPLAINplano completamente diferente

Agora, olhe para a consulta da questão SO: select * from person order by age\G. Como não há WHEREcláusula, você exigiu explicitamente uma verificação completa da tabela . A ordem de classificação padrão da tabela seria por id(PRIMARY KEY) devido ao seu auto_increment e ao gen_clust_index (também conhecido como Índice de Cluster) é ordenado pelo rowid interno . Quando você solicitou o índice, lembre-se de que os índices secundários do InnoDB têm o ID da linha anexado a cada entrada do índice. Isso produz a necessidade interna de acesso de linha completa a cada vez.

Configurando ORDER BY uma tabela do InnoDB pode ser uma tarefa bastante assustadora se você ignorar esses fatos sobre como os índices do InnoDB são organizados.

Voltando à consulta SO, desde que você exigiu explicitamente uma verificação completa da tabela , IMHO, o MySQL Query Optimizer fez a coisa correta (ou pelo menos escolheu o caminho de menor resistência). Quando se trata do InnoDB e da consulta SO, é muito mais fácil executar uma varredura completa da tabela e, em seguida, algumas, em filesortvez de fazer uma varredura completa do índice e uma pesquisa de linha através do gen_clust_index para cada entrada secundária do índice.

Eu não sou um defensor do uso de dicas de índice, porque ignora o plano EXPLAIN. Não obstante, se você realmente conhece seus dados melhor que o InnoDB, precisará recorrer às Dicas de índice, especialmente com consultas que não têmWHERE cláusula.

UPDATE 2012-11-14 14:21 EDT

De acordo com o livro Entendendo o MySQL Internals

insira a descrição da imagem aqui

O parágrafo 7 diz o seguinte:

Os dados são armazenados em uma estrutura especial chamada índice clusterizado , que é uma árvore B com a chave primária atuando como valor da chave e o registro real (em vez de um ponteiro) na parte dos dados. Assim, cada tabela do InnoDB deve ter uma chave primária. Se um não for fornecido, uma coluna de ID de linha especial normalmente não visível para o usuário será adicionada para atuar como uma chave primária. Uma chave secundária armazenará o valor da chave primária que identifica o registro. O código da árvore B pode ser encontrado em innobase / btr / btr0btr.c .

É por isso que afirmei anteriormente: é muito mais fácil executar uma varredura completa da tabela e, em seguida, alguns arquivos, em vez de fazer uma varredura completa do índice e uma pesquisa de linha através do gen_clust_index para cada entrada secundária do índice . O InnoDB fará uma pesquisa de índice duplo toda vez . Isso parece meio brutal, mas esses são apenas os fatos. Novamente, leve em consideração a falta de WHEREcláusula. Essa, por si só, é a dica para o MySQL Query Optimizer para fazer uma varredura completa da tabela.

RolandoMySQLDBA
fonte
Rolando, obrigado por uma resposta tão completa e detalhada. No entanto, não parece ser relevante para selecionar índices FOR ORDER BY(que é o caso específico desta pergunta). A pergunta afirmava que, nesse caso, o mecanismo de armazenamento era InnoDB(e a pergunta SO original mostra que as 10 mil linhas são distribuídas de maneira bastante uniforme em 8 itens, a cardinalidade também não deve ser um problema aqui). Infelizmente, não acho que isso responda à pergunta.
eggyal 14/11/12
Isso é interessante, pois a primeira parte também foi meu primeiro instinto (não tinha uma boa cardinalidade, então o mysql escolheu usar a varredura completa). Mas quanto mais eu leio, essa regra não parece se aplicar a pedidos por otimização. Tem certeza de que ele ordena por chave primária para índices agrupados do innodb? Esta postagem indica que a chave primária é adicionada ao final. Portanto, a classificação ainda não estaria na (s) coluna (s) explícita (s) do índice? Em suma, ainda estou perplexo!
Derek Downey
1
A filesortseleção foi decidida pelo Query Optimizer por um motivo simples: falta conhecimento prévio dos dados que você possui. Se a sua escolha de usar dicas de índice (com base no problema nº 2) lhe proporcionar um tempo de execução satisfatório, faça o que for necessário. A resposta que forneci foi apenas um exercício acadêmico para mostrar como o MySQL Query Optimizer pode ser temperamental, além de sugerir cursos de ação.
RolandoMySQLDBA
1
Li e reli esta e outras postagens, e só posso concordar que isso tem a ver com a ordem do innodb na chave primária, pois estamos selecionando tudo (e não um índice de cobertura). Estou surpreso que não haja menção a essa estranheza específica do InnoDB na página do documento de otimização ORDER BY. Enfim, +1 para Rolando
Derek Downey
1
@eggyal Isso foi escrito esta semana. Observe o mesmo plano EXPLAIN e a verificação completa levará mais tempo se o conjunto de dados não couber na memória.
Derek Downey
0

Adaptado (com permissão) da resposta de Denis para outra pergunta no SO:

Como todos os registros (ou quase todos) serão buscados pela consulta, você geralmente fica melhor sem nenhum índice. A razão para isso é que, na verdade, custa algo para ler um índice.

Ao percorrer a tabela inteira, a leitura seqüencial da tabela e a classificação de suas linhas na memória pode ser o seu plano mais barato. Se você precisar apenas de algumas linhas e a maioria corresponder à cláusula where, buscar o menor índice fará o truque.

Para entender o porquê, imagine a E / S do disco envolvida.

Suponha que você queira a tabela inteira sem um índice. Para fazer isso, você lê dados_página1, dados_página2, dados_página3, etc., visitando as várias páginas do disco envolvidas em ordem, até chegar ao final da tabela. Você então classifica e retorna.

Se você deseja as 5 principais linhas sem um índice, leia sequencialmente a tabela inteira como antes, enquanto classifica em heap as 5 principais linhas. É certo que é muita leitura e classificação para algumas linhas.

Suponha, agora, que você queira a tabela inteira com um índice. Para fazer isso, você lê index_page1, index_page2, etc., sequencialmente. Isso leva você a visitar, digamos, data_page3, data_page1, data_page3 novamente, data_page2, etc., em uma ordem completamente aleatória (aquela pela qual as linhas classificadas aparecem nos dados). O IO envolvido torna mais barato apenas ler toda a bagunça sequencialmente e classificar a sacola na memória.

Se você deseja apenas as 5 principais linhas de uma tabela indexada, pelo contrário, o uso do índice se torna a estratégia correta. Na pior das hipóteses, você carrega 5 páginas de dados na memória e segue em frente.

Um bom planejador de consultas SQL, btw, tomará a decisão de usar ou não um índice com base na fragmentação dos seus dados. Se buscar linhas em ordem significa aumentar e retroceder a tabela, um bom planejador pode decidir que não vale a pena usar o índice. Por outro lado, se a tabela estiver agrupada em cluster usando o mesmo índice, é garantido que as linhas estejam em ordem, aumentando a probabilidade de utilização.

Porém, se você juntar a mesma consulta a outra tabela e essa outra tabela tiver uma cláusula where extremamente seletiva que pode usar um índice pequeno, o planejador poderá decidir que é realmente melhor, por exemplo, buscar todos os IDs de linhas marcadas como foohash junte-se às tabelas e monte-as na memória.

eggyal
fonte