Criando um motor de Datalog interativo com Rust

 (github.com/frankmcsherry)
1 pontos por GN⁺ 2025-06-16 | 1 comentários | Compartilhar no WhatsApp
  • O experimento datatoad, um shell de Datalog interativo baseado em Rust, começou a partir das limitações de usabilidade e desempenho reveladas em um workshop de programação lógica sobre ferramentas de Datalog
  • O datatoad busca uma estrutura que permita adicionar regras durante a execução e continuar derivando novos fatos, reduzindo o custo de tratamento de duplicatas no conjunto de fatos com armazenamento columnar e camadas LSM
  • A avaliação de regras transforma o corpo do Datalog em um problema de join, separando avaliação completa e avaliação incremental conforme o estado stable, para evitar joins stable-stable já calculados
  • Em experimentos com o dataset Graspan, apenas com reescrita manual de regras e introdução de relações intermediárias, a análise de aliasing caiu de 736,34 segundos e 50,13 GB para 119,34 segundos e 5,32 GB
  • Os trabalhos seguintes avançam para otimização de plano de join com e-graph, layered trie, representação em bytes de largura fixa, spill para disco, avaliação distribuída, streaming join e demand transform

O problema que o datatoad quer resolver

  • Em um workshop de programação lógica no fim de semana do Memorial Day, ficou evidente o desconforto com as ferramentas de Datalog para análise de programas, o que levou à tentativa de criar uma implementação de Datalog simples, útil e rápida
  • O alvo da implementação não é um executor estático de exemplos, mas um shell de Datalog interativo
    • É possível carregar grandes volumes de fatos
    • É possível adicionar novas regras durante a execução
    • Os resultados das regras adicionadas continuam sendo refletidos no estado existente
  • O código pode ser acompanhado no repositório do datatoad
  • O datafrog existente fornece os algoritmos centrais de um motor de Datalog, mas exige que o usuário faça a integração manualmente; por isso, o datatoad reorganiza as mesmas ideias de uma forma mais fácil de usar
  • No exemplo de nulabilidade do grafo de dataflow httpd, o datatoad levou 8,3 segundos com dados Vec<String> e consultas não compiladas, cerca de 4 vezes mais lento do que os aproximadamente 2 segundos do exemplo em datafrog com dados (u32, u32)
  • No problema de reachability, ele produziu o mesmo número de tuplas de saída que a implementação em datafrog, mas a verificação geral de corretude ainda não foi concluída

Modelo de Datalog e estrutura do shell

  • Datalog é uma linguagem em que se escrevem regras lógicas simples e se derivam todos os fatos alcançáveis a partir delas
  • Uma regra é composta por head e body
    • Exemplo: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c).
    • tri e edge são relações, e a, b, c são variáveis
    • As variáveis que aparecem no head também precisam estar no body
  • Fatos são tratados como regras com body vazio
    • Exemplo: edge(1, 2) :- .
    • É possível usar vários heads para escrever vários fatos de uma vez
  • Devido à monotonicidade do Datalog, mesmo que se adicionem regras ou fatos, o conjunto de fatos verdadeiros não diminui, e o mesmo conjunto de regras de entrada chega ao mesmo resultado independentemente da ordem das regras
  • Na representação em Rust, três estruturas são centrais: Rule, Atom e Term
    • Rule { head: Vec<Atom>, body: Vec<Atom> }
    • Atom { name: String, terms: Vec<Term> }
    • Term::Var(String) ou Term::Lit(String)
  • Para armazenar literais, usa-se Vec<u8> em vez de String
    • As propriedades necessárias são igualdade entre literais e uma ordem de classificação arbitrária
    • Se os bytes representam String, (u32, u32) ou outro significado, isso fica em aberto para o usuário
  • O estado do interpretador guarda regras e fatos juntos
    • rules: Vec<Rule>
    • facts: facts::Facts
  • Quando o shell faz o parsing de uma linha de entrada como Datalog, ele chama State::extend e State::update, e o comando .list exibe o nome de cada relação e a quantidade de fatos

Parsing e armazenamento de fatos

  • O parser está em parse.rs e usa uma forma trazida da gramática do Soufflé
  • Variáveis começam com ?
  • Os tokens se limitam a ., ,, (, ), :-, ?, e o restante do texto é tratado como nome de atom ou de term
  • O tokenizer remove espaços em branco e troca :- por ← para fazer a leitura como um símbolo único
  • O parsing de regras lê os atoms do head até o turnstile e os atoms do body até o ponto final
    • Um atom é composto por nome, parêntese esquerdo, lista de terms e parêntese direito
    • Um term é variável se houver ?; caso contrário, é um literal
  • Regras inválidas retornam None, e no momento ainda não informam em detalhe qual parte estava errada
  • Para adicionar regras negativas seria necessário um token Exclamation, mas isso ainda não é tratado

