it-swarm-eu.dev

Proč MySQL nemá indexy hash na MyISAM nebo InnoDB?

Mám aplikaci, která bude vybírat pouze pro rovnost, a zjistím, že bych měl použít hash index přes btree index. Hodně k mému zděšení nejsou hashové indexy na MyISAM nebo InnoDB podporovány. Co je s tím?

36
Alex

Mnoho databází nepodporuje indexy založené na hašování vůbec.

Aby byla hashovací tabulka efektivní, musíte znát počet řádků, které budou pravděpodobně přítomny, jinak bude základní hashovací tabulka příliš velká (mnoho prázdných položek, ztrácí místo a potenciálně IO disku) nebo příliš malý význam, který často se používá indirection (možná více úrovní indirection, nebo ještě horší, pokud je hash implementace jednostupňová, můžete nakonec provést lineární vyhledávání přes spravedlivý počet záznamů), ve kterém okamžiku věci pravděpodobně nebudou efektivnější než stromové index stejně.

Aby byl index obecně užitečný (tj. Obvykle lepší než alternativní), je třeba příležitostně znovu vytvořit index, protože data rostou (a zmenšují se), což by mohlo přidat významnou občasnou režii. U tabulek založených na paměti je to obvykle v pořádku, protože přestavba bude pravděpodobně velmi rychlá (protože data budou vždy v RAM a pravděpodobně nebude v žádném případě masivní), ale opětovné vytvoření velkého indexu na disku je velmi těžká operace (a IIRC mySQL nepodporuje živé obnovení indexů, takže během operace drží zámek tabulky).

Indexy hash se proto používají v tabulkách paměti, protože tam jsou obecně lepší výkony, ale tabulky založené na disku je nepodporují, protože by mohly být na úkor výkonu, nikoli bonusu. Neexistuje nic, co by zastavilo zpřístupnění indexů hash pro tabulky založené na disku, samozřejmě, některé databáze do tuto funkci podporují, ale pravděpodobně nejsou implementovány v tabulkách ISAM/InnoDB, protože správci neuvažují funkce, kterou stojí za to přidat (protože zvláštní kód, který se má psát a udržovat, nestojí za výhodu za těch málo okolností, že to přináší významný rozdíl). Možná, pokud silně nesouhlasíte, můžete s nimi mluvit a udělat dobrý důvod pro implementaci této funkce.

Pokud indexujete velké řetězce, může implementovat váš vlastní pseudo-hashový index (uložením hashe hodnoty i skutečné hodnoty a indexování, který má sloupec), ale to je rozhodně efektivnější pro velké řetězce (kde výpočet hašovací hodnoty a prohledávání indexu stromu pomocí této hodnoty je vždy pravděpodobně rychlejší než prosté prohledávání indexu stromu pomocí větších hodnot pro porovnání a použité další úložiště nebude významné), proto před implementací proveďte nějakou analýzu výkonu to ve výrobě.

16
David Spillett

Na související poznámku by vás mohla zajímat diskuse o typech indexů z dokumentů PostgreSQL. V posledních verzích dokumentů již není přítomen (vzhledem k následným optimalizacím, beru to), ale s sebou může být podobný pro MySQL (a důvod, proč se hash indexy používají pouze pro tabulky haldy):

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

Poznámka: Testování ukázalo, že indexy hash PostgreSQL nefungují lépe než indexy B-stromu, a velikost indexu a doba vytváření indexů hash je mnohem horší. Operace indexu hash navíc nejsou v současné době protokolovány pomocí protokolu WAL, takže po selhání databáze bude pravděpodobně nutné znovu vytvořit hash indexy pomocí REINDEX. Z těchto důvodů je použití hash indexu v současné době vyloučeno. Podobně se zdá, že indexy R-stromu nemají ve srovnání s ekvivalentními operacemi Gistových indexů žádné výhody výkonu. Stejně jako indexy hash, nejsou protokolovány pomocí protokolu WAL a mohou vyžadovat reindexování po selhání databáze. I když problémy s indexy hash mohou být nakonec vyřešeny, je pravděpodobné, že typ indexu R-tree bude v budoucí verzi vyřazen. Uživatelé se vyzývají, aby migrovali aplikace, které používají indexy R-stromu, na Gistovy indexy.

Opět je to (zastaralá verze) specifické pro PostgreSQL, ale mělo by naznačovat, že „přirozený“ typ indexu nemusí nutně přinést optimální výkon.

6

Zde je něco zajímavého:

Podle knihy MySQL 5.0 Guide Study Study Guide , Strana 433, Oddíl 29.5.1

Ve výchozím algoritmu indexování používá modul MEMORY HASH.

Pro smích jsem se pokusil vytvořit tabulku InnoDB a tabulku MyISAM s primárním klíčem pomocí HASH v 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 si nestěžoval.

AKTUALIZACE

Špatné zprávy !!! Použil jsem ZOBRAZIT INDEXY. Říká se, že index je BTREE.

CREATE INDEX syntaxe MySQL Page uvádí, že HASH INDEX mohou pojmout pouze paměťové moduly MEMORY a NDB.

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)

Někteří lidé navrhli následující myšlenk na stránkách 102–105 knihy „ Vysoce výkonná MySQL: optimalizace, zálohy, replikace a další " emulovat hashovací algoritmus.

Stránka 105 obsahuje tento rychlý a špinavý algoritmus, který se mi líbí:

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

Vytvořte sloupec v jakékoli tabulce a tuto hodnotu indexujte.

Pokusit se !!!

5
RolandoMySQLDBA

BTree není o moc pomalejší než Hash pro vyhledávání v jednom řádku. Protože BTree poskytuje velmi efektivní dotazy na rozsah, proč se obtěžovat s čímkoli jiným než BTree.

MySQL dělá velmi dobře práci s cachováním BTree bloků, takže dotaz založený na BTree málokdy musí udělat I/O, což je největší časový spotřebitel v každém dotazu.

2
Rick James