13 maneras de entender un JOIN en una base de datos relacional

 (justinjaffray.com)
4 puntos por GN⁺ 2023-07-04 | 1 comentarios | Compartir por WhatsApp
  • El inner join en una base de datos relacional va más allá de una simple sintaxis de SQL: la misma estructura puede interpretarse de distintas formas desde la consulta, los bucles anidados, el modelo lógico, la verificación de tipos y el álgebra
  • En tablas normalizadas, el join se vuelve la herramienta más práctica para seguir referencias y volver a combinar información almacenada sin duplicación
  • Desde la perspectiva de implementación, puede verse como recorrer pares de filas y conservar solo las combinaciones que cumplen la condición, o como seleccionar, desde los dominios de columnas, solo las combinaciones de valores presentes en ambas relaciones
  • En el modelo de programación, el join puede explicarse con flatMap, LATERAL de SQL, la resolución del problema N+1 en un ORM, la verificación de tipos basada en traits de Rust y andThen del mónada Set
  • Matemáticamente, los caminos en grafos, el modelo mínimo, la relación admisible más grande, la mínima cota superior de un orden parcial y el producto de anillo de expresiones relacionales revelan la misma propiedad del join

En datos normalizados, un join se convierte en una consulta

  • De la forma más práctica, un join puede verse como una operación para consultar un valor o adjuntar información redundante a datos existentes
  • El ejemplo parte de una forma de guardar user, country y country_code en una sola tabla
    • El mismo valor de country_code se repite para cada country, lo que genera duplicación
    • Si se trata de datos que cambian con frecuencia, hay que actualizar todas las ubicaciones al mismo tiempo, lo que aumenta los errores y la ineficiencia
  • En la forma normalizada, la relación entre country y country_code se separa en otra tabla, y la tabla de usuarios solo referencia country_id
  • Si se hace INNER JOIN entre users y countries por country_id, se recupera otra vez la forma original de user, country y country_code
  • A partir de aquí, la explicación asume joins implícitos basados en columnas con el mismo nombre, sin apegarse estrictamente a la sintaxis detallada de SQL

Perspectiva de implementación: joins recorriendo filas y columnas

  • Dado dos conjuntos R, S y un predicado p, el join recorre todos los r ∈ R y s ∈ S, y luego emite solo los casos en que p(r, s) es verdadero
    • Si el producto cartesiano de dos colecciones representa todas las conexiones posibles entre filas, el join es el subconjunto que satisface la condición
  • Viéndolo desde las columnas, el dominio de cada columna se toma como el conjunto de valores posibles, y se recorren combinaciones de valores de columnas
    • Si existen R(a, b) y S(b, c), se recorren los dominios de a, b y c
    • Solo se emite [a, b, c] cuando (a, b) está en R y (b, c) está en S

El join como realidades alternativas compatibles

  • El ejemplo de John y Sally explica el join como una forma de conservar solo las realidades compatibles cuando cada uno posee solo parte de la información
  • John conoce las posibles combinaciones entre su mascota y animales callejeros, y Sally también conoce las posibles combinaciones entre su mascota y animales callejeros
    • Si John tiene un dog y el animal callejero también es un dog, y Sally tiene un cat mientras el animal callejero es un mouse, eso no puede ser cierto al mismo tiempo
    • Esto se debe a que ambos tendrían que estar observando al mismo animal callejero
  • Si se hace join entre las dos tablas usando stray, solo permanecen las combinaciones de mascota de John, animal callejero y mascota de Sally que no se contradicen entre sí

El join en modelos de programación

  • flatMap es una función que crea un nuevo arreglo para cada elemento del arreglo original y luego concatena los resultados, y puede usarse para implementar un join
    • SELECT * FROM r INNER JOIN s ON p se expresa como r.flatMap(x => s.filter(y => p(x, y)))
    • La sintaxis LATERAL de algunas variantes de SQL transforma el join en una forma de flatMap
  • Si el lado derecho de LATERAL no hace referencia a columnas del lado izquierdo, es equivalente a un producto cartesiano
    • La decorrelación de consultas depende de eliminar esas referencias a columnas del lado derecho mediante reescrituras sucesivas
  • El problema N+1, común en ORM, también puede explicarse con joins
    • Si se ejecuta una consulta adicional por cada fila del conjunto de resultados, en bases de datos que usan conexiones como Postgres el costo fijo de cada consulta individual es alto
    • El resultado de pedirle a la base de datos “haz todas estas consultas” es un join como users INNER JOIN countries
    • En bases de datos in-process como Sqlite, este problema es menor

