Pourquoi MySQL n'a-t-il pas d'indices de hachage sur MyISAM ou InnoDB?

35

J'ai une application qui ne sélectionnera que l'égalité, et je suppose que je devrais utiliser un index de hachage sur un index btree. À ma grande consternation, les indices de hachage ne sont pas pris en charge sur MyISAM ou InnoDB. Quoi de neuf avec ça?

RolandoMySQLDBA
la source
2
Mysql ne prend pas en charge les index basés sur des fonctions, des index bitmap, etc etc Juste parce qu'il est mysql ;-)
1
Je viens de penser que les index de hachage étaient si ... fondamentaux ... Je suppose qu'il existe une raison spécifique liée à la mise en œuvre.
1
@Alex: Je parie que la raison est "paresse" et "bureaucratie" mais attendons des réponses))
J'ai ajouté un bel algorithme HASH du High Performance MySQL Book à la fin de ma réponse.
RolandoMySQLDBA

Réponses:

16

De nombreuses bases de données ne prennent pas en charge les index à base de hachage du tout .

Pour qu’une table de hachage soit efficace, vous devez connaître le nombre de lignes susceptibles d’être présentes. Sinon, la table de hachage de base sera beaucoup trop volumineuse (nombreuses entrées vides, perte d’espace et risque potentiel d’E / S de disque) ou trop petite. L’indirection est souvent utilisée (éventuellement plusieurs niveaux d’indirection, ou pire si l’implémentation de hachage est à un niveau, vous pourriez éventuellement effectuer une recherche linéaire sur un nombre suffisant d’enregistrements). À ce stade, les choses ne sont probablement pas plus efficaces que l’arborescence. index de toute façon.

Donc, pour être généralement utile (c’est-à-dire généralement meilleur que l’alternative), l’indice doit être reconstitué de temps à autre à mesure que les données augmentent (et diminuent), ce qui pourrait ajouter une surcharge importante par intermittence. Cela convient généralement avec les tables basées sur la mémoire car la reconstruction sera probablement assez rapide (car les données seront toujours dans la RAM et ne seront probablement pas massives dans tous les cas), mais reconstruire un index volumineux sur le disque est une tâche ardue. opération très lourde (et IIRC mySQL ne supporte pas les reconstructions d'index en direct, donc maintient un verrou de table pendant l'opération).

Par conséquent, les index de hachage sont utilisés dans les tables de mémoire car ils sont généralement plus performants, mais les tables basées sur disque ne les prennent pas en charge car ils pourraient nuire aux performances et ne pas constituer un bonus. Bien sûr, certaines bases de données prennent en charge la fonctionnalité, mais elles ne sont probablement pas implémentées dans les tables ISAM / InnoDB, car les responsables ne considèrent pas cette fonctionnalité digne d'être ajoutée (car le code supplémentaire à écrire et à maintenir ne vaut pas l’avantage dans les quelques circonstances où il fait une différence significative). Peut-être que si vous êtes tout à fait en désaccord, vous pourriez leur parler et exposer de bons arguments en faveur de la mise en œuvre de la fonctionnalité.

Si vous indexez des chaînes volumineuses, alors implémentez votre propre index de pseudo-hachage (en stockant un hachage de la valeur ainsi que la valeur réelle, et l'indexation avec une colonne) peut fonctionner, mais cela est nettement plus efficace pour les grandes chaînes (où le calcul de la valeur de hachage et la recherche de l'index d'arborescence à l'aide de cette valeur sont toujours susceptibles d'être plus rapides que la recherche dans un index d'arborescence en utilisant les valeurs les plus élevées à des fins de comparaison, et la mémoire supplémentaire utilisée ne sera pas significative). ceci en production.

David Spillett
la source
Existe-t-il un moyen d'autoriser le re-hachage (reconstruction) côte à côte sans verrouiller toute la table?
Pacerier
@ Pacerier: pas que je sache avec MySQL (bien qu'ils aient pu ajouter la fonctionnalité depuis la dernière fois que je l'ai utilisée, consultez la documentation). Même lorsqu'un SGBD prend en charge la création / la reconstruction d'index en ligne, ce n'est pas l'option par défaut. Ce qui est verrouillé variera en fonction de: certaines personnes conserveront un verrou en écriture sur la table. D'autres transactions ne sont pas retardées si elles ne font que lire, certains DMBS retirent un verrou complet de la table. Si vous avez besoin de reconstruire en ligne, consultez la documentation de chaque SGBD avant de choisir lequel utiliser.
David Spillett
Généralement, la reconstruction n’est nécessaire que lorsque la longueur des données est doublée. Doivent-ils vraiment s'inquiéter de la longueur des données doublée chaque minute? (Normalement, cela arrive très rarement lorsque la base de données devient suffisamment grande pour que cela
pose
6