Ciclo de vida do conjunto de fatos

  • Um armazenamento simples em Vec<Vec<String>> cria alocações aninhadas e é desfavorável para o gerenciamento de memória
  • O datatoad usa columnar para converter tipos Rust em um layout plano com poucas alocações lineares
    • Os bytes das strings, os limites das strings e os limites dos fatos são armazenados em arrays separados
  • FactContainer encapsula uma lista de fatos ordenada e sem duplicatas, sugerindo por meio de um wrapper type a invariante de ordenação e remoção de duplicatas
  • Como um contêiner colunar é, na prática, append-only e não serve bem para alterações intermediárias, a adição de novos fatos usa uma forma de log-structured merge-tree (LSM)
    • FactLSM { layers: Vec<FactContainer> }
    • As camadas são gerenciadas para que seus tamanhos cresçam geometricamente
    • Camadas com tamanho dentro de 2 vezes uma da outra são mescladas para manter a ordenação e a remoção de duplicatas
  • FactBuilder mantém juntos uma área active, que pode estar desordenada e conter duplicatas, e layers, que são ordenadas e sem duplicatas
  • Os fatos de cada relação passam por três estágios
    • to_add: fatos que acabaram de chegar, mas ainda não tiveram sua novidade verificada
    • recent: fatos distintos que ainda precisam ser processados
    • stable: fatos distintos que já foram totalmente processados
  • FactSet::advance move recent para stable e remove de to_add os fatos que já existem em stable, formando um novo recent

A avaliação de regras é um problema de join

  • O body de uma regra Datalog pode ser visto como um equi-join de banco de dados relacional
  • O exemplo da regra de triângulo é o seguinte
    • tri(?a, ?b, ?c) :- edge(?a, ?b), edge(?b, ?c), edge(?a, ?c).
  • Enumerar diretamente todas as atribuições de variáveis é excessivo mesmo quando finito, então a estratégia é ordenar pelos key columns das variáveis em comum e fazer merge
  • A implementação reduz o body da direita para a esquerda
    • Faz o join das duas últimas relações para criar uma relação intermediária e depois faz join novamente com a relação à esquerda
    • Se houver apenas um atom no body, ele apenas o transforma para o formato do head
  • JoinPlan contém as seguintes informações
    • bodys, que reorganiza e filtra os body atoms para adequá-los ao join
    • joins, que guarda a key arity e a projeção de saída de cada join intermediário
    • heads, que representa coordenadas ou literais a inserir no head atom
    • A aridade do join final que gera o head
  • O plano atual é um right-linear join plan simples
  • Ao criar o JoinPlan, usam-se as posições de ocorrência mais à esquerda e mais à direita de cada variável para decidir até quando preservar cada valor de variável, separando as colunas dos body atoms em colunas dead, key e value
  • A função principal é implement_plan(rule, plan, pos, stable, facts)
    • Quando uma nova regra é adicionada, ela começa sobre todos os fatos com stable = true
    • Na aplicação repetida de regras existentes, calcula apenas novas derivações com stable = false

Joins incrementais e merge join

  • O join é bilinear, então pode ser decomposto assim
    • (A + a) ⋈ (B + b) = A ⋈ B + A ⋈ b + a ⋈ B + a ⋈ b
  • A ⋈ B, já produzido entre partes stable, não precisa ser recalculado
  • Se só forem necessárias novas derivações, basta executar três joins
    • A ⋈ b
    • a ⋈ B
    • a ⋈ b
  • join_with inclui ou exclui o join stable-stable conforme a flag stable
  • O join real é um merge join que percorre sequencialmente duas entradas ordenadas
    • Se as chaves forem iguais, chama action para todas as combinações daquela chave
    • Se as chaves forem diferentes, usa gallop para pular rapidamente até o próximo ponto de correspondência possível
  • gallop é uma ideia trazida do EmptyHeaded: ele avança exponencialmente enquanto a condição monótona for verdadeira e depois restringe por busca binária

Experimento de análise de nulabilidade

  • Os dados do experimento vêm do projeto Graspan e também continuam disponíveis no Google Drive
  • A entrada da análise de fluxo de dados tem duas relações, e e n
    • n(?a, ?b): o valor ?a pode ser escrito na posição ?b
    • e(?a, ?b): o valor de uma posição ?a pode se mover para outra posição ?b
  • A regra de alcançabilidade é a seguinte
    • n(?a, ?c) :- n(?a, ?b), e(?b, ?c) .
  • Na entrada httpd, o .list inicial mostra o seguinte
    • e: 9,905,624
    • n: 138,331
  • Executar a regra diretamente leva cerca de 15 segundos, e n passa a ter 9,393,283 itens
  • Um dos motivos da lentidão é que a relação temporária .temp-0-0-in, que reorganiza n para corresponder à chave do join, cresce até 9,393,283 itens
  • Se o usuário reescrever a regra, o desempenho melhora
    • m(?loc, ?val) :- n(?val, ?loc) .
    • m(?loc, ?val) :- m(?mid, ?val), e(?mid, ?loc) .
  • Na mesma entrada httpd, após a reescrita a segunda regra roda em cerca de 8.43s
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
datatoad 8.43s 24.33s 55.01s
datafrog 1.30s 4.06s 8.03s
  • O número do Graspan para lnx_kernel vem com *: o artigo reporta o tempo total junto, e por causa de colisões de identificadores na entrada é difícil tratá-lo como exatamente a mesma execução
  • Para comparar com ferramentas usadas na prática, Soufflé pode ser um alvo mais apropriado

