Czy indeks musi obejmować wszystkie wybrane kolumny, aby mógł być użyty do ORDER BY?

15

W SO ktoś ostatnio zapytał: Dlaczego ORDER BY nie korzysta z indeksu?

Sytuacja dotyczyła prostej tabeli InnoDB w MySQL zawierającej trzy kolumny i 10 000 wierszy. Jedna z kolumn, liczba całkowita, została zindeksowana, a OP próbował odzyskać całą swoją tabelę posortowaną według tej kolumny:

SELECT * FROM person ORDER BY age

Dołączył EXPLAINwyniki pokazujące, że to zapytanie zostało rozwiązane za pomocą filesort(zamiast indeksu) i zapytał, dlaczego tak jest.

Pomimo podpowiedzi FORCE INDEX FOR ORDER BY (age) powodującej użycie indeksu , ktoś odpowiedział (z dodatkowymi komentarzami / opiniami innych), że indeks służy do sortowania tylko wtedy, gdy wszystkie wybrane kolumny są odczytywane z indeksu (tj. Jak zwykle wskazuje to Using indexw Extrakolumnie o EXPLAINwyjściu). Wyjaśniono później, że przejście przez indeks, a następnie pobranie kolumn z tabeli powoduje losowe operacje we / wy, które MySQL uważa za droższe niż a filesort.

Wydaje się, że jest to sprzeczne z ręcznym rozdziałem dotyczącym ORDER BYoptymalizacji , który nie tylko daje wrażenie, że zadowalanie ORDER BYindeksem jest lepsze niż przeprowadzanie dodatkowego sortowania (w rzeczywistości filesortjest to kombinacja szybkiego sortowania i scalania, a zatem musi mieć dolną granicę ; podczas przechodzenia przez indeks w kolejności i szukania tabeli powinno być - więc ma to doskonały sens), ale pomija również wspomnianą rzekomą „optymalizację”, jednocześnie stwierdzając:Ω(nlog n)O(n)

Następujące zapytania używają indeksu do rozwiązania ORDER BYczęści:

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

Moim zdaniem tak właśnie jest w tej sytuacji (jednak indeks nie był używany bez wyraźnej wskazówki).

Moje pytania to:

  • Czy rzeczywiście konieczne jest zaindeksowanie wszystkich wybranych kolumn, aby MySQL mógł użyć indeksu?

    • Jeśli tak, to gdzie jest to udokumentowane (jeśli w ogóle)?

    • Jeśli nie, co tu się działo?

mysql index innodb order-by Eggyal
źródło

Odpowiedzi:

14

Czy rzeczywiście konieczne jest zaindeksowanie wszystkich wybranych kolumn, aby MySQL mógł użyć indeksu?

To jest załadowane pytanie, ponieważ istnieją czynniki, które określają, czy warto korzystać z indeksu.

CZYNNIK 1

Jaka jest kluczowa populacja dla danego indeksu? Innymi słowy, jaka jest liczność (odrębna liczba) wszystkich krotek zarejestrowanych w indeksie?

CZYNNIK 2

Jakiego silnika pamięci używasz? Czy wszystkie potrzebne kolumny są dostępne z indeksu?

CO DALEJ ???

Weźmy prosty przykład: tabela, która zawiera dwie wartości (mężczyzna i kobieta)

Utwórzmy taką tabelę z testem użycia indeksu

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>

Analiza dla InnoDB

Gdy dane zostały załadowane jako InnoDB, należy pamiętać, że wszystkie cztery EXPLAINplany korzystały z genderindeksu. Trzeci i czwarty EXPLAINplan wykorzystywały genderindeks, mimo że żądane dane były id. Dlaczego? Ponieważ idznajduje się w nim, PRIMARY KEYa wszystkie indeksy wtórne mają wskaźniki odniesienia z powrotem do PRIMARY KEY(za pośrednictwem ind_klust_genu ).

Analiza dla MyISAM

Gdy dane zostały załadowane jako MyISAM, pamiętaj, że pierwsze trzy EXPLAINplany korzystały z genderindeksu. W czwartym EXPLAINplanie Optymalizator zapytań postanowił w ogóle nie używać indeksu. Zamiast tego wybrał pełny skan tabeli. Dlaczego?

Niezależnie od DBMS, Optymalizatory Zapytań działają na bardzo prostej zasadzie: jeśli indeks jest sprawdzany jako kandydat do użycia w celu przeprowadzenia wyszukiwania, a Optymalizator Zapytań oblicza, że ​​musi on wyszukać więcej niż 5% całkowitej liczby wiersze w tabeli:

  • pełne skanowanie indeksu jest wykonywane, jeśli wszystkie potrzebne kolumny do pobrania znajdują się w wybranym indeksie
  • w przeciwnym razie pełny skan tabeli

WNIOSEK

