Dlaczego MySQL nie ma indeksów skrótu w MyISAM lub InnoDB?

Mam aplikację, która wybierze tylko na zasadzie równości, i uważam, że powinienem użyć indeksu skrótu zamiast indeksu btree. Ku mojemu przerażeniu indeksy skrótów nie są obsługiwane w MyISAM ani InnoDB. O co chodzi?

Wiele baz danych nie obsługują indeksów opartych hash w ogóle .

Aby tablica skrótów była wydajna, musisz znać liczbę wierszy, które prawdopodobnie będą obecne, w przeciwnym razie podstawowa tabela skrótów będzie o wiele za duża (wiele pustych wpisów, marnowanie miejsca i potencjalnie We / Wy dysku) lub zbyt mała, co oznacza, że często stosuje się pośrednie (być może wiele poziomów pośrednich, a nawet gorzej, jeśli implementacja skrótu jest jednopoziomowa, możesz w końcu przeprowadzić wyszukiwanie liniowe na sporej liczbie rekordów), w którym to momencie rzeczy prawdopodobnie nie są bardziej wydajne niż oparte na drzewie indeksuj mimo to.

Aby być ogólnie użytecznym (tj. Zwykle lepszym niż alternatywa), indeks musi być przebudowywany od czasu do czasu, gdy dane rosną (i kurczą się), co może powodować znaczne przejściowe obciążenie. Zwykle jest to w porządku w przypadku tabel opartych na pamięci, ponieważ przebudowa prawdopodobnie będzie dość szybka (ponieważ dane zawsze będą w pamięci RAM i prawdopodobnie nie będą ogromne), ale odbudowanie dużego indeksu na dysku jest bardzo ciężka operacja (a IIRC mySQL nie obsługuje przebudowywania indeksu na żywo, więc blokuje tabelę podczas operacji).

W związku z tym indeksy skrótów są używane w tabelach pamięci, ponieważ są one generalnie lepiej wydajne, ale tabele dyskowe nie obsługują ich, ponieważ mogą być szkodliwe dla wydajności, a nie premii. Nie ma nic do indeksów hash przestać być udostępniane na dysku tabel opartych oczywiście, nie ma wątpliwości, niektóre bazy danych zrobić obsługuje funkcji, ale prawdopodobnie nie są one realizowane w ISAM / tabel InnoDB jako opiekunów nie uznają wartości funkcji dodawania (jako dodatkowy kod do pisania i utrzymywania nie jest wart korzyści w tych nielicznych okolicznościach, które stanowią znaczącą różnicę). Być może, jeśli zdecydowanie się nie zgadzasz, możesz z nimi porozmawiać i uzasadnić wdrożenie tej funkcji.

Jeśli indeksujesz duże ciągi, wdrożenie własnego pseudo-skrótu (przez przechowywanie skrótu wartości oraz wartości rzeczywistej i indeksowanie z kolumną) może działać, ale jest to zdecydowanie bardziej wydajne w przypadku dużych ciągów (gdzie obliczenie wartości skrótu i ​​przeszukanie indeksu drzewa za pomocą tej wartości zawsze będzie prawdopodobnie szybsze niż po prostu przeszukanie indeksu drzewa przy użyciu większych wartości do porównania, a zastosowana dodatkowa pamięć nie będzie znacząca), więc wykonaj analizę wydajności przed wdrożeniem to w produkcji.

W pokrewnej notatce dyskusja na temat typów indeksów z dokumentów PostgreSQL może okazać się interesująca. Nie jest już obecny w najnowszych wersjach dokumentów (ze względu na kolejne optymalizacje, biorę to), ale wynos może być podobny do MySQL (i powód, dla którego indeksy skrótów są używane tylko dla tabel sterty):

http://www.postgresql.org/docs/8.1/static/indexes-types.html

