database - tradicional - que es una base de datos en programacion

¿Cuándo y por qué son caras las bases de datos? (7)

Estoy investigando en bases de datos y observando algunas limitaciones de los DB relacionales.

Me estoy dando cuenta de que unir mesas grandes es muy caro, pero no estoy completamente seguro de por qué. ¿Qué debe 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. Sé dónde encontrar eso ya.

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

¿Desnormalización para mejorar el rendimiento? Suena convincente, pero no retiene el agua.

Chris Date, quien junto con el 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 se incorporó más tarde a la edición seis de Introduction to Database Systems , 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. Impreso en 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 fallan en pagar 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 combinaciones que incluyen claves seleccionadas correctamente con índices correctamente configurados son baratas, no caras, porque permiten una poda significativa del resultado antes de que se materialicen las filas.

La materialización del resultado implica lecturas en disco que son el aspecto más costoso del ejercicio en 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 las comparaciones de unión, mitigando el costo de las combinaciones de varias columnas y reduciendo radicalmente el costo de las combinaciones que involucran comparaciones de cadenas. No solo caben mucho más en el caché, sino que hay mucho menos que leer en el disco.

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 los í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) configuran índices.

Es importante comprender que las exploraciones de tablas (el examen de cada fila de una tabla en el curso de la creación de una combinación) son poco frecuentes en la práctica. Un optimizador de consultas elegirá una exploración de tabla solo cuando se cumpla una o más de las siguientes.

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?
Se requiere un tipo de coerción antes de poder comparar las columnas (¿WTF?! Arreglarlo o ir a casa) VEA LAS NOTAS FINALES DE 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 una operación incorrecta , ser forzado a la E / S del 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" está precomputada y los índices se han aplicado con sensatez, sigue existiendo una penalización significativa. La normalización para precomputar una combinación, a pesar de las anomalías de actualización que conlleva, es un compromiso con una combinación en particular. Si necesita una unión diferente , ese compromiso le va a costar mucho .

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

Para todos ustedes que trabajan en sistemas de facturación o generadores de correo no deseado (se avergüenza de usted) y se ponen manos a la obra con indignación en el teclado para decirme que saben a ciencia cierta que la desnormalización es más rápida, lo siento, pero vive en uno de los programas especiales. casos - específicamente, el caso donde procesa todos los datos, en orden. No es un caso general, y usted está justificado en su estrategia.

No estás justificado en generalizarlo falsamente. Consulte el final de la sección de 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 algunos lipgloss.

Qué carga de bollocks. Las restricciones se aplican lo antes posible, primero las más restrictivas. Has leído la teoría, pero no la has entendido. Las combinaciones se tratan como "productos cartesianos a los que se aplican los predicados" únicamente mediante 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 manera de obtener el optimizador para producir un producto cartesiano es no proporcionar un predicado: SELECT * FROM A,B

Notas

David Aldridge proporciona alguna información adicional importante.

De hecho, existe una variedad de otras estrategias además de los índices y los 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 una clave externa, indícela, de modo que el optimizador tenga disponible una estrategia de índice.

Solía ser más inteligente que el optimizador de 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. Se me pide que sea menos altanero y se me recuerda que las matemáticas no mienten. Esto es cierto, pero no todas las implicaciones de los modelos matemáticos deben tomarse literalmente. Las raíces cuadradas de los números negativos son muy útiles si evitas examinar cuidadosamente su absurdo (haz un juego allí) y asegúrate de cancelarlas todas antes de intentar interpretar tu ecuación.

La razón por la que respondí tan salvajemente fue que la declaración en su forma actual 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 con valor de relación. Con un predicado vacío producirá un producto cartesiano, y verificar que lo haga es una comprobació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 un valor práctico fuera del aula.

Llamé a 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, simplificada deliberadamente para una manipulación conveniente.

El límite para la selección de una estrategia de combinación de exploración de tablas 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 del nodo del á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 mayoritariamente hecha de tiempo de configuración, y la forma de la curva significa que no se obtiene una recompensa (en comparación con una búsqueda lineal) hasta que n esté en 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 procesarlo en gran parte o por completo, entonces la precomputación de una unión puede ser muy útil.