Caminos en grafos y modelos lógicos

  • Como una relación “relaciona” dos conjuntos, puede verse como un grafo
    • La tabla users conecta el conjunto de nombres de usuario con el conjunto de country_id
    • La relación que conecta country_id con códigos de país de dos letras también puede representarse como otro grafo
  • Si el conjunto de la derecha del primer grafo y el conjunto de la izquierda del segundo comparten el mismo conjunto de vértices, pueden verse como uno solo
  • Si se enumeran todos los caminos que van desde el conjunto izquierdo, pasan por el vértice del medio y llegan al conjunto derecho, se obtiene el join de las dos relaciones
  • En lógica formal, una relación se ve como un predicado, y un modelo es el conjunto de hechos que hace verdaderas a las oraciones
    • Si users(A, B) y countries(B, C, D) son verdaderos, entonces se establece la implicación de que Q(A, B, C, D) es verdadero
    • Puede haber múltiples modelos que satisfagan esta condición
    • Para obtener un resultado estándar, se elige el modelo mínimo entre los modelos que satisfacen la condición
    • Ese modelo mínimo es igual al resultado del join entre users y country

El join visto como verificación de tipos

  • Los sistemas de tipos estilo ML se parecen mucho a Prolog y Datalog, por lo que pueden expresarse de manera similar a un join
  • En el ejemplo con Rust, las relaciones se definen como traits
    • Users y CountryCode cumplen el papel de relaciones
    • Smudge, Sissel, Petee, Canada, UnitedStates, CA y US se definen como tipos concretos
  • Implementaciones de traits como (Smudge, Canada): Users y (Canada, CA): CountryCode corresponden a filas de la relación
  • Para que (A, B, C) esté incluido en el join, deben cumplirse (A, B): Users y (B, C): CountryCode
  • test::<(Smudge, _, CA)>() pasa la verificación de tipos, pero test::<(Smudge, _, US)>() falla porque (Canada, US): CountryCode no está implementado

El join como operación del mónada Set

  • El ejemplo de Some y None en JavaScript comienza uniendo records opcionales
    • Si dos records tienen el mismo country, se fusionan y devuelven Some
    • Si no son compatibles o no hay valor, devuelven None
  • andThen extrae el valor dentro del opcional y aplica la función de combinación
  • Si se mantiene la misma función combine pero se cambia el contenedor a Rel, se puede trabajar con conjuntos relacionales
    • Rel.map aplica una función a todas las filas
    • Rel.andThen concatena con flatMap las relaciones producidas desde cada fila
  • Si se ejecuta la misma función combine sobre la relación users y la relación countries, se obtiene el resultado del join con códigos de país añadidos a Smudge, Sissel y Petee

La relación admisible más grande y el join en órdenes parciales

  • Si una tercera relación T que contiene todas las columnas de dos relaciones R y S no inventa nueva información, se define como admisible
    • Si cualquier fila de T se restringe a las columnas de R, esa fila debe existir en R
    • Del mismo modo, si se restringe a las columnas de S, también debe existir en S
  • Por ejemplo, Smudge, Canada, US no es admisible
    • Si se mira solo country y country_code, se obtiene Canada, US, pero esa fila no existe en S
  • Incluso la relación vacía es admisible, pero la relación admisible más grande incluye Smudge-Canada-CA, Sissel-Canada-CA y Petee-United States-US
  • Esa relación admisible más grande es el join de las dos relaciones
  • Desde la perspectiva de orden parcial, R ≤ Q se define así
    • Q contiene todas las columnas de R
    • Si cada fila de Q se restringe a las columnas de R, se obtiene una fila de R
  • En este orden parcial existe la mínima cota superior R ∨ S de las relaciones R y S, y esa es la misma idea de join relacional