Uwaga: Testy wykazały, że indeksy mieszające PostgreSQL nie działają lepiej niż indeksy B-drzewa, a rozmiar indeksu i czas kompilacji dla indeksów mieszających są znacznie gorsze. Ponadto operacje indeksowania skrótów nie są obecnie rejestrowane w WAL, więc indeksy skrótów mogą wymagać odbudowania za pomocą REINDEX po awarii bazy danych. Z tych powodów używanie indeksu skrótu jest obecnie odradzane. Podobnie, indeksy R-drzewa nie wydają się mieć żadnych korzyści wydajnościowych w porównaniu do równoważnych operacji indeksów GiST. Podobnie jak indeksy skrótów, nie są one rejestrowane w WAL i mogą wymagać ponownego indeksowania po awarii bazy danych. Podczas gdy problemy z indeksami skrótu mogą zostać ostatecznie rozwiązane, prawdopodobne jest, że typ indeksu R-drzewa zostanie wycofany w przyszłej wersji. Zachęcamy użytkowników do migracji aplikacji korzystających z indeksów R-drzewa do indeksów GiST.

Ponownie, jest to (przestarzała wersja) specyficzna dla PostgreSQL, ale powinna sugerować, że „naturalny” typ indeksu niekoniecznie zapewnia optymalną wydajność.

Oto coś interesującego:

Zgodnie z książką MySQL 5.0 Certification Study Guide , strona 433, sekcja 29.5.1

Mechanizm MEMORY używa domyślnie algorytmu indeksowania HASH.

Dla śmiechu próbowałem utworzyć tabelę InnoDB i tabelę MyISAM z kluczem podstawowym za pomocą HASH w MySQL 5.5.12

mysql> use test
Database changed
mysql> create table rolando (num int not null, primary key (num) using hash);
Query OK, 0 rows affected (0.11 sec)

mysql> show create table rolando\G
*************************** 1. row ***************************
       Table: rolando
Create Table: CREATE TABLE `rolando` (
  `num` int(11) NOT NULL,
  PRIMARY KEY (`num`) USING HASH
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

mysql> create table rolando2 (num int not null, primary key (num) using hash) engine=MyISAM;
Query OK, 0 rows affected (0.05 sec)

mysql> show create table rolando2\G
*************************** 1. row ***************************
       Table: rolando2
Create Table: CREATE TABLE `rolando2` (
  `num` int(11) NOT NULL,
  PRIMARY KEY (`num`) USING HASH
) ENGINE=MyISAM DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

MySQL nie narzekał.

AKTUALIZACJA

Złe wieści !!! Użyłem SHOW INDEXES From. Mówi, że indeks to BTREE.

CREATE INDEX składnia MySQL Strona stwierdza, że tylko pamięć i silniki przechowywania NDB mogą pomieścić INDEX hash.

mysql> show indexes from rolando;
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table   | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| rolando |          0 | PRIMARY  |            1 | num         | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

mysql> show indexes from rolando2;
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| rolando2 |          0 | PRIMARY  |            1 | num         | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

mysql> create table rolando3 (num int not null, primary key (num)) ENGINE=MEMORY;
Query OK, 0 rows affected (0.03 sec)

mysql> show create table rolando3\G
*************************** 1. row ***************************
       Table: rolando3
Create Table: CREATE TABLE `rolando3` (
  `num` int(11) NOT NULL,
  PRIMARY KEY (`num`)
) ENGINE=MEMORY DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

mysql> show indexes from rolando3;
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| rolando3 |          0 | PRIMARY  |            1 | num         | NULL      |           0 |     NULL | NULL   |      | HASH       |         |               |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

Niektóre osoby zasugerowały zastosowanie idei ze stron 102-105 książki „ High Performance MySQL: Optymalizacje, kopie zapasowe, replikacja i inne ” w celu emulacji algorytmu skrótu.

Strona 105 zawiera ten szybki i brudny algorytm, który lubię:

SELECT CONV(RIGHT(MD5('whatever value you want'),16),16,10) AS HASH64;

Utwórz kolumnę do tego w dowolnej tabeli i zindeksuj tę wartość.

Spróbuj !!!

BTree nie jest dużo wolniejszy niż Hash dla wyszukiwania w jednym wierszu. Ponieważ BTree zapewnia bardzo wydajne zapytania o zasięg, po co zawracać sobie głowę czymkolwiek innym niż BTree.

MySQL bardzo dobrze buforuje bloki BTree, więc zapytanie oparte na BTree rzadko musi wykonywać operacje We / Wy, które są największymi konsumentami czasu w każdym zapytaniu.