SQL Server Hash Indexes

Question

Al usar la columna CHECKSUM para crear artificialmente un índice hash, ¿la búsqueda es realmente O (1) o sigue siendo O (lg n) como lo es para un índice agrupado? Tengo una tabla de la que seleccionaré en función de su columna de ID y necesito que la búsqueda sea lo más rápida posible, ¿es el índice agrupado la opción más rápida posible? Estoy buscando algo que proporcione un rendimiento O (1).

Answer 1

De acuerdo, 2 puntos.
La función SQL CHECKSUM no produce un valor hash. En realidad, calcula un valor de CRC. No es un buen candidato para basar un control de hash porque habrá una cantidad relativamente grande de colisiones. Debería verificar la función hash_bytes si quiere una función hash.
En segundo lugar, en realidad no está creando un índice hash. Está creando un b-tree normal en un valor hash para que el tiempo de búsqueda sea exactamente el mismo que para cualquier otro índice b-tree en un tipo de datos de tamaño similar.
Existe la posibilidad de que pueda obtener un pequeño rendimiento utilizando un CRC o hash de un valor varchar largo para permitir comparaciones de un número menor de bytes, pero la comparación de cadenas solo comprueba tantos bytes como sea necesario, que es como Hasta el primer carácter que no coincide, y si coincide en el valor hash, entonces necesita verificar el valor real de todos modos. Entonces, a menos que tenga muchas cadenas muy similares, probablemente termine comparando MÁS bytes usando el hash (o CRC).

En resumen, no creo que este sea un plan sensato, pero como con todas las optimizaciones, debe probarlo en su caso específico y luego decidir. Me interesaría ver sus resultados si quisiera publicarlos. Y no creo que haya una forma más rápida de localizar una fila en el servidor SQL que usar un índice agrupado.

En caso de que te importe, Ingres (por CA) puede crear índices hash que luego lograrán O (1). puede haber otros RDBM disponibles que también admitan índices hash verdaderos.

Answer 2

No hay ventaja de buscar un CHECKSUM indexado sobre un índice agrupado en el campo ID si el campo ID es un int ya que ambos harán una búsqueda de índice agrupado. Además, un CHECKSUM de una columna int siempre devuelve el mismo valor que la columna (es decir, CHECKSUM (535) = 535). Sin embargo, una búsqueda de CHECKSUM generalmente tendrá un mejor rendimiento si la ID es una columna de caracteres largos.

Answer 3

Puede intentar configurar las cosas para utilizar una combinación hash, puede consultar el plan de ejecución para verificar que realmente se utiliza una combinación hash. Cuando se utilizan uniones hash, SQL Server seguirá construyendo la tabla hash primero como parte de la ejecución de la consulta individual. Creo que los índices nunca se almacenan como hash, solo como árboles.

En general, no crearía una columna hash artificial a menos que esté haciendo coincidencias exactas contra cadenas potencialmente grandes o blobs binarios (como pipTheGeek menciona). Solo quería agregar que a veces esto es necesario ya que las cadenas pueden ser demasiado grandes para caber en una clave de índice. Existe un límite en el tamaño de las claves de índice de 2k para SQL Server.

Por supuesto, en su unión necesita incluir la columna hash y la columna fuente para resolver cualquier ambigüedad que resulte del hash.

Answer 4

No creo que SQL Server tenga un índice basado en la tabla hash. El BOL documentation está hablando de construir un índice estándar (árbol) en un valor calculado. Esto no es lo mismo que Linear Hash Table, que es una estructura de índice disponible en algunas plataformas DBMS, pero no SQL Server (AFAIK).

Puede obtener algún beneficio del uso de la técnica descrita en this blog post para calcular valores de cadena grandes, como URL, para una búsqueda más rápida. Sin embargo, el índice subyacente sigue siendo una estructura de árbol y es O (Log N).