Tengo una tabla con 70 millones de registros y me falta un índice. Quiero calcular el tiempo para agregar el índice sin hacer una copia de seguridad de la tabla y hacer el índice en la tabla respaldada.¿Agregar el índice en una tabla de 2 millones de registros será el doble de lento que la misma tabla con 1 millón de registros?
Me pregunto si será el doble de lento (lineal) o si es exponencial.
base de datos: MySQL 5.0
Muchas gracias
(Negación: Tengo experiencia mínimo en MySQL)
Debe estar en algún lugar en el medio.
La complejidad absolutamente más baja de toda la operación sería la que aparecería al leer todos los registros en orden, que es un proceso lineal: O(n). Esta es una operación de E/S ligada y no se puede hacer mucho al respecto; los sistemas de caché modernos en la mayoría de los sistemas operativos pueden ayudar, pero solo en un DB que está en uso y que cabe en la memoria disponible.
En la mayoría de los motores SQL, los índices son una variación de un árbol B. La complejidad de la CPU de insertar un solo registro en dicho árbol es aproximadamente O(log(n)), donde n es su tamaño. Para los registros n obtenemos una complejidad de O(n log(n)). La complejidad total de la operación debe ser O(n log(n)).
Por supuesto, no es tan simple. La computación del árbol de índice no es realmente pesada para la CPU y dado que las páginas de índice deben caber en la RAM en cualquier sistema moderno, la operación de insertar un solo nodo cuando el árbol no está reequilibrado sería cercano a O(1) en el tiempo: una sola operación de disco para actualizar una página de hoja del índice.
Dado que el árbol se vuelve a equilibrar, sin embargo, las cosas son probablemente un poco más complejas. Es posible que haya que comprometer varias páginas de índice en el disco, lo que aumenta el tiempo necesario. Como una aproximada suposición, diría que O(n log(n)) es un buen comienzo ...
Sin embargo, nunca debería acercarse a una complejidad exponencial.
EDIT:
Simplemente me ocurrió que 70.000.000 entradas de árbol B no puede, de hecho, en forma en el caché en memoria. Dependería mucho de que se está indexando. INTEGER las columnas probablemente estarían bien, pero las columnas TEXT son otra historia. Si la longitud promedio del campo es de 100 bytes (por ejemplo, enlaces HTTP o 30 caracteres de texto UTF-8 que no está en inglés), necesitará más de 7 GB de memoria para almacenar el índice.
En pocas palabras:
Si el índice se ajusta en la memoria caché, a continuación, desde la construcción del índice debería ser una sola transacción DB, sería I/O-ligado y más o menos lineal, como todos los registros tienen para ser analizado y luego el índice itelse tiene que ser escrito en el almacenamiento permanente.
Si el índice no cabe en la memoria caché, la complejidad aumenta, ya que los tiempos de espera de E/S en el índice se involucran en cada operación.
¿Qué thkala describe es cierto para la inserción de filas individuales, pero al crear un nuevo índice, no RDBMS razonable se acaba de hacer n insertos, sino que se construir el índice de comenzar directamente con los nodos hoja. Es casi seguro que este proceso estará vinculado a IO.
Por lo tanto, en términos prácticos, el tiempo de reindexación debe ser lineal: el doble de largo para el doble de registros.
Verdadero, construir el índice debe ser una sola transacción. La complejidad del tiempo, sin embargo, dependerá de si el árbol de índice encajará en la RAM o no. 70,000,000 entradas de índice en una columna de TEXTO podrían llenar fácilmente varios GB de caché en memoria ... – thkala
Gracias por su respuesta! Está mucho más claro ahora –