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

Estoy investigando algunas bases de datos y estoy viendo algunas limitaciones de las bases de datos relacionales.

Me parece que las combinaciones de tablas grandes son muy caras, pero no estoy completamente seguro de por qué. ¿Qué necesita hacer el DBMS para ejecutar una operación de unión? ¿Dónde está el cuello de botella?
¿Cómo puede ayudar la desnormalización a superar este gasto? ¿Cómo ayudan otras técnicas de optimización (indexación, por ejemplo)?

¡Las experiencias personales son bienvenidas! Si va a publicar enlaces a recursos, evite Wikipedia. Ya sé dónde encontrar eso.

En relación con esto, me pregunto acerca de los enfoques desnormalizados utilizados por las bases de datos de servicios en la nube como BigTable y SimpleDB. Ver esta pregunta .

¿Denormalizar para mejorar el rendimiento? Suena convincente, pero no retiene el agua.

Chris Date, quien en compañía del Dr. Ted Codd fue el defensor 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 y probó estas afirmaciones.

Creo que lo escribió en Relational Database Writings 1988-1991, pero este libro luego se incluyó en la sexta edición de Introducción a los sistemas de bases de datos , que es el texto definitivo sobre teoría y diseño de bases de datos, en su octava edición mientras escribo y es probable que permanezca en imprenta en las próximas décadas. Chris Date era un experto en este campo cuando la mayoría de nosotros seguíamos corriendo descalzos.

Encontró que:

• Algunos de ellos son válidos para casos especiales
• Todos ellos no pagan por el uso general
• Todos ellos son significativamente peores para otros casos especiales.

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

La materialización del resultado implica lecturas de disco masivas, que son el aspecto más costoso del ejercicio por 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 las comparaciones de unión, mitigar el costo de las uniones de varias columnas y reducir radicalmente el costo de las uniones que involucran comparaciones de cadenas. No solo encajará mucho más en la memoria caché, también 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 las 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 desean desnormalizar un esquema generalmente no piensan en la cardinalidad cuando (si) establecen índices.

Es importante comprender 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 escaneo de tabla solo cuando se mantenga una o más de las siguientes opciones.

• 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 tiene sentido unirse en estas columnas, ¿por qué no están indexadas?
• Se requiere una conversión de tipos antes de que las columnas se pueden comparar (WTF ?! arreglarlo o volver a casa) VER NOTAS FIN DE EMISIÓN ADO.NET
• Uno de los argumentos de la comparación es una expresión (sin índice)

Realizar una operación es más costoso 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 costoso. Incluso cuando la operación "incorrecta" se calcula previamente y los índices se han aplicado con sensatez, sigue habiendo una penalización significativa. Renormalizar para precalcular una unión, a pesar de las anomalías de actualización que conlleva, es un compromiso con una unión particular. Si necesita una unión diferente , ese compromiso le costará mucho .

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

Para todos ustedes que trabajan en sistemas de facturación o generadores de correo basura (la culpa es suya) y están indignados con la mano en el teclado para decirme que saben con certeza que la desnormalización es más rápida, lo siento, pero están viviendo en uno de los especiales casos: específicamente, el caso en el que procesa todos los datos, en orden. No es un caso general, y está justificado en su estrategia.

Usted está no justificados en falso generalizar él. Consulte el final de la sección de notas para obtener más información sobre el uso apropiado de la desnormalización en escenarios de almacenamiento de datos.

También me gustaría responder a

Las uniones son solo productos cartesianos con brillo labial

Qué carga de bollocks. Las restricciones se aplican lo antes posible, lo más restrictivo primero. Has leído la teoría, pero no la has entendido. Las uniones se tratan 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 clasificarlas por costo y selectividad para que pueda seleccionar el mejor plan de consulta.

La única forma en que obtendrá el optimizador para producir un producto cartesiano es no proporcionar 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 índices y escaneos de tablas, y un optimizador moderno les costará a todos antes de producir un plan de ejecución.

Un consejo práctico: si se puede utilizar como clave externa, indexarlo, de modo que el optimizador disponga de 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 efectivo.

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

La razón por la que respondí tan salvajemente fue que la declaración redactada dice que

Las uniones son productos cartesianos ...

Puede que esto no sea lo que se quiso 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 de valor de relación. Con un predicado vacío producirá un producto cartesiano, y verificar que lo haga es una verificación de corrección para un motor de consulta de base de datos, pero nadie escribe uniones sin restricciones en la práctica porque no tienen ningún valor práctico fuera del aula.

Lo llamé 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 límite para la selección de una estrategia de unión de exploración de tabla puede variar entre los motores de la base de datos. Se ve afectado por una serie de decisiones de implementación, como el factor de relleno del nodo de árbol, el tamaño del valor clave y las sutilezas del algoritmo, pero en términos generales, la indexación de alto rendimiento tiene un tiempo de ejecución de k log n + c . El término C es una sobrecarga fija compuesta principalmente por el tiempo de configuración, y la forma de la curva significa que no obtendrá 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 particular. Como se mencionó anteriormente, esto interfiere con otras estrategias de unión. Pero si tiene cubos de espacio en disco, patrones de acceso predecibles y una tendencia a procesar gran parte o la totalidad de ellos, entonces puede ser muy útil precalcular una unión.

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