Análise de aliasing e otimização manual

  • A segunda análise é a análise de aliasing de Zheng and Rugina adotada pelo Graspan
  • Há dois tipos de relação de entrada
    • A(?val, ?loc): ?loc <- ?val
    • D(?val, ?loc): ?loc é usado na forma *?val
  • O objetivo é obter aliases de memória e aliases de valor
    • alias de memória: duas expressões lvalue podem apontar para a mesma posição de memória
    • alias de valor: duas expressões podem avaliar para o mesmo valor de ponteiro
  • Na notação do artigo aparecem ^T, ^? e ^*
    • ^T: transposição da relação
    • ^?: termo opcional
    • ^*: repetição de zero ou mais vezes
  • Em Datalog, ^? é expresso dividindo em duas regras, e ^* é tratado inserindo explicitamente a relação identidade
  • A execução inicial das regras demora bastante
    • Após inserir as duas últimas regras de inicialização de identidade, leva 686.57s e 736.34s
    • O processo usa 50.13GB
    • V: 361,947,256
    • M: 92,806,768
    • F: 2,669,647
  • Relações transpostas -V, -M, -a, -d são usadas explicitamente para eliminar as relações temporárias -in
    • Total de 815.92s, cerca de 13.6 minutos
    • Memória: 31.96GB
  • Como a abordagem de Zheng and Rugina é demand-driven e na prática só M é necessário, V é embutido em M
    • -V com 361,947,256 itens deixa de ser produzido
    • A memória cai para 18.96GB
  • Um trecho de join repetido recebe o nome Fd para ser reutilizado, e depois Fd passa a ser calculado diretamente no lugar de F, reduzindo também o problema da identidade
  • A forma final, com a relação intermediária MFd, produz o seguinte resultado
    • Tempo de execução: 119.34s
    • Memória: 5.32GB
    • -M: 92,806,768
    • Fd: 1,858,986
    • MFd: 73,474,947
  • Só com reescritas manuais, memória e tempo de execução melhoram quase 10x em relação à tentativa inicial
  • Criar resultados intermediários nomeados permite montar até certo ponto o plano de join em árvore arbustiva desejado, mas se você der nome a uma relação que na prática não é necessária, como V, vai acabar pagando caro para materializá-la

Consultas demand-driven e magic sets

  • Consultas demand-driven exploram apenas a parte necessária para um fato-alvo específico
  • Uma solução aproximada pode usar magic sets
    • É uma transformação que embute o literal-alvo na consulta
    • Dá para imaginar começar não de todo d, mas apenas do d de interesse; porém, se aplicar isso de forma simples, o resultado pode ficar incorreto
  • Magic sets não são a resposta ótima, e a ideia é ler mais artigos relacionados para encontrar abordagens possivelmente mais eficientes
  • Os links relacionados são os seguintes

Otimização de plano de join e IR paralela em dados

  • O apelo do Datalog não está tanto nas próprias Horn clauses, mas no fato de ele expor de forma pura o problema central da computação paralela em dados: o data rendezvous
  • A regra h(x, y, z) :- b1(x, y), b2(y, z) . pode ser vista como o problema de reunir, para cada y, os x e z relacionados em um mesmo lugar
  • A operação básica da computação paralela em dados é agrupar registros por chave e entregá-los à lógica do usuário; o join expressa um roteamento seletivo entre esses casos
  • Uma IR simples usa os seguintes opcodes
    • Var(String): coleção nomeada
    • Map(Action): filtro, permutação, projection
    • Key(usize): marca as primeiras colunas como chave
    • Mul(usize): combina várias coleções com o mesmo comprimento de chave
  • Depois, Map e Key são unificados em Action.key_arity
  • Action contém filtro de literal, filtro de igualdade entre variáveis, projection e aridade de chave
  • O ponto de partida mais simples é fazer cross join de todos os átomos do body e aplicar filtro e projection para cada head, mas isso até produz a resposta certa; o desempenho, porém, é muito ruim

