Muss ein Index alle ausgewählten Spalten abdecken, damit er für ORDER BY verwendet werden kann?

15

Drüben bei SO hat kürzlich jemand gefragt, warum ORDER BY den Index nicht verwendet.

Die Situation beinhaltete eine einfache InnoDB-Tabelle in MySQL mit drei Spalten und 10.000 Zeilen. Eine der Spalten, eine Ganzzahl, wurde indiziert - und das OP versuchte, seine gesamte Tabelle abzurufen, die nach dieser Spalte sortiert war:

SELECT * FROM person ORDER BY age

Er fügte eine EXPLAINAusgabe hinzu, aus der hervorgeht, dass diese Abfrage mit einem filesort(anstelle des Index) gelöst wurde, und fragte, warum dies der Fall sei.

Trotz des Hinweises FORCE INDEX FOR ORDER BY (age) , der zur Verwendung des Indexes führte , antwortete jemand (mit unterstützenden Kommentaren / Gegenstimmen von anderen), dass ein Index nur zum Sortieren verwendet wird, wenn alle ausgewählten Spalten aus dem Index gelesen wurden (dh wie normalerweise Using indexin der ExtraSpalte angegeben) der EXPLAINAusgabe). Später wurde erklärt, dass das Durchlaufen des Index und das anschließende Abrufen von Spalten aus der Tabelle zu zufälligen E / A-Vorgängen führt, die MySQL als teurer ansieht als a filesort.

