¿Por qué MySQL no tiene índices hash en MyISAM o InnoDB?

Tengo una aplicación que solo seleccionará la igualdad, y creo que debería usar un índice hash sobre un índice btree. Para mi consternación, los índices hash no son compatibles con MyISAM o InnoDB. ¿Que pasa con eso?

Muchas bases de datos no admiten índices basados en hash en absoluto .

Para que una tabla hash sea eficiente, necesita saber el número de filas que probablemente estén presentes; de lo contrario, la tabla hash base será demasiado grande (muchas entradas vacías, desperdicio de espacio y potencialmente IO de disco) o demasiado pequeño, lo que significa que a menudo se usa la indirección (posiblemente múltiples niveles de indirección, o peor aún si la implementación de hash es de un solo nivel, podría terminar realizando una búsqueda lineal en un número considerable de registros) en cuyo punto las cosas probablemente no sean más eficientes que un árbol índice de todos modos.

Por lo tanto, para ser generalmente útil (es decir, generalmente mejor que la alternativa), el índice debe reconstruirse ocasionalmente a medida que los datos crecen (y se reducen), lo que podría agregar una sobrecarga intermitente significativa. Esto generalmente está bien con las tablas basadas en memoria, ya que la reconstrucción probablemente será bastante rápida (ya que los datos siempre estarán en RAM y no es probable que sean masivos en cualquier caso), pero reconstruir un índice grande en el disco es un operación muy pesada (y IIRC mySQL no admite reconstrucciones de índice en vivo, por lo que mantiene un bloqueo de tabla durante la operación).

Por lo tanto, los índices hash se usan en las tablas de memoria, ya que generalmente tienen un mejor rendimiento, pero las tablas basadas en disco no los admiten, ya que podrían ser en detrimento del rendimiento, no una ventaja. No hay nada que índices hash dejar de ser puesto a disposición de las tablas de base de disco, por supuesto, sin duda algunas bases de datos hacen compatible con la función, pero se supone que no se implementa en ISAM / tablas InnoDB como los mantenedores no consideran el valor de función de la adición (como el código adicional para escribir y mantener no vale la pena el beneficio en esas pocas circunstancias que hace una diferencia significativa). Quizás si no está de acuerdo, podría hablar con ellos y presentar un buen caso para la implementación de la función.

Si está indexando cadenas grandes, entonces puede implementar su propio índice pseudo-hash (almacenando un hash del valor, así como el valor real, y la indexación que tiene una columna), pero esto definitivamente es más eficiente para cadenas grandes (donde calcular el valor hash y buscar en el índice de árbol por este valor siempre es más rápido que simplemente buscar un índice de árbol usando los valores más grandes para comparar, y el almacenamiento adicional utilizado no será significativo), así que haga un análisis de rendimiento antes de implementar esta en produccion.

En una nota relacionada, puede encontrar interesante la discusión sobre los tipos de índice de los documentos de PostgreSQL. Ya no está presente en las versiones recientes de los documentos (debido a las optimizaciones posteriores, supongo), pero la conclusión podría ser similar para MySQL (y la razón por la cual los índices hash solo se usan para tablas de montón):

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

Nota: Las pruebas han demostrado que los índices hash de PostgreSQL no funcionan mejor que los índices B-tree, y el tamaño del índice y el tiempo de construcción de los índices hash es mucho peor. Además, las operaciones de índice hash no están actualmente registradas en WAL, por lo que es posible que sea necesario reconstruir los índices hash con REINDEX después de un bloqueo de la base de datos. Por estos motivos, actualmente no se recomienda el uso del índice hash. Del mismo modo, los índices del árbol R no parecen tener ventajas de rendimiento en comparación con las operaciones equivalentes de los índices GiST. Al igual que los índices hash, no están registrados en WAL y pueden necesitar reindexarse ​​después de un bloqueo de la base de datos. Si bien los problemas con los índices hash pueden corregirse eventualmente, es probable que el tipo de índice R-tree se retire en una versión futura. Se alienta a los usuarios a migrar aplicaciones que usan índices de árbol R a índices GiST.

Nuevamente, es (versión obsoleta) específica de PostgreSQL, pero debería indicar que el tipo de índice "natural" no necesariamente rendirá un rendimiento óptimo.

Aquí hay algo interesante:

De acuerdo con el libro MySQL 5.0 Certification Study Guide , página 433, sección 29.5.1

El motor MEMORY utiliza HASH por defecto el algoritmo de indexación.

Para reír, intenté crear una tabla InnoDB y una tabla MyISAM con una clave principal usando HASH en 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 no se quejó.

ACTUALIZAR

Malas noticias !!! Usé SHOW INDEXES FROM. Dice que el índice es BTREE.

La página MySQL de la sintaxis CREATE INDEX establece que solo los motores de almacenamiento MEMORY y NDB pueden acomodar el 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)

Algunas personas sugirieron seguir la idea en las páginas 102-105 del libro " MySQL de alto rendimiento: optimizaciones, copias de seguridad, replicación y más " para emular el algoritmo hash.

La página 105 presenta este algoritmo rápido y sucio que me gusta:

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

Haga una columna para esto en cualquier tabla e indexe este valor.

Darle una oportunidad !!!

BTree no es mucho más lento que Hash para la búsqueda de una sola fila. Dado que BTree proporciona consultas de rango muy eficientes, ¿por qué molestarse con otra cosa que no sea BTree?

MySQL hace un muy buen trabajo al almacenar en caché los bloques BTree, por lo que una consulta basada en BTree rara vez tiene que hacer E / S, que es el mayor consumidor de tiempo en cualquier consulta.