13 maneiras de entender o JOIN em bancos de dados relacionais

 (justinjaffray.com)
4 pontos por GN⁺ 2023-07-04 | 1 comentários | Compartilhar no WhatsApp
  • O inner join em bancos de dados relacionais vai além de uma simples sintaxe SQL: a mesma estrutura pode ser interpretada de formas diferentes sob as perspectivas de consulta, laço aninhado, modelo lógico, verificação de tipos e álgebra
  • Em tabelas normalizadas, o join se torna a ferramenta mais prática para recombinar informações armazenadas sem duplicação seguindo referências
  • Do ponto de vista de implementação, ele pode ser visto como percorrer pares de linhas e manter apenas as combinações que satisfazem a condição, ou como selecionar apenas as combinações de valores que existem em ambas as relações dentro dos domínios das colunas
  • No modelo de programação, é possível explicar o join com flatMap, LATERAL no SQL, a solução do problema N+1 em ORMs, verificação de tipos baseada em traits no Rust e andThen da mônada Set
  • Matematicamente, caminhos em grafos, modelo mínimo, maior relação admissível, menor limite superior em ordens parciais e o produto em anel de relações revelam a mesma propriedade do join

Em dados normalizados, join vira consulta

  • De forma mais prática, o join pode ser visto como uma operação de consultar um valor ou anexar informações redundantes aos dados existentes
  • O exemplo começa com uma forma de armazenar user, country e country_code em uma única tabela
    • O valor country_code se repete para cada country, gerando duplicação
    • Se os valores mudam com frequência, é preciso atualizar todos os lugares ao mesmo tempo, aumentando erros e ineficiência
  • Na forma normalizada, a relação entre country e country_code é separada em outra tabela, e a tabela de usuários referencia apenas country_id
  • Ao fazer INNER JOIN entre users e countries por country_id, recupera-se novamente o formato original com user, country e country_code
  • A explicação a seguir assume joins implícitos com base em colunas de mesmo nome, sem se prender rigidamente aos detalhes da sintaxe SQL

Perspectiva de implementação: join percorrendo linhas e colunas

  • Dado dois conjuntos R, S e um predicado p, o join percorre todos os r ∈ R e s ∈ S, emitindo apenas os casos em que p(r, s) é verdadeiro
    • Se o produto cartesiano das duas coleções representa todas as ligações possíveis entre linhas, então o join é o subconjunto que satisfaz a condição
  • Olhando pelas colunas, cada domínio de coluna pode ser tratado como o conjunto de valores possíveis, e então percorrem-se as combinações desses valores
    • Se existem R(a, b) e S(b, c), percorrem-se os domínios de a, b e c
    • Só se emite [a, b, c] quando (a, b) pertence a R e (b, c) pertence a S

Join como realidades alternativas compatíveis

  • O exemplo de John e Sally explica o join como uma forma de manter apenas as realidades compatíveis quando cada pessoa conhece só parte da informação
  • John conhece as combinações possíveis entre seu pet e um animal stray, e Sally também conhece as combinações possíveis entre seu pet e esse animal stray
    • Se John tem um dog e o stray também é um dog, e Sally tem um cat enquanto o stray é um mouse, essas situações não podem ser verdade ao mesmo tempo
    • Isso acontece porque os dois precisam estar observando o mesmo stray
  • Ao fazer join das duas tabelas por stray, restam apenas as combinações de pet de John · stray · pet de Sally que não se contradizem

Join em modelos de programação

  • flatMap é uma função que cria um novo array para cada elemento do array original e concatena os resultados, e pode ser usada para implementar join
    • SELECT * FROM r INNER JOIN s ON p pode ser expresso como r.flatMap(x => s.filter(y => p(x, y)))
    • A sintaxe LATERAL em algumas variantes de SQL transforma o join em uma forma de flatMap
  • Se o lado direito de LATERAL não referencia colunas do lado esquerdo, ele é equivalente a um produto cartesiano
    • A decorrelation de consultas depende de remover referências do lado direito por meio de reescritas sucessivas
  • O problema N+1 comum em ORMs também pode ser explicado com join
    • Quando se executa uma consulta extra para cada linha do conjunto de resultados, bancos como o Postgres, que usam conexão, pagam um custo fixo alto por consulta individual
    • O resultado de pedir ao banco de dados “faça todas essas consultas” é um join como users INNER JOIN countries
    • Em bancos in-process como o Sqlite, esse problema é menor