El join como producto de anillo

  • Las relaciones también pueden expresarse algebraicamente
    • Una fila puede representarse como un producto de pares columna-valor
    • Una relación puede representarse como una suma de varias filas
  • Por ejemplo, el término producto de user = Smudge y country_id = 1 representa una fila
  • Se agregan reglas para simplificar la expresión
    • Idempotence: [x = y][x = y] = [x = y]
    • Contradiction: [x = y][x = z] = 0 if y ≠ z
  • Si se multiplican la relación de usuarios R y la relación lookup de países S, y se desarrolla usando la distributividad y la conmutatividad, los términos contradictorios desaparecen y solo quedan los compatibles
  • La expresión restante es Smudge-1-Canada-CA, Sissel-1-Canada-CA, Petee-2-United States-US, que es exactamente el join de las dos relaciones
  • Esta forma también puede verse como una contracción de tensores

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-07-04
Comentarios de Hacker News

  • Empecé a pensar los joins en términos de dimensiones espaciales y se volvió mucho más fácil de entender
    Si cada dimensión se pone en una tabla separada, como Dim_X, Dim_Y, Dim_Z, y se unen con el mismo EntityId, puede verse como si construyeran la posición tridimensional de una entidad
    Para crear 3 dimensiones se necesitan al menos 2 inner joins, y también puede extenderse del mismo modo a dimensiones no espaciales como el tiempo
    Si no limitas un momento específico, termina siendo un reporte con todas las ubicaciones que una entidad tuvo a lo largo del tiempo
    Los otros tipos de join también se vuelven más fáciles de entender con esta variante una vez que fijas el concepto al punto de poder “rotar” mentalmente el esquema

    • Me recuerda a HyperDex. Usa hashing de valores basado en atributos en un hiperespacio multidimensional para sus índices
      https://dbdb.io/db/hyperdex
    • Esto parece más cercano a una hipernormalización de los datos. Normalmente, en BCNF lo dejarías como una tabla tipo EntityPosition(EntityId, X, Y, Z)
      Aun así, la parte de ensamblar piezas de varias dimensiones y manejar agregaciones me hace pensar en el mundo del data warehouse
    • Siempre me he preguntado por qué se usa sintaxis como JOIN, INNER JOIN. Me parece mucho más claro listar las tablas en FROM y escribir la condición de join en la cláusula WHERE como una ecuación
      Cuando se mezclan varios JOIN en una cláusula FROM compleja, se vuelve difícil de leer, y leer las condiciones equivalentes en WHERE se siente más intuitivo
    • Me pregunto si se puede entender que todos los joins son una variación del cross join

  • La perspectiva 0 es que un join es un operador del álgebra relacional
    https://en.m.wikipedia.org/wiki/Relational_algebra
    El natural join R ⋈ S es el conjunto de combinaciones de tuplas cuyos nombres de atributos compartidos coinciden, y es una operación relacional que corresponde al AND lógico
    ⋈ puede verse como un producto cartesiano que filtra con un predicado las filas que no deben entrar en el resultado, y gran parte de SQL se entiende bien desde esa perspectiva

    • En la interpretación funcional de la teoría relacional, el join es composición de funciones, así que sorprende que esa perspectiva no aparezca
    • La explicación de “bucles anidados sobre filas” ya contiene la perspectiva de producto cartesiano + predicado

  • Llevo varios días buscando material sobre la implementación de ejecución/planificación de consultas, pero no aparecen fácilmente recursos del lado de implementación sobre predicados, índices existentes o joins
    Los resultados de Google están contaminados con material de uso básico
    Hasta ahora solo encontré material del CMU Database Group, y es excelente

    • Hay un libro gratuito de 700 páginas sobre este tema: “Building Query Compilers”
      https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.p...
      También podría ayudar el curso de TUM “Database Systems on Modern CPU Architectures”, y el material de 2020 incluye las clases completas en video
      https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en
    • No sé si tendrá la profundidad que buscas, pero vale la pena revisar el resumen de optimización y la documentación del query planner de SQLite
      https://www.sqlite.org/optoverview.html
      https://www.sqlite.org/queryplanner.html
    • En estos casos suele recomendarse leer la documentación de Postgres y su código fuente. El código también se deja leer bastante bien
      https://www.postgresql.org/docs/current/planner-optimizer.ht...
    • Este es un tema bastante especializado, así que es difícil encontrar buenos libros de texto, y mucho depende de qué tan profundo quieras llegar y qué parte te interese
      La ejecución de consultas y la planificación de consultas son casi cosas separadas
      En cuanto a artículos sobre optimización de joins, sigo pensando que el artículo original de Selinger es el mejor
      https://courses.cs.duke.edu/compsci516/cps216/spring03/paper...
      No soporta outer joins y desde entonces aparecieron técnicas más eficientes, pero para quien vea optimizadores de la familia System R sigue siendo una lectura familiar
      El src/backend/optimizer/README de Postgres también tiene mucho contenido que es difícil encontrar en otros lados
      Las clases de Andy Pavlo en CMU son casi el único material en línea que explica esto, y el PDF de “Building Query Compilers”, aunque incompleto, reúne artículos clave de Moerkotte y otros, así que vale la pena si quieres implementar algo moderno
      Encontrar índices aplicables normalmente no es tan difícil si revisas si hay un sargable predicate, pero estimar selectividad es difícil, y estimar selectividad a través de joins está muy cerca de ser el problema más difícil dentro de un optimizador
      Por ejemplo, si tienes A=x AND B=y AND C=z y solo cuentas con información de selectividad/cardinalidad para los índices (A,B) y (B,C), no es nada trivial estimar la selectividad conjunta de las tres condiciones
      Incluso hay artículos que para resolver esto requieren un solucionador de “programación cónica de segundo orden”
    • Probé anteponer relational algebra al buscar query planning, y aun a simple vista aparecieron más resultados orientados a implementación

  • La 14.ª forma es el multiway join, también llamado “worst-case optimal join”, aunque el nombre no suena muy bien
    En vez de ir uniendo tablas de dos en dos y seguir generando resultados intermedios, significa unir 3 o más tablas a la vez sin resultados intermedios
    Hay una entrada de blog relacionada y un video corto en https://relational.ai/blog/dovetail-join, y el artículo original está en https://dl.acm.org/doi/pdf/10.1145/3180143
    Trabajo en RelationalAI, y nosotros junto con algunas otras startups de bases de datos estamos llevando al mercado este nuevo algoritmo de join que se ha investigado por unos 10 años en la academia

    • La introducción de Justin a WCOJ también está bastante bien
      https://justinjaffray.com/a-gentle-ish-introduction-to-worst...
    • Si niegas la entrada, es decir, la conviertes en el complemento del conjunto, el AND del join se vuelve NOR, y Tetris aprovecha eso
      El límite en el peor caso no se vuelve más estricto que en un WCOJ sin estado/streaming, pero los datos reales suelen tener certificados box mucho más pequeños
      No he visto si dovetail join soporta consultas recursivas, o sea, datalog arbitrario donde solo se especifica la relación de salida y el motor resuelve por su cuenta las relaciones intermedias
      Me da curiosidad si soporta ese tipo de consultas

  • Debería haber más textos como este, que muestran las sutilezas del modelo relacional sobre todo a desarrolladores a nivel de aplicación
    La explicación y exploración desde la perspectiva de programación funcional también es concisa y convincente

  • Parece que se perdió otra oportunidad de enseñar el problema N+1
    Hacer join contra un índice no clusterizado sigue siendo N+1; simplemente es N+1 en disco en vez de N+1 yendo y viniendo entre red y disco

    • Suena como “tenía que cubrir el problema X que me interesa, y por eso está bien que el texto se extienda”

  • Un inner join es un producto cartesiano con una condición

    • Hay una gran diferencia de rendimiento entre crear el producto cartesiano y luego filtrar por la condición, y generar la condición directamente
      Un inner join con condición de igualdad genera la condición directamente, mientras que una condición de join por desigualdad sí requiere evaluación real

  • Buena explicación. Eso de que “la forma correcta es normalizar las tablas” es cierto en bases de datos transaccionales, pero en data warehouses cierto grado de desnormalización es ampliamente aceptado

  • El ejemplo de normalización me recordó cuando antes diseñaba tablas pensando que las claves primarias numéricas eran más rápidas que las cadenas
    Eso terminaba creando id sin significado, y hacía falta un join para obtener el valor único que realmente querías
    Un día me di cuenta de que si usabas la misma clave única en dos tablas podías reducir joins, y aunque era algo simple, resultó muy efectivo

    • Aun así, me gusta tener un campo id único por tabla. Ayuda con el logging y evita tener que preocuparse por la clave “real” compuesta por varios campos
      En cambio, pongo índices únicos sobre los valores de cadena y, más importante todavía, aplico ahí las restricciones de integridad
      Una tabla llena de cadenas con significado es mucho más fácil de leer que una llena de id numéricos o UUID