Otimização baseada em e-graph

  • A otimização usa e-graph e equality saturation
  • Como material de referência, são usados a página do egg, o artigo anterior e egg
  • O term graph é representado como um mapa de ENode<T> com Id, compartilhando nós idênticos para representar o programa de forma mais concisa
  • Foram aplicadas três regras de e-graph
    • MulPermute: torna equivalentes as permutações de entrada de Mul(k)
    • MulPartition: divide Mul(k) de várias maneiras e as torna equivalentes
    • MapPushdown: empurra Map para baixo de Mul(2) para formar joins com chave
  • A regra de exemplo é a seguinte
    • head(?a, ?b) :- a(?x, ?a), b(?y, ?x), b(?y, ?z), a(?z, ?b) .
  • Após a equality saturation, custos são atribuídos na etapa de extração
    • O custo de Map é o número de colunas de saída
    • O custo de Mul é a soma do número de colunas-chave e das colunas não-chave das entradas
    • O custo de Var é 0
    • Em caso de empate, minimiza-se primeiro a quantidade de Map e depois a de Mul
  • No exemplo, o plano selecionado é encontrado na wave two, com no máximo duas colunas não correlacionadas
    • map sobre as entradas a e b
    • um join
    • projection intermediária
    • join com ele mesmo
    • projection final
  • Essa busca de plano leva cerca de 40 ms mesmo em release build, e a maior parte do tempo é gasta na equivalence saturation

Atualização da execução de planos otimizados

  • Na atualização de 2025-06-29, foi implementada a execução de planos otimizados
  • O plano sai como Vec<ENode<Op>>, mas a execução real não executa cada nó de forma independente
  • A forma de execução pretendida é a seguinte
    • Para cada Var, aplicar vários Map dependentes em uma única varredura da coleção externa
    • Para cada Mul, aplicar vários Map dependentes em uma única varredura do join
  • Op::Map(action) não é tanto uma operação executada diretamente, mas um trabalho enfileirado para a operação da qual depende
  • Para isso, foi introduzido TempAction
    • filtro de literal
    • filtro de igualdade de variáveis
    • projection que pode conter referência de coluna ou literal de string
  • Na etapa de preparação do plano de execução, body e head são separados e as ações de Map são agrupadas por nó de entrada
  • No processamento de nomes na execução de Var, há três casos
    • a criação do head usa o nome da relação head
    • a transformação identity reutiliza o nome de entrada existente
    • transformações não triviais são armazenadas em nomes temporários .temp-*
  • A execução de Mul(2) verifica a key arity e os nomes das duas entradas, e chama join_with para acumular os resultados em vários builders
  • Em um exemplo complexo de aliasing, a execução do plano otimizado levou 114,28 segundos, cerca de 5 segundos mais rápida do que os 119 e poucos segundos anteriores, mas o motivo não está claro
  • A otimização multi-rule ainda não foi implementada, e talvez seja necessário repensar a própria abordagem de planejamento

Otimização da representação de fatos

  • O uso caiu de 50 GB para 5 GB, mas ainda parece consumir cerca de 10 vezes mais memória do que o necessário
  • A maior layer da relação grande -M contém 57.289.225 fatos e usa cerca de 2.098.253.766 bytes
    • limites dos fatos: 458.313.800 bytes
    • limites dos termos: 916.627.600 bytes
    • dados reais em bytes: 723.312.366 bytes
  • A primeira otimização aproveita o fato de a arity ser fixa
    • se todos os fatos têm 2 colunas, os limites dos fatos podem ser representados apenas com stride e length
    • isso praticamente elimina os cerca de 458 MB de dados de limites
  • A segunda otimização é igualar o comprimento dos termos
    • se os números forem transformados em strings de largura fixa com 7 dígitos, os limites dos termos também podem ser representados com stride e length
    • em compensação, a quantidade real de bytes pode aumentar
  • A terceira otimização é representar números em binário, e não como texto
    • um número de 7 dígitos cabe em 4 bytes de u32
    • também cabe em 3 bytes, então fica 57,289,225 × 2 × 3 = 343,735,350 bytes
    • isso reduz de cerca de 2 GB para cerca de 350 MB, uma queda de aproximadamente 6,10 vezes
  • Com compressão da repetição do primeiro termo, é possível reduzir ainda mais
    • há 57.289.225 fatos, mas apenas 1.147.612 first terms distintos
    • ao armazenar no formato (Term, [Term]) em vez de (Term, Term), a maior layer cai para algo em torno de 184.491.407 bytes
    • isso representa uma redução de cerca de 11,37 vezes em relação aos 2 GB iniciais
  • Na atualização de 2025-07-02, a otimização de primeira fase foi aplicada
    • o maior batch passou a ter 343.735.382 bytes, ou seja, o valor teórico de 343.735.350 bytes mais 32 bytes
    • o tempo de execução caiu de cerca de 115 segundos para cerca de 95 segundos, uma melhora de aproximadamente 20%