Caminhos em grafos e modelos lógicos

  • Como uma relação “relaciona” dois conjuntos, ela pode ser vista como um grafo
    • A tabela users conecta o conjunto de nomes de usuário ao conjunto de country_id
    • A relação que conecta country_id ao código de país de duas letras também pode ser representada como outro grafo
  • Se o conjunto da direita do primeiro grafo e o conjunto da esquerda do segundo compartilham o mesmo conjunto de vértices, eles podem ser vistos como um só
  • Enumerar todos os caminhos que saem do conjunto da esquerda, passam pelo vértice do meio e chegam ao conjunto da direita produz o join das duas relações
  • Em lógica formal, relações podem ser vistas como predicados, e um modelo é o conjunto de fatos que torna verdadeiro um conjunto de sentenças
    • Se users(A, B) e countries(B, C, D) são verdadeiros, então vale a implicação de que Q(A, B, C, D) também é verdadeiro
    • Pode haver vários modelos que satisfaçam essa condição
    • Para obter o resultado padrão, escolhe-se o menor modelo entre os que satisfazem a condição
    • Esse menor modelo é igual ao resultado do join entre users e country

Join como verificação de tipos

  • Sistemas de tipos no estilo ML se parecem bastante com Prolog e Datalog, então podem expressar algo semelhante a joins
  • No exemplo em Rust, as relações são definidas como traits
    • Users e CountryCode fazem o papel de relações
    • Smudge, Sissel, Petee, Canada, UnitedStates, CA, US são definidos como tipos concretos
  • Implementações de trait como (Smudge, Canada): Users e (Canada, CA): CountryCode correspondem às linhas da relação
  • Para que (A, B, C) pertença ao join, é preciso que (A, B): Users e (B, C): CountryCode
  • test::<(Smudge, _, CA)>() passa na verificação de tipos, mas test::<(Smudge, _, US)>() falha porque (Canada, US): CountryCode não está implementado

Join como operação da mônada Set

  • O exemplo em JavaScript com Some e None começa com a ideia de combinar registros opcionais
    • Se dois registros têm o mesmo country, eles são mesclados e retornam Some
    • Se são incompatíveis ou não há valor, retorna-se None
  • andThen extrai o valor opcional interno e aplica a função de combinação
  • Mantendo a mesma função combine e trocando o contêiner para Rel, passa-se a operar sobre conjuntos de relações
    • Rel.map aplica uma função a todas as linhas
    • Rel.andThen concatena com flatMap as relações produzidas a partir de cada linha
  • Ao executar a mesma combine sobre a relação users e a relação countries, obtém-se o resultado do join com códigos de país anexados a Smudge, Sissel e Petee

A maior relação admissível e o join em ordens parciais

  • Define-se que uma terceira relação T, com todas as colunas de R e S, é admissível se ela não inventa informação nova
    • Quando qualquer linha de T é restringida às colunas de R, essa linha precisa existir em R
    • Da mesma forma, ao restringi-la às colunas de S, ela também precisa existir em S
  • Por exemplo, Smudge, Canada, US não é admissível
    • Considerando apenas country e country_code, isso vira Canada, US, que não é uma linha de S
  • Até a relação vazia é admissível, mas a maior relação admissível contém Smudge-Canada-CA, Sissel-Canada-CA, Petee-United States-US
  • Essa maior relação admissível é o join entre as duas relações
  • Na perspectiva de ordem parcial, define-se R ≤ Q assim:
    • Q contém todas as colunas de R
    • Ao restringir cada linha de Q às colunas de R, obtém-se uma linha de R
  • Nessa ordem parcial, existe o menor limite superior R ∨ S de R e S, e ele tem o mesmo significado do join relacional

Join como produto em anel

  • Relações também podem ser expressas algebricamente
    • Uma linha é representada como um produto de pares coluna-valor
    • Uma relação é representada como uma soma de várias linhas
  • Por exemplo, o termo formado por user = Smudge e country_id = 1 representa uma linha
  • São adicionadas regras para simplificar a expressão
    • Idempotence: [x = y][x = y] = [x = y]
    • Contradiction: [x = y][x = z] = 0 if y ≠ z
  • Ao multiplicar a relação de usuários R pela relação de lookup de países S e expandir com distributividade e comutatividade, os termos contraditórios desaparecem e restam apenas os compatíveis
  • A expressão restante é Smudge-1-Canada-CA, Sissel-1-Canada-CA, Petee-2-United States-US, exatamente o join entre as duas relações
  • Essa abordagem também pode ser vista como tensor contraction

