Di SO, seseorang baru-baru ini bertanya. Mengapa ORDER OLEH menggunakan indeks?

Situasi ini melibatkan tabel InnoDB sederhana di MySQL yang terdiri dari tiga kolom dan baris 10rb. Salah satu kolom, bilangan bulat, diindeks — dan OP berusaha mengambil seluruh tabelnya yang diurutkan pada kolom itu:

SELECT * FROM person ORDER BY age

Dia melampirkan EXPLAINoutput yang menunjukkan bahwa kueri ini diselesaikan dengan filesort(bukan indeks) dan bertanya mengapa itu terjadi.

Terlepas dari petunjuk yang FORCE INDEX FOR ORDER BY (age) menyebabkan indeks digunakan , seseorang menjawab (dengan komentar / upvotes pendukung dari orang lain) bahwa indeks hanya digunakan untuk mengurutkan ketika kolom yang dipilih semua dibaca dari indeks (yaitu seperti yang biasanya ditunjukkan oleh Using indexdalam Extrakolom dari EXPLAINoutput). Penjelasan kemudian diberikan bahwa melintasi indeks dan kemudian mengambil kolom dari tabel menghasilkan I / O acak, yang menurut MySQL lebih mahal daripada a filesort.

Ini tampaknya terbang di hadapan bab manual tentang ORDER BYPengoptimalan , yang tidak hanya menyampaikan kesan kuat bahwa memuaskan ORDER BYdari indeks lebih disukai daripada melakukan pengurutan tambahan (memang, filesortmerupakan kombinasi antara quicksort dan mergesort dan karenanya harus memiliki batas yang lebih rendah dari ; sementara berjalan melalui indeks dalam urutan dan mencari ke meja seharusnya - jadi ini masuk akal), tetapi juga mengabaikan menyebutkan dugaan "optimasi" ini sementara juga menyatakan:Ω(nlog n)O(n)

Kueri berikut menggunakan indeks untuk menyelesaikan ORDER BYbagian:

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

Untuk bacaan saya, itulah tepatnya kasus dalam situasi ini (namun indeks tidak digunakan tanpa petunjuk eksplisit).

Pertanyaan saya adalah:

• Apakah memang perlu untuk semua kolom yang dipilih diindeks agar MySQL dapat memilih untuk menggunakan indeks?

  • Jika demikian, di mana ini didokumentasikan (jika sama sekali)?

  • Jika tidak, apa yang terjadi di sini?

Apakah memang perlu untuk semua kolom yang dipilih diindeks agar MySQL dapat memilih untuk menggunakan indeks?

Ini adalah pertanyaan yang dimuat karena ada faktor yang menentukan apakah indeks layak digunakan.

FAKTOR # 1

Untuk indeks apa pun, berapa populasi kunci? Dengan kata lain, apa kardinalitas (jumlah berbeda) dari semua tupel yang dicatat dalam indeks?

FAKTOR # 2

Mesin penyimpanan apa yang Anda gunakan? Apakah semua kolom yang diperlukan dapat diakses dari indeks?

APA BERIKUTNYA ???

Mari kita ambil contoh sederhana: tabel yang memuat dua nilai (Pria dan Wanita)

Mari buat tabel seperti itu dengan tes untuk penggunaan indeks

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>

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

Analisis untuk InnoDB

Ketika data dimuat sebagai InnoDB, harap dicatat bahwa keempat EXPLAINpaket menggunakan genderindeks. Rencana ketiga dan keempat EXPLAINmenggunakan genderindeks meskipun data yang diminta id. Mengapa? Karena idada dalam PRIMARY KEYdan semua indeks sekunder memiliki pointer referensi kembali ke PRIMARY KEY(melalui gen_clust_index ).

Analisis untuk MyISAM

Ketika data dimuat sebagai MyISAM, harap dicatat bahwa tiga EXPLAINpaket pertama menggunakan genderindeks. Dalam paket keempat EXPLAIN, Pengoptimal Kueri memutuskan untuk tidak menggunakan indeks sama sekali. Itu memilih untuk pemindaian tabel penuh sebagai gantinya. Mengapa?

Terlepas dari DBMS, Pengoptimal Kueri beroperasi pada aturan praktis yang sangat sederhana: Jika indeks sedang disaring sebagai kandidat yang akan digunakan untuk melakukan pencarian dan Pengoptimal Kueri menghitung bahwa ia harus mencari lebih dari 5% dari total jumlah baris dalam tabel:

