¿Cuándo y por qué las uniones de base de datos son caras?

Desnormalización para mejorar el rendimiento? Suena convincente, pero no aguanta.

Chris Date, quien en compañía del Dr. Ted Codd fue el proponente original del modelo de datos relacionales, se quedó sin paciencia con argumentos mal informados contra la normalización y los demolió sistemáticamente utilizando un método científico: obtuvo grandes bases de datos yprobó estas afirmaciones.

Creo que lo escribió en Escritos de Bases de Datos Relacionales 1988-1991 pero este libro más tarde se incluyó en la sexta edición de Introducción a los Sistemas de Bases de Datos, que es el texto definitivo sobre la teoría y el diseño de bases de datos, en su octava edición mientras escribo y es probable que permanezca impreso durante las próximas décadas. Chris Date era un experto en este campo cuando la mayoría de nosotros todavía corríamos descalzos.

Encontró que:

• Algunos de ellos son para casos especiales
• Todos ellos no pagan para uso general
• Todos ellos son significativamente peor para otros casos especiales

Todo vuelve a mitigar el tamaño del conjunto de trabajo. Las uniones que involucran claves correctamente seleccionadas con índices correctamente configurados son baratas, no costosas, porque permiten una poda significativa del resultado antes de que las filas se materialicen.

Materializar el resultado implica lecturas de disco a granel que son el aspecto más caro del ejercicio por un orden de magnitud. Realizar una unión, por el contrario, lógicamente requiere la recuperación de solo las claves . En la práctica, ni siquiera se obtienen los valores clave: los valores hash clave se utilizan para comparaciones de uniones, mitigando el costo de las uniones de varias columnas y reduciendo radicalmente el costo de las uniones que involucran comparaciones de cadenas. No solo cabrá mucho más en la caché, sino que hay mucho menos lectura de disco que hacer.

Además, un buen optimizador elegirá la condición más restrictiva y la aplicará antes de realizar una unión, aprovechando de manera muy efectiva la alta selectividad de uniones en índices con alta cardinalidad.

Es cierto que este tipo de optimización también se puede aplicar a bases de datos desnormalizadas, pero el tipo de personas que quieren desnormalizar un esquema normalmente no piensan en cardinalidad cuando (si) establecen índices.

Es importante entender que los escaneos de tabla (examen de cada fila en una tabla en el curso de producir una unión) son raros en la práctica. Un optimizador de consultas elegirá un análisis de tabla solo cuando o más de lo siguiente se mantiene.

• Hay menos de 200 filas en la relación (en este caso un escaneo será más barato)
• No hay índices adecuados en las columnas de unión (si es significativo unirse en estas columnas, ¿por qué no están indexadas? arréglalo)
• Se requiere una coerción de tipo antes de que las columnas puedan compararse (WTF?! fix it or go home) VER NOTAS FINALES PARA ADO.NET CUESTIÓN
• Uno de los argumentos de la comparación es una expresión (no index)

Realizar una operación es más caro que no realizarla. Sin embargo, realizar la operación incorrecta, ser forzado a E/S de disco sin sentido y luego descartar la escoria antes de realizar la unión que realmente necesita, es mucho más caro. Incluso cuando la operación" incorrecta " está precalculada y los índices se han aplicado con sensatez, sigue habiendo una penalización significativa. La desnormalización para precomputar un join-a pesar de las anomalías de actualización un compromiso con una unión en particular. Si necesitas un diferente join, ese compromiso te va a costar mucho .

Si alguien quiere recordarme que es un mundo cambiante, creo que encontrará que los conjuntos de datos más grandes en hardware gruntier solo exageran la propagación de los hallazgos de Date.

Para todos ustedes que trabajan en sistemas de facturación o generadores de correo basura (vergüenza para ustedes) y están indignados poniendo la mano en el teclado para decirme que saben a ciencia cierta que la desnormalización es más rápida, lo siento, pero estás viviendo en uno de los casos especiales, específicamente, el caso en el que procesas todos los datos, en orden. No es un caso general, y tú estás justificado en tu estrategia.

Estás no justificado en generalizarlo falsamente. Consulte el final de la sección notas para obtener más información sobre el uso adecuado de la desnormalización en escenarios de almacenamiento de datos.

, también me gustaría responder a

Las uniones son solo productos cartesianos con algo de brillo de labios

Qué montón de tonterías. Las restricciones se aplican lo antes posible, primero las más restrictivas. Has leído la teoría, pero no la has entendido. Las uniones son tratadas como "productos cartesianos a los que se aplican predicados" solo por el optimizador de consultas. Esta es una representación simbólica (una normalización, de hecho) para facilitar la descomposición simbólica para que el optimizador pueda producir todas las transformaciones equivalentes y clasifíquelos por costo y selectividad para que pueda seleccionar el mejor plan de consultas.

La única manera de conseguir que el optimizador produzca un producto cartesiano es no suministrar un predicado: SELECT * FROM A,B

Notas

David Aldridge proporciona información adicional importante.

De hecho, hay una variedad de otras estrategias además de los índices y análisis de tablas, y un optimizador moderno les costará a todos antes de producir un plan de ejecución.

A consejo práctico: si se puede utilizar como clave foránea, indexarla, de modo que el optimizador tenga una estrategia de indexación.