Sur une note connexe, vous pourriez trouver intéressante la discussion sur les types d’index de la documentation PostgreSQL. Il n'est plus présent dans les versions récentes de la documentation (à cause des optimisations ultérieures, je suppose), mais le résultat peut être similaire pour MySQL (et la raison pour laquelle les index de hachage ne sont utilisés que pour les tables de segment de mémoire):

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

Remarque: les tests ont montré que les index de hachage de PostgreSQL ne fonctionnaient pas mieux que les index B-tree, et que la taille de l'index et le temps de construction des index de hachage étaient bien pires. De plus, les opérations d'index de hachage ne sont pas actuellement enregistrées dans le journal WAL. Par conséquent, il peut être nécessaire de reconstruire les index de hachage avec REINDEX après un crash de la base de données. Pour ces raisons, l'utilisation d'index de hachage est actuellement déconseillée. De même, les index R-tree ne semblent présenter aucun avantage en termes de performances par rapport aux opérations équivalentes des index GiST. Comme les index de hachage, ils ne sont pas enregistrés dans le fichier WAL et peuvent nécessiter une réindexation après un blocage de la base de données. Bien que les problèmes avec les index de hachage puissent éventuellement être résolus, il est probable que le type d'index de l'arbre R sera supprimé dans une version ultérieure. Les utilisateurs sont encouragés à migrer les applications utilisant les index R-tree vers les index GiST.

Là encore, il s'agit d'une version (obsolète) de PostgreSQL, mais cela devrait indiquer que le type d'index "naturel" ne donnera pas nécessairement des performances optimales.

Denis de Bernardy
la source
5

Voici quelque chose d'intéressant:

Selon le livre MySQL 5.0 Certification Study Guide , page 433, Section 29.5.1

Le moteur MEMORY utilise l'algorithme HASH par défaut.

Pour rire, j'ai essayé de créer une table InnoDB et une table MyISAM avec une clé primaire avec HASH dans 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 ne s'est pas plaint.

MISE À JOUR

Mauvaises nouvelles !!! J'ai utilisé SHOW INDEXES FROM. Il dit que l'indice est BTREE.

La page MySQL de la syntaxe CREATE INDEX indique que seuls les moteurs de stockage MEMORY et NDB peuvent prendre en charge HASH INDEX.

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)

Certaines personnes ont suggéré de suivre l’idée des pages 102 à 105 de l’ouvrage " MySQL hautes performances: optimisations, sauvegardes, réplication, etc." etc." pour émuler l’algorithme de hachage.

La page 105 présente cet algorithme rapide que je préfère:

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

Créez une colonne pour cela dans n'importe quelle table et indexez cette valeur.

Essaie !!!

RolandoMySQLDBA
la source
5
Avant d'utiliser la technique de pseudo-hachage-index en production, analysez-la. Pour les chaînes de grande taille, cela peut faire toute la différence, mais vous finissez toujours par parcourir un index arborescent et vous devez faire des comparaisons supplémentaires pour trouver la bonne ligne parmi celles trouvées avec le hachage, donc pour les petites valeurs, calculer les valeurs de hachage les stocker ne vaut tout simplement pas la peine. Ce n'est pas vraiment un index de hachage, vous réduisez simplement le travail effectué dans l'arborescence (chaque comparaison prenant en compte moins d'octets, par exemple en comparant des INT de 8 octets au lieu de chaînes de x00 octets).
David Spillett
@ David Spillett En cela, je suis totalement d'accord avec vous. D'autres stratégies d'indexation sont également suggérées dans le même ouvrage au chapitre 11 "Stratégies d'indexation pour de hautes performances". Pour renforcer encore ma réponse, le livre mentionne en fait l’utilisation d’un index clusterisé qui stocke la ligne et l’indice BTree dans la même structure. Cela pourrait accélérer le travail réduit que vous avez mentionné. Malheureusement, les obstacles auxquels vous devez faire face que vous venez de mentionner sont quelque peu inévitables. Un +1 de moi sur votre commentaire néanmoins, monsieur !!! En fait, +1 pour votre réponse également.
RolandoMySQLDBA
@RolandoMySQLDBA Pouvez-vous en dire plus sur le "hachage personnalisé", le dernier paragraphe ne semble pas donner beaucoup d'indices ...
Pacerier
2

BTree n’est pas beaucoup plus lent que Hash pour la recherche sur une seule ligne. Puisque BTree fournit des requêtes de gamme très efficaces, pourquoi s’embêter avec autre chose que BTree.

MySQL fait un très bon travail de mise en cache des blocs BTree, aussi une requête basée sur BTree doit-elle rarement faire des E / S, qui est le plus gros consommateur de temps de toute requête.

Rick James
la source