Representação em layered trie

  • Na atualização de 2025-07-20, o layered trie passou a funcionar
  • Foi feita uma comparação entre a representação row-oriented e a representação column-oriented em layered trie
    • toad-row
    • toad-col
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
toad-row 3.88s 11.30s 25.67s
toad-col 3.47s 11.94s 23.09s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
toad-row 28.21s 28.25s 7.62s
toad-col 19.39s 21.96s 9.48s
datafrog UNK UNK UNK
  • O layered trie suprime a repetição das colunas anteriores em uma representação por linhas ordenadas
  • Cada coluna é uma lista de listas de valores
    • cada lista corresponde a um prefixo da coluna anterior e contém uma lista ordenada de valores distintos
    • o número de listas de uma coluna é igual ao total de itens da coluna anterior
  • Pode ser visto como uma árvore, mas a implementação real permanece em colunas
  • A vantagem é que busca, join, diferença e merge podem ser feitos no nível de prefixo
  • Quando quase não há valores distintos e é melhor observar a linha inteira de uma vez, a abordagem row-oriented pode ser mais vantajosa
  • Como abstração comum, foi introduzida a trait FactContainer
    • form
    • len
    • apply
    • join
    • except
    • merge
  • apply monta linhas e as entrega à action rastreando os intervalos de cada layer com uma stack explícita, em vez de usar recursão
  • align é um helper comum para alinhar prefixos entre dois layered tries
    • Ordering::Less: intervalo presente apenas em self
    • Ordering::Greater: intervalo presente apenas em other
    • Ordering::Equal: prefixo de comprimento igual à arity presente em ambos os lados
  • join, except e merge são todos implementados sobre align
    • join expande as extensões restantes no prefixo comum e faz cross join
    • except faz graft dos intervalos exclusivos de self em um TrieBuilder
    • merge faz graft, uma vez cada, dos intervalos só de self, só de other e iguais, conforme apropriado

Otimizações de largura fixa e desempenho

  • Quando é possível fazer upgrade para [u8; 4] de largura fixa, o desempenho de comparação melhora bastante
  • Como o layered trie permite aplicar otimizações de largura fixa por coluna, ele pode ter vantagem sobre row no longo prazo
  • Em except e merge, foi fácil aplicar upgrade e downgrade, mas aplicar isso em join foi mais difícil por causa de problemas de tipos no Rust
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
toad-row 3.88s 11.30s 25.67s
^-- +opt 3.11s 9.49s 19.83s
toad-col 3.47s 11.94s 23.09s
^-- +opt 2.55s 9.13s 15.95s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
toad-row 28.21s 28.25s 7.62s
^-- +opt 23.31s 23.08s 6.73s
toad-col 19.39s 21.96s 9.48s
^-- +opt 14.26s 16.45s 8.33s
datafrog UNK UNK UNK
  • Cerca de 2/3 do tempo atual é consumido em join
  • A otimização de joins provavelmente ainda tem margem para pelo menos mais 2x de ganho
  • Uma tentativa de simplesmente reordenar o inner loop não produziu melhoria mensurável

Especializando até o nível de código compilado

  • Se for possível detectar fatos com termos de mesmo comprimento e mesma aridade, dá para tratar Vec<u8> como algo como Vec<[[u8; B]; T]>
  • Nessa forma, o Rust entende melhor o formato dos dados, reduzindo o custo de verificações de bounds e length, além de tornar comparações particularmente baratas
  • Comparações são usadas em vários pontos do datatoad
    • ordenação e remoção de duplicatas de batches de fatos
    • merge de batches
    • merge de chaves de join
    • filtragem de novos fatos comparando-os com fatos existentes
  • O desempenho de referência é o seguinte
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
datatoad 7.44s 17.26s 42.25s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
datatoad 101.24s 96.36s 20.20s
datafrog UNK UNK UNK
  • A otimização de ordenação foi testada fazendo unsafe transmute de Vec<u8> para Vec<[u8; 8]> para depois aplicar sort e dedup
dataflow httpd psql lnx_kernel
dt-orig 7.44s 17.26s 42.25s
dt-sort 4.99s 13.55s 32.15s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
dt-orig 101.24s 96.36s 20.20s
dt-sort 52.99s 53.19s 11.20s
datafrog UNK UNK UNK
  • A otimização de merge foi implementada de forma simples, concatenando as duas entradas e depois aplicando sort e dedup