También puede averiguar las rutas de acceso que normalmente utiliza su operación y calcular previamente todas las combinaciones para esas rutas de acceso. Esta es la premisa detrás de los almacenes de datos, o al menos es cuando están compuestas 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 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 conflicto 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). Podría ser más rápido para las ejecuciones de facturación, pero si lo hace, obtendrá anomalías de actualización. ¿Alguna vez intentaste 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 para los almacenes de datos. Las ganancias de rendimiento mucho mayores se derivan de los valores acumulados precomputados: totales mensuales, ese tipo de cosas. Siempre se trata de reducir el conjunto de trabajo.

Problema de ADO.NET con los desajustes de tipo

Supongamos que tiene una tabla de 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 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 ocurre de manera implícita, pero diga adiós a la indexación y buena suerte al descubrir por qué.

"Cuenta los golpes de disco" (Rick James)

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

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

Comentario del autor original: Los motores de base 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, puede ser malinterpretado, ya que implica que las uniones son necesariamente problemáticas en grandes cantidades de datos. Esto daría lugar a una mala toma de decisiones por parte de desarrolladores inexpertos.

Creo que toda la pregunta se basa en una premisa falsa. Unirse en tablas grandes no es necesariamente caro. De hecho, hacer uniones eficientemente es una de las razones principales 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 cambio, escriba la consulta de manera que solo se utilicen las filas importantes de cada tabla y el conjunto real mantenido por la unión sigue siendo más pequeño.

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 finales. Además, en las consultas grandes con muchas uniones, normalmente se desea comenzar con los conjuntos de tablas más pequeños y trabajar hasta llegar a los grandes, de modo que el conjunto guardado en la memoria permanezca lo más pequeño posible durante el mayor tiempo posible.

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

Decidir si denormalizar 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 cómo los cambios en su estructura normalizada afectan su estructura desnormalizada. Sin embargo, puede ser problemático, ya que puede requerir que la lógica transaccional funcione en una estructura desnormalizada.

El debate por la normalización y la desnormalización no va a terminar porque los problemas son enormes. Hay muchos problemas donde 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 salvan mi trasero para resolver los futuros problemas de normalización.

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

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

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

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

Acerca de la única sobrecarga con una unión proviene de averiguar 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 combinación incorrecto (debido a estadísticas inexactas, índices inadecuados, o simplemente un error del optimizador o un caso de borde) puede afectar drásticamente los tiempos de consulta.

Una combinación de bucle es mucho más barata para (al menos 1) pequeño conjunto de datos.
Una combinación de combinación requiere un tipo de ambos conjuntos de datos primero. Sin embargo, si se une en una columna indexada, entonces el índice ya está ordenado y no es necesario realizar ningún trabajo adicional. De lo contrario, hay algo de sobrecarga de CPU y memoria en la clasificación.
La unión hash requiere tanto memoria (para almacenar la tabla hash) como CPU (para construir el hash). De nuevo, 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 todas las cosas del disco, esto es bastante lento.

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

En definitiva, en el peor de los casos, en realidad debería ser más rápido leer la misma cantidad de datos lógicos de x tablas unidas, como lo 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 se puede obtener un beneficio enorme simplemente al combinar las tablas. El tipo de desnormalización que tiende a aumentar el rendimiento, IME, es el almacenamiento en caché de valores calculados en lugar de leer las 10,000 filas requeridas para calcularlos.

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

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.

Elaborando lo que otros han dicho,

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

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

Lo que la mayoría de los comentaristas no notan es la amplia gama de metodologías de unión disponibles en un RDBMS complejo, y los denormalizadores invariablemente pasan por alto el mayor costo de mantener los datos desnormalizados. No todas las uniones se basan en índices, y las bases de datos tienen una gran cantidad de algoritmos y metodologías optimizados para la unión que pretenden reducir los costos de la unión.

En cualquier caso, el costo de una unión depende de su tipo y algunos otros factores. No tiene que ser caro en absoluto - algunos ejemplos.

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

Las bases de datos están diseñadas para unirse, y son muy flexibles en la forma en que lo hacen y, en general, tienen un gran rendimiento, a menos que el mecanismo de unión sea incorrecto.