Un almacén de datos correctamente diseñado se produce periódicamente mediante una transformación masiva fuera 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 de solo lectura . 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 trataste de que Reader's Digest dejara de enviarte cosas?

El espacio en disco es barato en estos días, así que déjate llevar. Pero la desnormalización es solo una parte de la historia de los almacenes de datos. Las ganancias de rendimiento mucho mayores se derivan de valores acumulados precalculados: totales mensuales, ese tipo de cosas. Es siempre trata de reducir el espacio de trabajo.

Problema de ADO.NET con desajustes de tipo

Suponga que tiene una tabla de SQL Server que contiene una columna indexada de tipo varchar, y usa 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 una conversión cada vez más amplia, por lo que sucede implícitamente, pero diga adiós a la indexación y buena suerte para averiguar por qué.

"Cuenta los golpes en el disco" (Rick James)

Si todo está en caché en RAM, JOINsson bastante baratos. Es decir, la normalización no tiene mucha penalización de rendimiento .

Si un esquema "normalizado" causa mucho JOINsimpacto en el disco, pero el esquema equivalente "desnormalizado" no tendría que afectar el disco, entonces la desnormalización gana una competencia de rendimiento.

Comentario del autor original: Los motores de bases de datos modernos son muy buenos para organizar la secuencia de acceso para minimizar las fallas de caché durante las operaciones de unión. Lo anterior, si bien es cierto, podría interpretarse erróneamente como que implica que las uniones son necesariamente problemáticamente caras en grandes datos. Esto llevaría a una mala toma de decisiones por parte de desarrolladores sin experiencia.

Lo que la mayoría de los comentaristas no notan es la amplia gama de metodologías de combinación disponibles en un RDBMS complejo, y los denormalizadores invariablemente pasan por alto el mayor costo de mantener los datos denormalizados. No todas las uniones se basan en índices, y las bases de datos tienen muchos algoritmos y metodologías optimizadas para unir que tienen como objetivo reducir los costos de las uniones.

En cualquier caso, el costo de una unión depende de su tipo y algunos otros factores. No tiene por qué ser caro, algunos ejemplos.

• Una combinación hash, en la que se combinan datos masivos, es muy barata y el costo solo se vuelve significativo si la tabla hash no se puede almacenar en la memoria caché. No se requiere índice. La división equitativa entre los conjuntos de datos unidos puede ser de gran ayuda.
• El costo de una combinación de clasificación y combinación depende del costo de la clasificación en lugar de la combinación: un método de acceso basado en índices puede eliminar virtualmente el costo de la clasificación.
• El costo de una unión de bucle anidado en un índice depende de la altura del índice b-tree y del acceso del bloque de la tabla. Es rápido, pero no es adecuado para uniones masivas.
• Una unión de bucle anidado basada en un clúster es mucho más barata, con menos IO lógicas requeridas por fila de unión: si las tablas unidas están ambas en el mismo clúster, la unión se vuelve muy barata mediante la colocación de filas unidas.

Las bases de datos están diseñadas para unirse, y son muy flexibles en su forma de hacerlo y, en general, son muy eficaces a menos que obtengan un mecanismo de unión incorrecto.

Creo que toda la pregunta se basa en una premisa falsa. Las uniones en mesas grandes no son necesariamente caras. De hecho, hacer uniones de manera eficiente es una de las principales razones por las que existen bases de datos relacionales . Las uniones en conjuntos grandes a menudo son caras, pero muy raramente desea unir todo el contenido de la tabla grande A con todo el contenido de la tabla grande B. En su lugar, escribe la consulta de modo que solo se usen las filas importantes de cada tabla y El conjunto real mantenido por la unión sigue siendo menor.

Además, tiene las eficiencias mencionadas por Peter Wone, de modo que solo las partes importantes de cada registro deben estar en la memoria hasta que se materialice el conjunto de resultados final. Además, en consultas grandes con muchas combinaciones, generalmente desea comenzar con los conjuntos de tablas más pequeños y avanzar hasta los grandes, de modo que el conjunto guardado en la memoria permanezca lo más pequeño posible el mayor tiempo posible.

Cuando se hace correctamente, las uniones son generalmente la mejor manera de comparar, combinar o filtrar grandes cantidades de datos.

El cuello de botella es casi siempre E / S de disco, e incluso más específicamente: E / S de disco aleatorio (en comparación, las lecturas secuenciales son bastante rápidas y se pueden almacenar en caché con estrategias de lectura anticipada).

Las uniones pueden aumentar las búsquedas aleatorias, si estás saltando leyendo pequeñas partes de una mesa grande. Pero, los optimizadores de consultas lo buscan y lo convertirán en un escaneo de tabla secuencial (descartando las filas innecesarias) si cree que sería mejor.