dataflow httpd psql lnx_kernel
dt-orig 7.44s 17.26s 42.25s
dt-sort 4.99s 13.55s 32.15s
dt-both 3.71s 11.23s 23.58s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
dt-orig 101.24s 96.36s 20.20s
dt-sort 52.99s 53.19s 11.20s
dt-both 31.32s 30.08s 8.56s
datafrog UNK UNK UNK
  • Ainda não chegou ao desempenho compilado do datafrog
  • O custo restante de comparações também está em join e antijoin, e o plano é revisitar as mesmas oportunidades de otimização ao migrar para uma estrutura baseada em trie
  • Também está buscando uma forma de remover unsafe, concluindo que código unsafe deve ser evitado

Trabalho que ainda falta

  • Spill para disco

    • O armazenamento columnar é composto por poucas alocações grandes
    • Em vez de escrever na memória ao criar, seria possível escrever em arquivo e reutilizar via memory map

  • Avaliação distribuída

    • Join, deduplicação e verificação de distinctness são baseados em igualdade de chaves
    • É possível distribuir as chaves e seus dados correspondentes entre vários workers
    • Com timely_communication, isso pode ser estendido até vários processos

  • Avaliação de regras em streaming

    • Atualmente, joins usam join binário e output materializado
    • Se os índices necessários existirem, é possível criar um plano que não materialize o estado interno
    • Worst-case optimal join também deve ser tratado aqui

  • Especialização de representações customizadas

    • Existe a ideia de detectar transitive closure e especializar para decomposição em componentes fortemente conectados
    • Relações de equivalência podem usar a estrutura de dados union-find
    • bddbddb e factorized databases também tratam de tópicos relacionados

  • Busca de fatos relevantes

    • É preciso entender e aplicar demand transform
    • Isso é visto como uma transformação necessária para exploração interativa de Datalog

Leituras relacionadas