• pemindaian indeks lengkap dilakukan jika semua kolom yang diperlukan untuk pengambilan berada dalam indeks yang dipilih
• pemindaian tabel lengkap sebaliknya

KESIMPULAN

Jika Anda tidak memiliki indeks cakupan yang tepat, atau jika populasi kunci untuk setiap tuple yang diberikan lebih dari 5% dari tabel, enam hal harus terjadi:

1. Datanglah ke kesadaran bahwa Anda harus membuat profil kueri
2. Temukan semua WHERE,, GROUP BYdan klausa ORDER BY` dari Query tersebut
3. Formulasikan indeks dalam urutan ini
   • WHERE klausa kolom dengan nilai statis
   • GROUP BY kolom
   • ORDER BY kolom
4. Hindari Pemindaian Tabel Penuh (Kueri yang tidak memiliki WHEREklausa yang masuk akal )
5. Hindari Populasi Key Buruk (atau setidaknya cache populasi Key Buruk itu)
6. Tentukan Mesin Penyimpanan MySQL terbaik ( InnoDB atau MyISAM ) untuk Tabel

Saya telah menulis tentang aturan praktis 5% ini di masa lalu:

• May 07, 2012: MySQL EXPLAIN tidak menampilkan 'gunakan indeks' untuk FULLTEXT
• Mar 22, 2012: Mengapa MySQL memilih paket eksekusi ini?
• Mar 09, 2012: indeks tidak digunakan
• Jan 18, 2012: Variabel status MySQL Handler_read_rnd_next tumbuh banyak
• Dec 27, 2011: MySQL - cara tercepat untuk mengubah tabel untuk InnoDB
• Jul 29, 2011: Optimalisasi Kueri MySQL: Indeks dan Pagination
• Jul 12, 2011: Permintaan MySQL sangat lambat saat mengubah satu bidang WHERE meskipun tidak ada indeks / kunci

UPDATE 2012-11-14 13:05 EDT

Saya melihat kembali pertanyaan Anda dan pada posting SO asli . Kemudian, saya memikirkan tentang yang saya Analysis for InnoDBsebutkan sebelumnya. Itu bertepatan dengan personmeja. Mengapa?

Untuk tabel mfdanperson

• Mesin Penyimpanan adalah InnoDB
• Kunci Utama adalah id
• Akses tabel adalah dengan indeks sekunder
• Jika tabel adalah MyISAM, kita akan melihat EXPLAINrencana yang sama sekali berbeda

Sekarang, melihat query dari pertanyaan SO: select * from person order by age\G. Karena tidak ada WHEREklausa, Anda secara eksplisit menuntut pemindaian tabel penuh . Urutan sortir default tabel adalah oleh id(PRIMARY KEY) karena auto_increment dan gen_clust_index (alias Clustered Index) dipesan oleh rowid internal . Ketika Anda memesan oleh indeks, perlu diingat bahwa indeks sekunder InnoDB memiliki rowid yang melekat pada setiap entri indeks. Ini menghasilkan kebutuhan internal untuk akses baris penuh setiap kali.

Menyiapkan ORDER BYtabel InnoDB bisa menjadi tugas yang agak menakutkan jika Anda mengabaikan fakta-fakta ini tentang bagaimana indeks InnoDB diatur.

Kembali ke permintaan SO, karena Anda secara eksplisit menuntut pemindaian tabel penuh , IMHO MySQL Query Optimizer melakukan hal yang benar (atau setidaknya, memilih jalur yang paling tidak resistan). Ketika datang ke InnoDB dan permintaan SO, jauh lebih mudah untuk melakukan pemindaian tabel penuh dan kemudian beberapa filesortdaripada melakukan pemindaian indeks penuh dan pencarian baris melalui gen_clust_index untuk setiap entri indeks sekunder.

Saya bukan penganjur menggunakan Petunjuk Indeks karena mengabaikan rencana MENJELASKAN. Meskipun demikian, jika Anda benar-benar mengetahui data Anda lebih baik daripada InnoDB, Anda harus beralih ke Petunjuk Indeks, terutama dengan kueri yang tidak memiliki WHEREklausa.

UPDATE 2012-11-14 14:21 EDT

Menurut buku Memahami MySQL Internal

Paragraf 7 mengatakan:

Data disimpan dalam struktur khusus yang disebut indeks berkerumun , yang merupakan pohon-B dengan kunci utama yang bertindak sebagai nilai kunci, dan catatan aktual (bukan penunjuk) di bagian data. Dengan demikian, setiap tabel InnoDB harus memiliki kunci utama. Jika tidak disediakan, kolom ID baris khusus yang biasanya tidak terlihat oleh pengguna ditambahkan untuk bertindak sebagai kunci utama. Kunci sekunder akan menyimpan nilai kunci utama yang mengidentifikasi catatan. Kode B-tree dapat ditemukan di innobase / btr / btr0btr.c .

Inilah sebabnya saya nyatakan sebelumnya: jauh lebih mudah untuk melakukan pemindaian tabel penuh dan kemudian beberapa filesort daripada melakukan pemindaian indeks penuh dan pencarian baris melalui gen_clust_index untuk setiap entri indeks sekunder . InnoDB akan melakukan pencarian indeks ganda setiap kali . Kedengarannya brutal, tapi itu faktanya. Sekali lagi, pertimbangkan kurangnya WHEREklausa. Ini, dengan sendirinya, adalah petunjuk untuk Pengoptimal Permintaan MySQL untuk melakukan pemindaian tabel penuh.

Diadaptasi (dengan izin) dari jawaban Denis untuk pertanyaan lain pada SO:

Karena semua catatan (atau hampir semua) akan diambil oleh kueri, biasanya Anda lebih baik tanpa indeks sama sekali. Alasan untuk ini adalah, sebenarnya biaya sesuatu untuk membaca indeks.

Saat Anda mencari seluruh tabel, membaca tabel secara berurutan dan menyortir barisnya dalam memori mungkin merupakan rencana termurah Anda. Jika Anda hanya perlu beberapa baris dan sebagian besar akan cocok dengan klausa di mana, pergi untuk indeks terkecil akan melakukan trik.

Untuk memahami alasannya, bayangkan disk I / O yang terlibat.

Misalkan Anda ingin seluruh tabel tanpa indeks. Untuk melakukan ini, Anda membaca data_page1, data_page2, data_page3, dll., Mengunjungi berbagai halaman disk yang terlibat secara berurutan, hingga Anda mencapai akhir tabel. Anda kemudian mengurutkan dan kembali.

Jika Anda menginginkan 5 baris teratas tanpa indeks, Anda akan secara berurutan membaca seluruh tabel seperti sebelumnya, sambil menumpuk-mengurutkan 5 baris teratas. Memang, itu banyak membaca dan menyortir untuk beberapa baris.

Misalkan, sekarang, Anda ingin seluruh tabel dengan indeks. Untuk melakukan ini, Anda membaca index_page1, index_page2, dll, secara berurutan. Ini kemudian mengarahkan Anda untuk mengunjungi, katakanlah, data_page3, lalu data_page1, lalu data_page3 lagi, lalu data_page2, dll., Dalam urutan yang benar-benar acak (dengan mana baris yang diurutkan muncul dalam data). IO yang terlibat membuatnya lebih murah untuk hanya membaca seluruh kekacauan secara berurutan dan menyortir tas pencuri dalam memori.

Jika Anda hanya menginginkan 5 baris teratas dari tabel yang diindeks, sebaliknya, menggunakan indeks menjadi strategi yang tepat. Dalam skenario terburuk, Anda memuat 5 halaman data dalam memori dan melanjutkan.

Perencana kueri SQL yang baik, btw, akan membuat keputusan apakah akan menggunakan indeks atau tidak berdasarkan seberapa terfragmentasinya data Anda. Jika mengambil baris secara berurutan berarti melakukan zoom bolak-balik melintasi tabel, perencana yang baik dapat memutuskan bahwa tidak layak menggunakan indeks. Sebaliknya, jika tabel dikelompokkan menggunakan indeks yang sama, barisnya dijamin berurutan, meningkatkan kemungkinan bahwa tabel tersebut akan digunakan.

Tapi kemudian, jika Anda bergabung dengan kueri yang sama dengan tabel lain dan bahwa tabel lain memiliki klausa yang sangat selektif di mana yang dapat menggunakan indeks kecil, perencana mungkin memutuskan itu sebenarnya lebih baik untuk, misalnya mengambil semua ID dari baris yang ditandai sebagai foo, hash bergabung dengan tabel, dan tumpukan mengurutkannya dalam memori.