¿Acelerar mis índices en MySQL - CRC o MD5?

Question

Tengo una gran mesa con algo así como 8 300 000 filas (no se editará ni eliminará nunca).

Mi primera columna tiene un aspecto similar P300-4312B_X16_S y la entrada no es única, así que utilizo un ÍNDICE regular en este campo.

Sin embargo, MySQL es MUCHO más rápido usando un campo binario en lugar de un varchar, así que codifico mi ÍNDICE en MD5 usando BINARY(16) para almacenar los datos.

Esta mañana, he comenzado a utilizar CRC32 por primera vez y he visto que CRC32 se puede generar como una cadena hexadecimal con 8 caracteres.

Mi pregunta: Si utilizo un CRC32 en lugar de un MD5, será más rápido. Sin embargo, cuando se ejecuta CRC32 digamos 2 000 000 de valor único, el resultado será único o tal vez en algún momento tendré el doble de la misma cadena para dos cadenas diferentes. Lo pregunto porque el resultado es de solo 8 caracteres (32b) de largo en lugar de 32 (128b) como el MD5.

Gracias.

Answer 1

El número esperado de colisiones es el número de pares sobre el número de posibles valores de verificación. Entonces para 2,000,000 de valores hay (2000000 * 1999999)/2 pares, que es aproximadamente 2x10 . Para un CRC de 32 bits, el número esperado de colisiones es el de más de 2 , que es 466. Por lo tanto, esencialmente se garantiza que habrá colisiones en ese caso.

Para un valor de comprobación de MD5 de 128 bits, el número esperado de colisiones es de aproximadamente 6x10 ^-27. Para valores pequeños del número esperado, esa es también la probabilidad de una colisión.

Si es importante para usted tener una probabilidad muy baja de una colisión, entonces necesita elegir algo que no sea CRC-32.

No necesita la sobrecarga de MD5 sin embargo, donde su fuerza criptográfica no es importante para su aplicación. Realmente no te importa si alguien malicioso puede encontrar una forma de fabricar una entrada con el mismo valor de verificación que otra entrada. Por lo tanto, podría usar un hash no criptográfico de 64 bits diseñado para ese propósito, que se ejecutaría mucho más rápido y daría una probabilidad de colisión de 10 ^-7 en su caso de 2,000,000 de valores. O puede usar un hash no criptográfico de 128 bits y obtener la misma probabilidad que para MD5, pero mucho más rápido. Eche un vistazo a CityHash family de los algoritmos hash.

Sin embargo, tenga en cuenta que en todos los casos la probabilidad de una colisión no es cero. Debería considerar las consecuencias de una colisión en su código.