1 comentários

 
GN⁺ 2025-06-16
Opiniões no Hacker News

  • É curioso ver este artigo chegar ao 1º lugar
    No momento estou criando um jogo de estratégia em tempo real com Differential Datalog e Rust, deixando a lógica do jogo sob responsabilidade do DDL
    Na maior parte, é quase uma desculpa para conhecer ideias novas e embarcar em uma interminável tosquia de iaques
    https://github.com/vmware-archive/differential-datalog

    • Parece uma demo legal feita com ddlog
      Aliás, a equipe do ddlog agora fundou a Feldera, e talvez valha considerar usar DBSP diretamente em Rust
      https://github.com/feldera/feldera
    • Fico curioso se, misturando o repositório do artigo original com o salsa, o crate que impulsiona o analisador de Rust, daria para criar uma espécie de differential datalog frankensteiniano
      https://github.com/salsa-rs/salsa
    • Tenho curiosidade sobre o estado da implementação e até onde ela pode chegar
      DDLog já não é mais mantido ativamente, o que torna isso ainda mais interessante

  • “Eu, um vilão notório, fui convidado com a quase certeza de que estava indo receber a punição que há muito me era devida.” — a melhor primeira frase de um post técnico que li este ano
    As intervenções do narrador também foram excelentes, e é raro encontrar um texto tão tecnicamente profundo que ainda seja divertido de ler
    A jornada para otimizar consultas de alias parecia um romance policial, e o leitor também acaba gemendo junto com o uso de 50 GB de memória e comemorando quando cai para 5 GB
    Tanto o código quanto o texto são excelentes

  • Avancei um pouco no trabalho de portar o mangle datalog para Rust
    Ele está em https://github.com/google/mangle/tree/main/rust, no mesmo repositório da implementação em Go
    Como a prioridade não é alta e também há um pouco de síndrome do segundo sistema, o progresso é lento
    O Mangle Rust segue na direção de lidar com dados de tamanho arbitrário lendo e gravando fatos em disco via mapeamento de memória, enquanto a implementação em Go é em memória
    Este artigo é bom porque aborda o parsing de Datalog e também árvores LSM, e é muito mais fácil de acompanhar do que os materiais sobre datafrog
    Em Rust há muitas implementações de Datalog que usam macros procedurais, como ascent e crepe, mas elas têm a desvantagem de dificultar o recebimento de consultas em tempo de execução
    Para usos de análise estática em que as consultas e o programa são fixos, a abordagem com macros procedurais pode ser melhor

  • Mesmo que o atual renascimento do Datalog pareça estar perdendo força, é bom ver os entusiastas centrais continuarem resistindo
    A conferência Datalog 2.0 recente foi bem menor do que antes, e a segunda conferência HYTRADBOI também teve uma presença menor de Datalog
    Na primeira HYTRADBOI, um quarto das submissões tinha relação com Datalog
    Também é animador ver outras pessoas compartilhando projetos recentes de Datalog
    No momento estou preparando uma grande migração de software e criando um pipeline de qualidade de dados para um banco de dados SQL legado
    Quando as consultas são bem estruturadas, elas ficam muito legíveis; por isso, acho Datalog muito mais útil que SQL para identificar e localizar problemas de qualidade de dados

    • Mesmo concordando com a direção geral, é difícil tratar o baixo número de participantes do Datalog 2.0 como um exemplo representativo do declínio do Datalog
      O Datalog 2.0 é um workshop satélite da LPNMR, uma conferência europeia relativamente pouco conhecida, e por acaso essa conferência foi realizada em Dallas
      Quando participei presencialmente, o evento também pareceu um tanto esvaziado; submeti um artigo ao workshop, mas não vi muita gente da área por lá
      A exceção notável foram algumas pessoas da Europa apresentando o solucionador Nemo
      Acho que o baixo público deste ano mostra mais o fato de ser um workshop satélite de uma conferência que já não é muito famosa, e cujo evento principal também era a ICLP, do que falta de interesse em implementações de Datalog
      Claro, não estou tentando contestar a afirmação mais ampla de que há pouca novidade restante na implementação de motores Datalog puros
      O espaço de pesquisa já foi muito além disso e migrou para problemas mais exóticos, como streaming (HydroFlow), choice (Dusa) e coisas mais próximas do chase geral (o motor de chase do Egglog)
      Em geral há pouca discordância de que Datalog vanilla é entediante, mas saturação direta monotônica e cláusulas de Horn são uma baseline rica, com um terreno de engenharia de desempenho bem compreendido, o que as torna uma boa base para construir teorias mais interessantes, como semianéis ou Z-sets

  • Se você achou interessantes a máquina de estados e a parte de parsing, recomendo também a antiga palestra de Rob Pike, Lexical Scanning in Go
    https://www.youtube.com/watch?v=HxaD_trXwRE
    Ela é em Go, mas a maior parte se aplica facilmente a outras linguagens
    É bom que linguagens modernas como Rust, Zig e Go deem suporte nativo a Unicode/rune/grafema
    Em comparação com Java, .NET, C++ ou linguagens de script, muitos problemas simplesmente desaparecem

  • Gosto do trabalho do autor com Datalog de modo geral, mas preferiria que materiais introdutórios não ensinassem junções binárias
    Fora dos casos ideais, o interior ficou rapidamente bagunçado, e o método de junções gerais foi muito mais fácil de generalizar mentalmente
    https://en.wikipedia.org/wiki/Worst-case_optimal_join_algorithm

  • Há muito tempo, durante os estudos, tive um contato superficial com Prolog e sei mais ou menos para que ele é usado e em que é útil, mas não cheguei a entendê-lo profundamente
    Desde então, continuo ouvindo que Datalog é incrível, mas ainda não consigo entender bem o que o Datalog melhora em relação ao Prolog
    Acabei de passar os olhos pela página da Wikipedia sobre Datalog e parece que Prolog tem desempenho relativamente ruim, enquanto Datalog reduz expressividade e funcionalidades em troca de uma grande melhora de desempenho, permitindo datasets maiores e processamento mais paralelizado
    Parece incluir também a perda da completude de Turing, mas fico curioso se isso é o ponto central ou se estou totalmente fora do caminho

    • Pelo que sei, Prolog parece declarativo no sentido de que, se você apenas codifica as relações, ele encontra a resposta, mas na prática depende muito da ordem das regras e também exige diretivas adicionais como “cut”
      O cut não só evita cálculos desperdiçados como também pode afetar os resultados
      Já Datalog, em geral, fica mais próximo de um banco de dados relacional com outra sintaxe
    • Datalog é mais simples, não é Turing-completo e, se me lembro bem, usa inferência para frente, o que tem efeitos em cadeia sobre desempenho e características de memória
      Um espaço de busca enorme e trivial em Prolog pode consumir tanta memória em Datalog que talvez nem seja possível expressá-lo
      Datalog é como um carro de uso diário com câmbio CVT, enquanto Prolog está mais para um carro de F1
      Em vez de uma melhoria, é mais como uma poda parcial do Prolog para impedir que as pessoas deem um tiro no próprio pé, além de ser muito mais fácil de implementar e embutir em outras aplicações
      Se você está acostumado com Prolog, Datalog provavelmente vai parecer bem limitante
      Não há call/3, nem expansão de term/goal; basicamente, Datalog foi projetado como um subconjunto mínimo comum do Prolog para uso em buscas interativas em bancos de dados
      Código Datalog rápido é fácil de escrever, mas o teto também é muito mais baixo
      Prolog também pode ser escrito de modo a permitir concorrência, mas isso é uma tarefa intermediária que exige entender a implementação
      Guarded Horn Clauses e linguagens derivadas foram desenvolvidas para formalizar essa parte, mas os avanços japoneses posteriores ao Prolog são bastante difíceis de acompanhar
      O desempenho de Prolog depende muito do programador, da implementação usada e de onde ele é usado
      Assim como Lisp, Prolog também pode ser usado para gerar código de máquina nativo a partir de uma DSL em tempo de compilação
      Se você entende como a implementação de base funciona e escreve o código de acordo com ela, ele pode ser suficientemente rápido
      Mas, para isso, é preciso escrever código Prolog por anos em uma única implementação
      Também há muita pesquisa sobre otimização de compiladores Prolog e casos de implementações proprietárias
      http://logicprogramming.stanford.edu/readings/ullman.pdf
      https://www.ueda.info.waseda.ac.jp/AITEC_ICOT_ARCHIVES/ICOT/Museum/IFS/abst/078.html
      https://www.sciencedirect.com/science/article/pii/S0743106696889813
      https://link.springer.com/content/pdf/10.1007/3-540-18024-9_26.pdf
      https://sicstus.sics.se/

  • Se você quer usar Datalog com Rust, o cozodb é escrito em Rust e também oferece sintaxe de consultas Datalog

    • Cozodb parece interessante, mas dá a impressão de estar quase inativo
      Dei uma olhada nele por volta de novembro de 2024 e encontrei alguns pontos fáceis de melhorar no backend de armazenamento SQLite
      https://github.com/cozodb/cozo/issues/285
    • Cozodb funcionou, em geral, bem conforme a documentação e foi agradável de usar
      Usei também para análise estática de programas, e internamente ele usa árvores ordenadas e técnicas de tipos
      A documentação é suficiente para comparação com o passo a passo do blog, e o trabalho de otimização de consultas é especialmente interessante
      Porém, se você não trabalhar em memória no Rust, o custo de serialização dos dados é alto, e o projeto, na melhor das hipóteses, está silencioso

  • Antigamente, fãs de Clojure diziam que Datalog era melhor que SQL e que era uma pena os bancos de dados relacionais usarem todos SQL
    Eu não cheguei a investigar a fundo por que eles pensavam assim

    • Basicamente, Datalog é muito menos verboso que SQL, o custo de separar views é muito menor e ele oferece suporte esmagadoramente melhor a fechamento transitivo
      http://canonical.org/~kragen/binary-relations começou como uma consulta não recursiva simples, mas a tradução para SQL já é criminosa, e uma solução SQL devidamente separada mereceria pena de morte
      Recursos recursivos foram adicionados recentemente ao ANSI SQL, então isso já não é completamente impossível, mas há três grandes desvantagens
      Primeiro, por acidente tornaram SQL Turing-completo; em contraste, consultas Datalog têm término garantido
      Segundo, ainda é extremamente desajeitado de usar
      Terceiro, por causa do primeiro motivo, muitas vezes não é implementado por completo, então é difícil confiar no uso
    • O dialeto Clojure/Datomic é difícil de entender, mas concordo com a direção geral
      Para experimentar Datalog online em um ambiente de notebook amigável, recomendo Percival
      https://percival.ink/
      Não há, no ecossistema de implementações de Datalog, um padrão equivalente a “ANSI SQL”, mas, depois de aprender as ideias centrais, outros Datalogs não são muito difíceis
      Também comecei um fork do Percival que compila Datalog para SQLite; se quiser ver como os dois expressam as mesmas coisas, pode conferir
      https://percival.jake.tl/
      Agregações e joins mais avançados ainda não estão prontos, mas a forma básica funciona bem
      Logica é um compilador Datalog→SQL muito mais sério e completo, criado por pesquisadores do Google, que compila para BigTable, DuckDB e alguns dialetos SQL
      https://logica.dev/
      A área em que Datalog fica mais de uma ordem de grandeza mais fácil é ao lidar com consultas/regras recursivas
      Também é possível em SQL, mas a sensação é mais próxima de tentar sugar massinha Play-Doh por um canudo
      O Materialize.com do Frank tem uma forma SQL “WITH MUTUALLY RECURSIVE”, muito melhor que o antigo método recursivo do ANSI SQL, e está sendo avaliada no Notion para consultas de carregamento de páginas e sincronização de dados
      https://materialize.com/blog/recursion-in-materialize/
      A Feldera também tem uma forma parecida para views recursivas
      https://www.feldera.com/blog/recursive-sql-queries-in-feldera
      Gosto da Feldera porque cada “regra” ou subview pode ser feita como uma instrução separada, em vez de colocar tudo em uma única instrução gigantesca
      A principal desvantagem que vi nos testes é que o dialeto SQL da Feldera tem bastantes restrições herdadas do Apache Calcite, enquanto o dialeto SQL da Materialize se esforça muito para manter compatibilidade com PostgreSQL

  • Um novo texto do McSharry — excelente
    Da última vez que verifiquei, a VMWare parecia ter se afastado do differential datalog

    • A equipe do Differential Datalog fundou a Feldera
      https://www.feldera.com/
      Parece que eles trocaram differential Datalog por differential SQL, provavelmente porque perceberam que vender Datalog é realmente difícil