Solía ser más inteligente que el optimizador MSSQL. Eso cambió hace dos versiones. Ahora generalmente me enseña . Es, en un sentido muy real, un sistema experto, que codifica toda la sabiduría de muchas personas muy inteligentes en un dominio lo suficientemente cerrado como para que un sistema basado en reglas sea eficaz.

"Bollocks" puede haber sido sin tacto. Me preguntan a ser menos arrogante y recordó que las matemáticas no mienten. Esto es cierto, pero no todas las implicaciones de los modelos matemáticos deben tomarse necesariamente literalmente. Las raíces cuadradas de los números negativos son muy útiles si evita cuidadosamente examinar su absurdo (juego de palabras) y asegúrese de cancelarlos todos antes de intentar interpretar su ecuación.

La razón por la que respondí tan salvajemente fue que la declaración tal como está redactada dice que

Se une son productos cartesianos...

Esto puede no ser lo que se quería decir, pero es lo que se escribió, y es categóricamente falso. Un producto cartesiano es una relación. Una unión es una función. Más específicamente, una unión es una función valorada por relación. Con un predicado vacío producirá un producto cartesiano, y comprobar que lo hace es una comprobación de corrección para un motor de consultas de base de datos, pero nadie escribe uniones sin restricciones en la práctica porque no tienen ningún valor práctico fuera de un aula.

Dije esto porque no quiero que los lectores caigan en la antigua trampa de confundir el modelo con la cosa modelada. Un modelo es una aproximación, deliberadamente simplificada para una manipulación conveniente.

El corte para la selección de una estrategia de unión de exploración de tabla puede variar entre los motores de base de datos. Se ve afectado por una serie de decisiones de implementación, como el factor de relleno árbol-nodo, el tamaño clave-valor y las sutilezas del algoritmo, pero en general hablando de alto rendimiento de la indexación tiene un tiempo de ejecución de k log n + c. El término C es una sobrecarga fija hecha principalmente de tiempo de configuración, y la forma de la curva significa que no obtienes una recompensa (en comparación con una búsqueda lineal) hasta que n está en los cientos.

A veces la desnormalización es una buena idea

La desnormalización es un compromiso con una estrategia de unión en particular. Como se mencionó anteriormente, esto interfiere con otras estrategias de unión. Pero si tiene cubos de espacio en disco, patrones predecibles de acceso y una tendencia a procesar mucho o todo, entonces precomputar una unión puede valer la pena.

También puede averiguar las rutas de acceso que normalmente usa su operación y precomputar todas las uniones para esas rutas de acceso. Esta es la premisa detrás de los almacenes de datos, o al menos lo es cuando están construidos por personas que saben por qué están haciendo lo que están haciendo, y no solo por el bien de la palabra de moda cumplimiento.

Un almacén de datos correctamente diseñado se produce periódicamente mediante una transformación masiva a partir de un sistema de procesamiento de transacciones normalizado. Esta separación de las bases de datos de operaciones e informes tiene el efecto muy deseable de eliminar el choque entre OLTP y OLAP (procesamiento de transacciones en línea, es decir, entrada de datos, y procesamiento analítico en línea, es decir, informes).

Un punto importante aquí es que aparte de las actualizaciones periódicas, el almacén de datos es leer solo . Esto hace discutible la cuestión de las anomalías de actualización.

No cometa el error de desnormalizar su base de datos OLTP (la base de datos en la que ocurre la entrada de datos). Puede ser más rápido para las ejecuciones de facturación, pero si lo hace, obtendrá anomalías de actualización. ¿Alguna vez has intentado que Reader's Digest deje de enviarte cosas?

El espacio en disco es barato en estos días, así que diviértete. Pero la desnormalización es solo una parte de la historia de los almacenes de datos. Se derivan ganancias de rendimiento mucho más grandes de valores pre-calculados: totales mensuales, ese tipo de cosas. Se trata de siempre de reducir el conjunto de trabajo.

ADO.NET problema con desajustes de tipo

Supongamos que tiene una tabla SQL Server que contiene una columna indexada de tipo varchar, y utiliza AddWithValue para pasar un parámetro que restringe una consulta en esta columna. Las cadenas de C# son Unicode, por lo que el tipo de parámetro inferido será NVARCHAR, que no coincide con VARCHAR.

VARCHAR a NVARCHAR es un ampliar la conversión para que suceda implícitamente , pero diga adiós a la indexación y buena suerte averiguando por qué.

"Contar los golpes de disco" (Rick James)

Si todo está almacenado en memoria RAM, JOINs son bastante baratos. Es decir, la normalización no tiene mucha penalización de rendimiento.

Si un esquema" normalizado " hace que JOINs golpee el disco mucho, pero el esquema "desnormalizado" equivalente no tendría que golpear el disco, entonces la desnormalización gana un rendimiento competencia.

Comentario del autor original: Los motores de base de datos modernos son muy buenos para organizar la secuenciación de acceso para minimizar los errores de caché durante las operaciones de unión. Lo anterior, si bien es cierto, podría ser mal interpretado como implicando que las uniones son necesariamente problemáticas caras en grandes datos. Esto llevaría a causar una mala toma de decisiones por parte de desarrolladores inexpertos.