Dies scheint auf in das Gesicht des Handbuchs Kapitel zu fliegen ORDER BYOptimierung , die nicht nur den starken Eindruck vermittelt , dass Befriedigung ORDER BYvon einem Index zu Ausführen einer zusätzlichen Sortierung vorzuziehen ist (in der Tat, filesortist eine Kombination aus quicksort und mergesort und deshalb muss haben eine untere Grenze ; beim Durchgehen des Indexes in der richtigen Reihenfolge und beim Suchen in der Tabelle sollte es so sein (das macht also durchaus Sinn), aber es wird auch vernachlässigt, diese angebliche "Optimierung" zu erwähnen, und gleichzeitig Folgendes angegeben:Ω(nlog n)O(n)

Die folgenden Abfragen verwenden den Index, um das ORDER BYTeil aufzulösen :

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

Meiner Meinung nach ist dies in dieser Situation genau der Fall (der Index wurde jedoch nicht ohne ausdrücklichen Hinweis verwendet).

Meine Fragen sind:

  • Müssen tatsächlich alle ausgewählten Spalten indiziert werden, damit MySQL den Index verwenden kann?

    • Wenn ja, wo ist dies (wenn überhaupt) dokumentiert?

    • Wenn nicht, was war hier los?

eggyal
quelle

Antworten:

14

Müssen tatsächlich alle ausgewählten Spalten indiziert werden, damit MySQL den Index verwenden kann?

Dies ist eine geladene Frage, da es Faktoren gibt, die bestimmen, ob ein Index die Verwendung wert ist.

FAKTOR 1

Wie lautet die Schlüsselpopulation für einen bestimmten Index? Mit anderen Worten, wie hoch ist die Kardinalität (eindeutige Anzahl) aller im Index erfassten Tupel?

FAKTOR 2

Welche Speicher-Engine verwenden Sie? Sind alle benötigten Spalten über einen Index zugänglich?

WAS KOMMT ALS NÄCHSTES ???

Nehmen wir ein einfaches Beispiel: Eine Tabelle mit zwei Werten (männlich und weiblich)

Lassen Sie eine solche Tabelle mit einem Test für die Indexverwendung erstellen

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>

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

Analyse für InnoDB

Beachten Sie, dass beim Laden der Daten als InnoDB alle vier EXPLAINPläne den genderIndex verwendeten. Der dritte und vierte EXPLAINPlan verwendeten den genderIndex, obwohl die angeforderten Daten vorhanden waren id. Warum? Denn idin den PRIMARY KEYund allen Sekundärindizes gibt es Referenzzeiger zurück zum PRIMARY KEY(über den gen_clust_index ).

Analyse für MyISAM

Beachten Sie, dass die ersten drei EXPLAINPläne den genderIndex verwendeten , als die Daten als MyISAM geladen wurden . Im vierten EXPLAINPlan hat das Abfrageoptimierungsprogramm entschieden, überhaupt keinen Index zu verwenden. Stattdessen wurde ein vollständiger Tabellenscan gewählt. Warum?

Unabhängig von DBMS arbeiten die Abfrageoptimierer mit einer sehr einfachen Faustregel: Wenn ein Index als Kandidat für die Durchführung der Suche überprüft wird und das Abfrageoptimierungsprogramm berechnet, dass mehr als 5% der Gesamtzahl der Suchvorgänge ausgeführt werden müssen Zeilen in der Tabelle:

  • Ein vollständiger Index-Scan wird durchgeführt, wenn sich alle zum Abrufen erforderlichen Spalten im ausgewählten Index befinden
  • ansonsten ein vollständiger Tabellenscan

FAZIT

Wenn Sie nicht die richtigen Deckungsindizes haben oder wenn die Schlüsselpopulation für ein bestimmtes Tupel mehr als 5% der Tabelle beträgt, müssen sechs Dinge geschehen:

  1. Stellen Sie fest, dass Sie die Abfragen profilieren müssen
  2. Finden Sie alle WHERE, GROUP BYund ORDER BY` Klauseln aus diesen Abfragen
  3. Formulieren Sie die Indizes in dieser Reihenfolge
    • WHERE Klauselspalten mit statischen Werten
    • GROUP BY Säulen
    • ORDER BY Säulen
  4. Vermeiden Sie vollständige Tabellenscans (Abfragen ohne sinnvolle WHEREKlausel)
  5. Vermeiden Sie fehlerhafte Schlüsselpopulationen (oder zwischenspeichern Sie zumindest diese fehlerhaften Schlüsselpopulationen)
  6. Entscheiden Sie sich für die beste MySQL Storage Engine ( InnoDB oder MyISAM ) für die Tabellen

Ich habe in der Vergangenheit über diese Faustregel von 5% geschrieben:

UPDATE 2012-11-14 13:05 EDT

Ich habe mir Ihre Frage und den ursprünglichen SO-Beitrag noch einmal angesehen . Dann dachte ich an meine, die Analysis for InnoDBich zuvor erwähnt hatte. Es fällt mit dem personTisch zusammen. Warum?

Für beide Tabellen mfundperson

  • Die Storage Engine ist InnoDB
  • Primärschlüssel ist id
  • Der Tabellenzugriff erfolgt über den sekundären Index
  • Wenn der Tisch MyISAM wäre, würden wir einen völlig anderen EXPLAINPlan sehen

Nun sehen Sie die Abfrage aus der SO Frage: select * from person order by age\G. Da es keine WHEREKlausel gibt, haben Sie ausdrücklich einen vollständigen Tabellenscan verlangt . Die Standardsortierreihenfolge der Tabelle wäre nach id(PRIMARY KEY), da sie auto_increment und the ist gen_clust_index (aka Clustered Index) nach interner Zeilen-ID sortiert ist . Beachten Sie bei der Sortierung nach Index, dass InnoDB-Sekundärindizes die Zeilen-ID an jeden Indexeintrag angehängt haben. Dies erzeugt jedes Mal den internen Bedarf für vollen Zeilenzugriff.

Einrichten ORDER BY einer InnoDB-Tabelle kann eine ziemlich entmutigende Aufgabe sein, wenn Sie diese Fakten über die Organisation von InnoDB-Indizes ignorieren.

Zurück zu dieser SO-Abfrage: Da Sie ausdrücklich einen vollständigen Tabellenscan gefordert haben , hat der MySQL Query Optimizer IMHO das Richtige getan (oder zumindest den Pfad des geringsten Widerstands gewählt). Wenn es um InnoDB und die SO-Abfrage geht, ist es weitaus einfacher, einen vollständigen Tabellenscan durchzuführen als bei einigen anderenfilesort als einen vollständigen Indexscan und eine Zeilensuche über den gen_clust_index für jeden sekundären Indexeintrag.

Ich bin kein Befürworter der Verwendung von Indexhinweisen, da der EXPLAIN-Plan ignoriert wird. Wenn Sie Ihre Daten jedoch wirklich besser kennen als InnoDB, müssen Sie auf Indexhinweise zurückgreifen, insbesondere bei Abfragen ohne WHEREKlausel.

UPDATE 2012-11-14 14:21 EDT

Nach dem Buch MySQL-Interna verstehen

Bildbeschreibung hier eingeben

Seite 202 Absatz 7 besagt Folgendes:

Die Daten werden in einer speziellen Struktur gespeichert , die als Clustered-Index bezeichnet wird. Dabei handelt es sich um einen B-Baum mit dem Primärschlüssel als Schlüsselwert und dem tatsächlichen Datensatz (anstelle eines Zeigers) im Datenteil. Daher muss jede InnoDB-Tabelle einen Primärschlüssel haben. Wenn keine angegeben ist, wird eine spezielle Zeilen-ID-Spalte hinzugefügt, die für den Benutzer normalerweise nicht sichtbar ist, und dient als Primärschlüssel. Ein Sekundärschlüssel speichert den Wert des Primärschlüssels, der den Datensatz identifiziert. Der B-Tree-Code befindet sich in innobase / btr / btr0btr.c .

Aus diesem Grund habe ich bereits ausgeführt: Es ist viel einfacher, einen vollständigen Tabellenscan und dann einen Dateisort durchzuführen, als für jeden sekundären Indexeintrag einen vollständigen Indexscan und eine Zeilensuche über den gen_clust_index durchzuführen . InnoDB wird jedes Mal einen Doppelindex-Lookup durchführen . Das klingt brutal, aber das sind nur die Fakten. Berücksichtigen Sie auch hier die fehlende WHEREKlausel. Dies ist an sich der Hinweis für den MySQL Query Optimizer, einen vollständigen Tabellenscan durchzuführen.

RolandoMySQLDBA
quelle
Rolando, vielen Dank für diese gründliche und detaillierte Antwort. Es scheint jedoch nicht relevant für die Auswahl von Indizes zu sein FOR ORDER BY(was in dieser Frage der Sonderfall ist). Die Frage ergab, dass in diesem Fall die Speicher-Engine war InnoDB(und die ursprüngliche SO-Frage zeigt, dass die 10-KB-Zeilen ziemlich gleichmäßig auf 8 Elemente verteilt sind, Kardinalität sollte auch hier kein Problem sein). Leider glaube ich nicht, dass dies die Frage beantwortet.
Eggyal
Dies ist interessant, da der erste Teil auch mein erster Instinkt war (er hatte keine gute Kardinalität, daher entschied sich mysql für die Verwendung des vollständigen Scans). Aber je mehr ich las, desto weniger schien diese Regel für die Optimierung der Reihenfolge zu gelten. Sind Sie sicher, dass die Reihenfolge für Innodb-Clustered-Indizes nach Primärschlüssel erfolgt? Dieser Beitrag gibt an, dass der Primärschlüssel am Ende hinzugefügt wird. Wäre die Sortierung also nicht immer noch in den expliziten Spalten des Index? Kurz gesagt, ich bin immer noch ratlos!
Derek Downey
1
Die filesortAuswahl wurde vom Abfrageoptimierungsprogramm aus einem einfachen Grund festgelegt: Es fehlen Vorkenntnisse zu den von Ihnen zur Verfügung gestellten Daten. Wenn Sie sich für die Verwendung von Indexhinweisen (basierend auf Ausgabe 2) entscheiden, um eine zufriedenstellende Laufzeit zu erzielen, sollten Sie sich auf jeden Fall dafür entscheiden. Die Antwort, die ich gegeben habe, war nur eine akademische Übung, um zu zeigen, wie temperamentvoll der MySQL Query Optimizer sein kann, und um Handlungsoptionen vorzuschlagen.
RolandoMySQLDBA
1
Ich habe diesen und andere Beiträge gelesen und wieder gelesen, und ich kann nur zustimmen, dass dies mit der Bestellung von Innodb auf dem Primärschlüssel zusammenhängt, da wir alle auswählen (und keinen übergeordneten Index). Ich bin überrascht, dass diese InnoDB-spezifische Seltsamkeit auf der Seite des ORDER BY-Optimierungsdokuments nicht erwähnt wird. Wie auch immer, +1 für Rolando
Derek Downey
1
@eggyal Dies wurde diese Woche geschrieben. Beachten Sie, dass derselbe EXPLAIN-Plan und der vollständige Scan länger dauern, wenn der Datensatz nicht in den Speicher passt.
Derek Downey
0

Angepasst (mit Genehmigung) von Denis 'Antwort auf eine andere Frage zu SO:

Da alle Datensätze (oder fast alle) von der Abfrage abgerufen werden, ist es normalerweise besser, wenn überhaupt kein Index vorhanden ist. Der Grund dafür ist, dass es tatsächlich etwas kostet, einen Index zu lesen.

Wenn Sie die gesamte Tabelle durchsuchen, ist es möglicherweise der günstigste Plan, die Tabelle nacheinander zu lesen und die Zeilen im Speicher zu sortieren. Wenn Sie nur wenige Zeilen benötigen und die meisten mit der where-Klausel übereinstimmen, reicht es aus, den kleinsten Index zu verwenden.

Um zu verstehen, warum, stellen Sie sich die betroffenen Datenträger-E / A vor.

Angenommen, Sie möchten die gesamte Tabelle ohne Index. Dazu lesen Sie data_page1, data_page2, data_page3 usw. und besuchen die verschiedenen betroffenen Plattenseiten, bis Sie das Ende der Tabelle erreichen. Sie sortieren dann und kehren zurück.

Wenn Sie die Top-5-Zeilen ohne Index haben möchten, lesen Sie die gesamte Tabelle nacheinander wie zuvor, während Sie die Top-5-Zeilen heapsortieren. Zugegeben, das ist eine Menge Lesen und Sortieren für eine Handvoll Zeilen.

Angenommen, Sie möchten jetzt die gesamte Tabelle mit einem Index versehen. Dazu lesen Sie nacheinander index_page1, index_page2 usw. Dies führt dann dazu, dass Sie beispielsweise data_page3, data_page1, data_page3, data_page2 usw. in einer völlig zufälligen Reihenfolge aufrufen (die Reihenfolge, nach der die sortierten Zeilen in den Daten angezeigt werden). Das IO macht es billiger, nur die ganze Unordnung nacheinander zu lesen und den Grabbag im Speicher zu sortieren.

Wenn Sie dagegen nur die obersten 5 Zeilen einer indizierten Tabelle verwenden möchten, ist die Verwendung des Index die richtige Strategie. Im schlimmsten Fall laden Sie 5 Datenseiten in den Speicher und fahren fort.

Ein guter SQL-Abfrageplaner entscheidet übrigens anhand der Fragmentierung Ihrer Daten, ob ein Index verwendet wird oder nicht. Wenn das Abrufen von Zeilen in der angegebenen Reihenfolge das Hin- und Herzoomen in der Tabelle bedeutet, kann ein guter Planer entscheiden, dass es sich nicht lohnt, den Index zu verwenden. Wenn dagegen die Tabelle mit demselben Index geclustert wird, ist die Reihenfolge der Zeilen garantiert, was die Wahrscheinlichkeit erhöht, dass sie verwendet wird.

Wenn Sie jedoch dieselbe Abfrage mit einer anderen Tabelle verknüpfen und diese andere Tabelle eine äußerst selektive where-Klausel enthält, die einen kleinen Index verwenden kann, könnte der Planer entscheiden, dass es tatsächlich besser ist, z. B. alle IDs von Zeilen abzurufen, die mit foohash markiert sind Verbinden Sie die Tabellen und sortieren Sie sie im Speicher.

eggyal
quelle