Una sola tabla desnormalizada tiene un problema similar: las filas son grandes y, por lo tanto, se ajustan menos en una sola página de datos. Si necesita filas ubicadas lejos de otra (y el tamaño de la fila grande las separa más), tendrá más E / S aleatorias. Una vez más, un escaneo de tabla puede verse obligado a evitar esto. Pero, esta vez, el escaneo de la tabla tiene que leer más datos debido al gran tamaño de la fila. Agregue a eso el hecho de que está copiando datos de una sola ubicación a múltiples ubicaciones, y el RDBMS tiene mucho más para leer (y caché).

Con 2 tablas, también obtiene 2 índices agrupados, y generalmente puede indexar más (debido a una menor sobrecarga de inserción / actualización), lo que puede aumentar drásticamente el rendimiento (principalmente, de nuevo, porque los índices son (relativamente) pequeños, rápidos para leer en el disco (o barato para almacenar en caché), y disminuye la cantidad de filas de la tabla que necesita leer desde el disco).

Casi la única sobrecarga con una unión proviene de descubrir las filas coincidentes. SQL Server utiliza 3 tipos diferentes de combinaciones, principalmente basadas en tamaños de conjuntos de datos, para encontrar filas coincidentes. Si el optimizador elige el tipo de unión incorrecto (debido a estadísticas inexactas, índices inadecuados o simplemente un error del optimizador o un caso extremo), puede afectar drásticamente los tiempos de consulta.

• Una unión en bucle es muy barata para (al menos 1) conjunto de datos pequeño.
• Una combinación de fusión requiere primero una especie de ambos conjuntos de datos. Sin embargo, si se une en una columna indexada, entonces el índice ya está ordenado y no es necesario realizar más trabajos. De lo contrario, hay una sobrecarga de CPU y memoria en la clasificación.
• La combinación hash requiere memoria (para almacenar la tabla hash) y CPU (para construir el hash). Nuevamente, esto es bastante rápido en relación con la E / S del disco. Sin embargo , si no hay suficiente RAM para almacenar la tabla hash, Sql Server usará tempdb para almacenar partes de la tabla hash y las filas encontradas, y luego procesará solo partes de la tabla hash a la vez. Como con todo lo relacionado con el disco, esto es bastante lento.

En el caso óptimo, no causan E / S de disco, por lo que son insignificantes desde una perspectiva de rendimiento.

En general, en el peor de los casos, en realidad debería ser más rápido leer la misma cantidad de datos lógicos de las tablas unidas x, ya que es de una sola tabla desnormalizada debido a las lecturas de disco más pequeñas. Para leer la misma cantidad de datos físicos , podría haber una ligera sobrecarga.

Dado que el tiempo de consulta generalmente está dominado por los costos de E / S, y el tamaño de sus datos no cambia (menos una sobrecarga de fila muy minúscula) con la desnormalización, no hay una gran cantidad de beneficios al combinar tablas juntas. El tipo de desnormalización que tiende a aumentar el rendimiento, IME, es almacenar en caché los valores calculados en lugar de leer las 10,000 filas necesarias para calcularlos.

El orden en el que te unes a las tablas es extremadamente importante. Si tiene dos conjuntos de datos, intente construir la consulta de manera tal que el más pequeño se use primero para reducir la cantidad de datos en los que la consulta tiene que trabajar.

Para algunas bases de datos no importa, por ejemplo, MS SQL conoce el orden de unión adecuado la mayor parte del tiempo. Para algunos (como IBM Informix) el orden hace toda la diferencia.

Decidir si desnormalizar o normalizar es un proceso bastante sencillo cuando se considera la clase de complejidad de la unión. Por ejemplo, tiendo a diseñar mis bases de datos con normalización cuando las consultas son O (k log n) donde k es relativo a la magnitud de salida deseada.

Una manera fácil de desnormalizar y optimizar el rendimiento es pensar en cómo los cambios en su estructura normalizada afectan su estructura desnormalizada. Sin embargo, puede ser problemático, ya que puede requerir lógica transaccional para trabajar en una estructura desnormalizada.

El debate sobre la normalización y la desnormalización no va a terminar ya que los problemas son enormes. Hay muchos problemas en los que la solución natural requiere ambos enfoques.

Como regla general, siempre he almacenado una estructura normalizada y cachés desnormalizados que se pueden reconstruir. Finalmente, estos cachés me salvan el culo para resolver los futuros problemas de normalización.

Elaborando lo que otros han dicho,

Las uniones son solo productos cartesianos con brillo de labios. {1,2,3,4} X {1,2,3} nos daría 12 combinaciones (nXn = n ^ 2). Este conjunto calculado actúa como referencia sobre qué condiciones se aplican. El DBMS aplica las condiciones (como donde tanto la izquierda como la derecha son 2 o 3) para darnos las condiciones coincidentes. En realidad está más optimizado pero el problema es el mismo. Los cambios en el tamaño de los conjuntos aumentarían el tamaño del resultado exponencialmente. La cantidad de memoria y los ciclos de CPU consumidos se efectúan en términos exponenciales.

Cuando nos desnormalizamos, evitamos este cálculo por completo, piense en tener un adhesivo de color, adjunto a cada página de su libro. Puede inferir la información sin usar una referencia. La multa que pagamos es que estamos comprometiendo la esencia de DBMS (organización óptima de datos)