Jeśli nie masz odpowiednich indeksów pokrycia lub jeśli kluczowa populacja dla dowolnej krotki wynosi więcej niż 5% tabeli, musi się zdarzyć sześć rzeczy:

  1. Przekonaj się, że musisz profilować zapytania
  2. Znajdź wszystko WHERE, GROUP BYi porządek BY` klauzule z tych zapytań
  3. Sformułuj indeksy w tej kolejności
    • WHERE kolumny klauzul o wartościach statycznych
    • GROUP BY kolumny
    • ORDER BY kolumny
  4. Unikaj pełnego skanowania tabeli (zapytania pozbawione sensownej WHEREklauzuli)
  5. Unikaj populacji złych kluczy (lub przynajmniej buforuj te populacje złych kluczy)
  6. Wybierz najlepszy silnik pamięci MySQL ( InnoDB lub MyISAM ) dla tabel

W przeszłości pisałem o tej ogólnej zasadzie 5%:

AKTUALIZACJA 14.11.2012 13:05 EDT

Spojrzałem na twoje pytanie i na oryginalny post SO . Potem pomyślałem o mojej Analysis for InnoDBwcześniej wspomnianej. To pokrywa się ze personstołem. Dlaczego?

Dla obu tabel mfiperson

  • Silnik pamięci to InnoDB
  • Klucz podstawowy to id
  • Dostęp do tabeli odbywa się poprzez indeks wtórny
  • Gdyby tabelą był MyISAM, zobaczylibyśmy zupełnie inny EXPLAINplan

Teraz spojrzeć na zapytania z pytaniem SO: select * from person order by age\G. Ponieważ nie ma WHEREklauzuli, wyraźnie zażądałeś pełnego skanowania tabeli . Domyślna kolejność sortowania tabeli byłaby według id(KLUCZ PODSTAWOWY) ze względu na jej auto_increment, a gen_clust_index (aka Clustered Index) jest uporządkowany według wewnętrznego rowid . Po zamówieniu według indeksu należy pamiętać, że indeksy wtórne InnoDB mają identyfikator rowid dołączony do każdej pozycji indeksu. To powoduje wewnętrzną potrzebę pełnego dostępu do wiersza za każdym razem.

Konfigurowanie ORDER BYtabeli InnoDB może być dość zniechęcającym zadaniem, jeśli zignorujesz te fakty dotyczące organizacji indeksów InnoDB.

Wracając do tego zapytania SO, ponieważ wyraźnie zażądałeś pełnego skanowania tabeli , IMHO Optymalizator zapytań MySQL zrobił właściwą czynność (lub przynajmniej wybrał ścieżkę najmniejszego oporu). Jeśli chodzi o InnoDB i kwerendę SO, o wiele łatwiej jest wykonać pełne skanowanie tabeli, a następnie niektóre, filesortzamiast wykonywać pełne skanowanie indeksu i wyszukiwanie wierszy za pośrednictwem gen_clust_index dla każdej pozycji indeksu wtórnego.

Nie jestem zwolennikiem korzystania ze Wskazówek dotyczących indeksu, ponieważ ignoruje on plan WYJAŚNIENIA. Niezależnie od tego, jeśli naprawdę znasz swoje dane lepiej niż InnoDB, będziesz musiał skorzystać ze wskazówek indeksu, szczególnie w przypadku zapytań, które nie zawierają żadnych WHEREklauzul.

AKTUALIZACJA 14.11.2012 14:21 EDT

Zgodnie z książką Understanding MySQL Internals

wprowadź opis zdjęcia tutaj

Page 202 Ustęp 7 mówi, co następuje:

Dane są przechowywane w specjalnej strukturze zwanej indeksem klastrowym , który jest drzewem B z kluczem podstawowym działającym jako wartość klucza oraz rzeczywistym rekordem (a nie wskaźnikiem) w części danych. Dlatego każda tabela InnoDB musi mieć klucz podstawowy. Jeśli nie zostanie dostarczony, zostanie dodana specjalna kolumna identyfikatora wiersza, która zwykle nie jest widoczna dla użytkownika, aby działała jako klucz podstawowy. Klucz pomocniczy przechowuje wartość klucza podstawowego, który identyfikuje rekord. Kod B-drzewa można znaleźć w innobase / btr / btr0btr.c .

Właśnie dlatego powiedziałem wcześniej: o wiele łatwiej jest wykonać pełne skanowanie tabeli, a następnie niektóre sortowanie plików, niż pełne skanowanie indeksu i wyszukiwanie wierszy za pomocą gen_clust_index dla każdej pozycji indeksu wtórnego . InnoDB za każdym razem przeprowadzi podwójne wyszukiwanie indeksu . Brzmi to trochę brutalnie, ale to tylko fakty. Ponownie weź pod uwagę brak WHEREklauzuli. To samo w sobie jest wskazówką dla MySQL Query Optimizer, aby wykonać pełne skanowanie tabeli.

RolandoMySQLDBA
źródło
Rolando, dziękuję za tak dokładną i szczegółową odpowiedź. Jednak wydaje się, że nie ma to znaczenia przy wyborze indeksów FOR ORDER BY(co jest szczególnym przypadkiem w tym pytaniu). Pytanie zawierało stwierdzenie, że w tym przypadku był to silnik pamięci masowej InnoDB(a oryginalne pytanie SO pokazuje, że wiersze 10 000 są dość równomiernie rozmieszczone na 8 elementach, tutaj również nie powinna być problemem liczność). Niestety nie sądzę, że to odpowiada na pytanie.
eggyal
Jest to interesujące, ponieważ pierwsza część była również moim pierwszym instynktem (nie miała dobrej liczności, więc mysql zdecydował się na pełne skanowanie). Ale im więcej czytam, ta zasada nie wydawała się mieć zastosowania do optymalizacji przez optymalizację. Czy na pewno porządkuje według klucza podstawowego dla indeksów klastrowych innodb? Ten post wskazuje, że klucz główny został dodany na końcu, więc czy sortowanie nadal nie byłoby w wyraźnych kolumnach indeksu? Krótko mówiąc, wciąż jestem zakłopotany!
Derek Downey
1
filesortSelekcji podejmowane przez optymalizator kwerendy z jednego prostego powodu: Brakuje foreknowledge danych, które masz. Jeśli wybór użycia wskazówek dotyczących indeksu (na podstawie problemu nr 2) zapewnia satysfakcjonujący czas działania, to idź za tym. Odpowiedź, którą podałem, była tylko ćwiczeniem akademickim, które miało pokazać, jak temperamentny może być Optymalizator zapytań MySQL, a także sugerować kierunki działania.
RolandoMySQLDBA
1
Przeczytałem i ponownie przeczytałem ten i inne posty i mogę tylko zgodzić się, że ma to związek z porządkowaniem innodb na kluczu podstawowym, ponieważ wybieramy wszystko (a nie indeks obejmujący). Dziwi mnie, że nie ma wzmianki o tej dziwności specyficznej dla InnoDB na stronie dokumentu optymalizacji ORDER BY. W każdym razie +1 do Rolando
Derek Downey
1
@eggyal Ten został napisany w tym tygodniu. Zwróć uwagę na ten sam plan EXPLAIN, a pełne skanowanie trwa dłużej, jeśli zestaw danych nie mieści się w pamięci.
Derek Downey
0

Dostosowane (za zgodą) z odpowiedzi Denisa na inne pytanie dotyczące SO:

Ponieważ wszystkie rekordy (lub prawie wszystkie) zostaną pobrane przez zapytanie, zwykle lepiej jest bez żadnego indeksu. Powodem tego jest fakt, że odczyt indeksu kosztuje coś.

Kiedy idziesz do całego stołu, sekwencyjne czytanie tabeli i sortowanie jej wierszy w pamięci może być najtańszym planem. Jeśli potrzebujesz tylko kilku wierszy, a większość dopasuje klauzulę where, wybranie najmniejszego indeksu załatwi sprawę.

Aby zrozumieć, dlaczego, wyobraź sobie dysk I / O, którego to dotyczy.

Załóżmy, że chcesz mieć całą tabelę bez indeksu. Aby to zrobić, czytaj dane strona_1, strona_ danych2, strona_ danych3 itd., Odwiedzając kolejno różne strony dysku, aż dojdziesz do końca tabeli. Następnie sortuj i wróć.

Jeśli chcesz uzyskać 5 pierwszych wierszy bez indeksu, sekwencyjnie odczytujesz całą tabelę, jak poprzednio, podczas sortowania sterty pierwszych 5 wierszy. Trzeba przyznać, że to dużo czytania i sortowania dla kilku wierszy.

Załóżmy teraz, że chcesz mieć całą tabelę z indeksem. Aby to zrobić, sekwencyjnie czytasz stronę indeksową, stronę indeksową 2 itd. To następnie prowadzi do odwiedzenia, powiedzmy, data_page3, następnie data_page1, następnie data_page3, następnie data_page2 itd., W całkowicie losowej kolejności (w kolejności, w której posortowane wiersze pojawiają się w danych). Zaangażowane we / wy sprawia, że ​​taniej jest po prostu sekwencyjnie czytać cały bałagan i sortować torbę w pamięci.

Jeśli chcesz tylko 5 górnych wierszy zindeksowanej tabeli, w przeciwieństwie do tego użycie indeksu staje się właściwą strategią. W najgorszym przypadku ładujesz 5 stron danych do pamięci i przechodzisz dalej.

Dobry planista zapytań SQL, btw, podejmie decyzję, czy użyć indeksu, czy nie, na podstawie stopnia fragmentacji danych. Jeśli pobieranie wierszy w kolejności oznacza powiększanie w tę iz powrotem po stole, dobry planista może zdecydować, że nie warto używać indeksu. W przeciwieństwie do tego, jeśli tabela jest grupowana przy użyciu tego samego indeksu, gwarantuje się, że wiersze są w porządku, co zwiększa prawdopodobieństwo, że zostanie wykorzystana.

Ale jeśli połączysz to samo zapytanie z inną tabelą, a ta inna tabela ma bardzo selektywną klauzulę where, która może używać małego indeksu, planista może zdecydować, że w rzeczywistości lepiej, np. Pobrać wszystkie identyfikatory wierszy oznaczonych jako foohash połącz tabele i posortuj je w pamięci.

Eggyal
źródło