Leituras relacionadas

1 comentários

 
GN⁺ 2023-07-04
Comentários do Hacker News

  • Ficou muito mais fácil entender joins quando comecei a pensar neles em termos de dimensão espacial
    Se cada dimensão, como Dim_X, Dim_Y, Dim_Z, ficar em uma tabela separada e for ligada pelo mesmo EntityId, dá para ver isso como a composição da posição tridimensional de uma entidade
    Para montar 3 dimensões, são necessários pelo menos 2 inner joins, e também dá para expandir da mesma forma para dimensões não espaciais, como tempo
    Se você não restringir um instante específico, isso vira um relatório com todas as posições que uma entidade já ocupou ao longo do tempo
    Outros tipos de join também ficam mais fáceis de entender nessa variação quando você internaliza o conceito a ponto de conseguir “girar” o esquema na cabeça

    • Lembrou o HyperDex. Ele usa uma abordagem de hash de valores em um hiperespaço multidimensional baseado em atributos para indexação
      https://dbdb.io/db/hyperdex
    • Isso parece mais próximo de uma hipernormalização dos dados. Normalmente, em BCNF, eu deixaria tudo em uma tabela como EntityPosition(EntityId, X, Y, Z)
      Ainda assim, essa ideia de juntar pedaços de várias dimensões e lidar com agregações lembra data warehouse
    • Sempre me pergunto por que usar sintaxe como JOIN, INNER JOIN. Listar as tabelas em FROM e colocar as condições de join no WHERE como equações parece bem mais claro
      Quando há vários JOIN misturados em um FROM complexo, fica difícil de ler, e ler condições de igualdade no WHERE parece mais intuitivo
    • Fiquei na dúvida se o certo é entender que todo join é uma variação de cross join

  • O ponto de vista número 0 é que “join é um operador da álgebra relacional”
    https://en.m.wikipedia.org/wiki/Relational_algebra
    O natural join R ⋈ S é o conjunto de combinações de tuplas com nomes de atributos em comum e corresponde, no plano lógico, ao operador relacional equivalente a AND
    Dá para ver ⋈ como um produto cartesiano no qual um predicado filtra as linhas que não devem entrar no resultado, e boa parte do SQL fica bem mais compreensível sob essa ótica

    • Na interpretação funcional da teoria relacional, join é composição de funções, então é curioso essa perspectiva não ter aparecido
    • A explicação de “loops aninhados sobre linhas” já contém a perspectiva de produto cartesiano + predicado

  • Faz dias que estou procurando material sobre implementação de execução/planejamento de consultas, mas quase não acho conteúdo voltado para implementação de predicados, índices existentes e joins
    Os resultados do Google estão poluídos por material de uso básico
    Até agora, só encontrei o material do CMU Database Group, e ele é excelente

    • Há um livro gratuito de 700 páginas sobre isso: “Building Query Compilers”
      https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.p...
      A disciplina “Database Systems on Modern CPU Architectures”, da TUM, também pode ajudar, e o material de 2020 inclui a série completa de videoaulas
      https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en
    • Não sei se vai na profundidade que você quer, mas vale ver a visão geral de otimização e a documentação do query planner do SQLite
      https://www.sqlite.org/optoverview.html
      https://www.sqlite.org/queryplanner.html
    • Nesses casos, muita gente recomenda ler a documentação do Postgres e o código-fonte. O código também é relativamente agradável de ler
      https://www.postgresql.org/docs/current/planner-optimizer.ht...
    • Esse é um tema bem especializado, então é difícil encontrar um bom livro-texto, e tudo depende de quão fundo você quer ir e de qual parte te interessa
      Execução de consultas e planejamento de consultas são, na prática, coisas quase separadas
      Em otimização de joins, eu ainda acho que o artigo original do Selinger continua sendo o melhor
      https://courses.cs.duke.edu/compsci516/cps216/spring03/paper...
      Ele não dá suporte a outer joins e técnicas mais eficientes surgiram depois, mas para quem estuda otimizadores da linha do System R ele ainda é uma leitura familiar
      O src/backend/optimizer/README do Postgres também tem muito conteúdo que é difícil encontrar em outros lugares
      As aulas do Andy Pavlo, da CMU, são quase o único material online que realmente explica isso, e o PDF “Building Query Compilers”, embora incompleto, reúne artigos fundamentais de Moerkotte e outros, então vale a pena para quem quer implementar algo moderno
      Encontrar índices aplicáveis em geral não é tão difícil, porque normalmente basta verificar se há um sargable predicate, mas estimar seletividade é difícil, e estimar seletividade após joins está entre os problemas mais difíceis de um otimizador
      Por exemplo, se existe A=x AND B=y AND C=z e você só tem informações de seletividade/cardinalidade dos índices (A,B) e (B,C), estimar a seletividade conjunta das três condições está longe de ser trivial
      Há até artigos que propõem resolver isso com um solucionador de “programação de cone de segunda ordem”
    • Colocar relational algebra antes do termo de busca e pesquisar query planning parece trazer bem mais resultados voltados à implementação, pelo menos à primeira vista

  • A 14ª forma é o multi-join, também chamado de “join ótimo no pior caso”, mas o nome não é lá muito bom
    Em vez de juntar as tabelas de duas em duas e continuar produzindo resultados intermediários, isso significa juntar 3 ou mais tabelas ao mesmo tempo, sem resultados intermediários
    Há um post de blog relacionado e um vídeo curto em https://relational.ai/blog/dovetail-join, e o artigo original está em https://dl.acm.org/doi/pdf/10.1145/3180143
    Trabalho na RelationalAI, e nós e algumas outras empresas novas de banco de dados estamos levando ao mercado esse novo algoritmo de join, pesquisado na academia por cerca de 10 anos

    • O texto de introdução do Justin sobre WCOJ também é bem bom
      https://justinjaffray.com/a-gentle-ish-introduction-to-worst...
    • Se você negar a entrada, ou seja, convertê-la no complemento do conjunto, o AND do join vira NOR, e o Tetris explora isso
      O limite do pior caso não fica mais apertado do que no WCOJ sem estado/streaming, mas dados reais frequentemente têm certificados de caixa muito menores
      Não vi se o dovetail join suporta consultas recursivas, ou seja, datalog arbitrário em que só a relação de saída é especificada e as relações intermediárias são tratadas pelo motor
      Fico curioso se esse tipo de consulta é suportado

  • Precisamos de mais textos como este, que mostrem as sutilezas do modelo relacional principalmente para desenvolvedores no nível de aplicação
    A explicação e a exploração pela ótica da programação funcional também são concisas e convincentes

  • Parece que perderam outra oportunidade de ensinar o problema N+1
    Fazer join com um índice não clusterizado ainda é N+1; só não é o N+1 entre rede e disco, e sim o N+1 dentro do disco

    • Soa como “eles deveriam ter abordado o problema X que me interessa, e tudo bem se o texto ficasse maior por isso”

  • Um inner join é um produto cartesiano com condição

    • Há uma grande diferença de desempenho entre gerar o produto cartesiano e depois filtrar pela condição, e gerar a condição diretamente
      Inner joins com condição de igualdade geram a condição diretamente, enquanto condições de join por desigualdade exigem avaliação de fato

  • Boa explicação. A afirmação de que “a forma correta é normalizar as tabelas” está certa em bancos de dados transacionais, mas em data warehouses algum grau de desnormalização é amplamente aceito

  • O exemplo de normalização me fez lembrar da época em que eu projetava tabelas achando que chaves primárias numéricas eram mais rápidas que strings
    Isso acabava criando id sem significado, e era preciso fazer join para obter o valor único que realmente se queria
    Um dia percebi que, se duas tabelas usassem a mesma chave única, dava para reduzir joins; era simples, mas teve bastante efeito

    • Ainda assim, gosto de manter um campo id único por tabela. Ajuda no logging e evita ter de se preocupar com a chave “real” composta por vários campos
      Em vez disso, coloco um índice único nos valores de string e, mais importante, aplico as restrições de integridade neles
      Tabelas cheias de strings com significado são muito mais fáceis de ler do que tabelas cheias de id numéricos ou UUIDs