Crear un motor Datalog interactivo con Rust

 (github.com/frankmcsherry)
1 puntos por GN⁺ 2025-06-16 | 1 comentarios | Compartir por WhatsApp
  • A partir de las limitaciones de usabilidad y rendimiento de las herramientas Datalog que quedaron en evidencia en un taller de programación lógica, comenzó el experimento de datatoad, un shell Datalog interactivo basado en Rust
  • datatoad apunta a una arquitectura que permita agregar reglas en ejecución y seguir derivando nuevos hechos, y reduce el costo de procesar duplicados en el conjunto de hechos con almacenamiento columnar y capas LSM
  • La evaluación de reglas convierte el cuerpo de Datalog en un problema de joins y, según si es stable o no, separa la evaluación completa de la evaluación incremental para evitar joins stable-stable ya calculados
  • En experimentos con el dataset Graspan, solo con reescritura manual de reglas e introducción de relaciones intermedias, el análisis de aliasing se redujo de 736.34 segundos y 50.13 GB a 119.34 segundos y 5.32 GB
  • El trabajo posterior continúa con optimización de planes de join basada en e-graph, layered trie, representación de bytes de ancho fijo, spill a disco, evaluación distribuida, joins en streaming y demand transform

El problema que datatoad busca resolver

  • En un taller de programación lógica durante el fin de semana de Memorial Day, se hicieron evidentes las incomodidades de las herramientas Datalog para análisis de programas, y eso motivó intentar una implementación de Datalog simple, útil y rápida
  • El objetivo de la implementación no es un ejecutor de ejemplos estáticos, sino un shell Datalog interactivo
    • Puede cargar grandes volúmenes de hechos
    • Puede agregar nuevas reglas durante la ejecución
    • Sigue reflejando en el estado existente los resultados de las reglas agregadas
  • El código puede seguirse en el repositorio de datatoad
  • El ya existente datafrog ofrece los algoritmos centrales de un motor Datalog, pero requiere que el usuario conecte las piezas manualmente, así que datatoad reorganiza las mismas ideas en una forma más fácil de usar
  • En el ejemplo de nullability del grafo de flujo de datos httpd, datatoad tardó 8.3 segundos con datos Vec<String> y consultas no compiladas, unas 4 veces más lento que el ejemplo de datafrog con datos (u32, u32), que ronda los 2 segundos
  • En el problema de reachability produjo la misma cantidad de tuplas de salida que la implementación de datafrog, pero la verificación general de exactitud todavía no está cerrada

Modelo Datalog y estructura del shell

  • Datalog es un lenguaje en el que se escriben reglas lógicas simples y se derivan todos los hechos alcanzables a partir de esas reglas
  • Las reglas se componen de head y body
    • Ejemplo: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c).
    • tri y edge son relaciones, y a, b, c son variables
    • Las variables que aparecen en el head también deben estar en el body
  • Los hechos se tratan como reglas con body vacío
    • Ejemplo: edge(1, 2) :- .
    • Se pueden usar varios heads para escribir varios hechos de una vez
  • Debido a la monotonicidad de Datalog, aunque se agreguen reglas o hechos, el conjunto de hechos verdaderos no se reduce, y el mismo conjunto de reglas de entrada llega al mismo resultado sin importar el orden de las reglas
  • La representación en Rust se centra en tres estructuras: Rule, Atom y Term
    • Rule { head: Vec<Atom>, body: Vec<Atom> }
    • Atom { name: String, terms: Vec<Term> }
    • Term::Var(String) o Term::Lit(String)
  • Para almacenar literales se usa Vec<u8> en lugar de String
    • Las propiedades necesarias son igualdad de literales y algún ordenamiento arbitrario
    • Queda abierto al usuario si esos bytes representan String, (u32, u32) u otro significado
  • El estado del intérprete guarda juntas las reglas y los hechos
    • rules: Vec<Rule>
    • facts: facts::Facts
  • Cuando el shell parsea una línea de entrada como Datalog, llama a State::extend y State::update, y con el comando .list imprime el nombre de cada relación y la cantidad de hechos

Parsing y almacenamiento de hechos

  • El parser está en parse.rs y usa una forma tomada de la gramática de Soufflé
  • Las variables comienzan con ?
  • Los tokens se limitan a ., ,, (, ), :-, ?, y el resto del texto se trata como nombre de atom o term
  • El tokenizer elimina espacios y reemplaza :- por ← para escanearlo como un solo símbolo
  • El parsing de reglas lee los atoms del head hasta el turnstile y los atoms del body hasta el punto final
    • Un atom se compone de nombre, paréntesis izquierdo, lista de terms y paréntesis derecho
    • Si un term tiene ?, es variable; si no, es literal
  • Las reglas inválidas devuelven None, y por ahora no se informa en detalle qué parte está mal
  • Para agregar reglas negativas haría falta un token Exclamation, pero todavía no se maneja

Ciclo de vida del conjunto de hechos

  • Un almacenamiento simple con Vec<Vec<String>> acumula asignaciones anidadas y no favorece la gestión de memoria
  • datatoad usa columnar para transformar tipos de Rust en unos pocos bloques de asignación lineal con layout plano
    • Los bytes de las cadenas, los límites de las cadenas y los límites de los hechos se guardan en arreglos separados
  • FactContainer envuelve una lista de hechos ordenada y sin duplicados, e implica mediante un wrapper type el invariante de orden y deduplicación
  • Como el contenedor columnar es en la práctica append-only y no se adapta bien a cambios intermedios, para agregar nuevos hechos se usa una estructura tipo log-structured merge-tree (LSM)
    • FactLSM { layers: Vec<FactContainer> }
    • El tamaño de las capas se administra para que crezca geométricamente
    • Se fusionan capas cuyos tamaños estén dentro de un factor de 2 para mantener el estado ordenado y deduplicado
  • FactBuilder mantiene en conjunto un área active no ordenada y potencialmente duplicada, y unas layers ordenadas y deduplicadas
  • Los hechos de cada relación pasan por tres etapas
    • to_add: hechos recién llegados cuya novedad todavía no fue verificada
    • recent: hechos distintos que aún deben procesarse
    • stable: hechos distintos que ya fueron procesados por completo
  • FactSet::advance mueve recent a stable y elimina de to_add los hechos que ya están en stable para crear un nuevo recent

La evaluación de reglas como problema de joins

  • El body de una regla Datalog puede verse como un equi-join de base de datos relacional
  • El ejemplo de la regla de triángulo es el siguiente
    • tri(?a, ?b, ?c) :- edge(?a, ?b), edge(?b, ?c), edge(?a, ?c).
  • Enumerar directamente todas las asignaciones de variables sería demasiado, aunque sea finito, así que se ordenan y fusionan usando como base las columnas clave de las variables compartidas
  • La implementación reduce el body de derecha a izquierda
    • Une las dos últimas relaciones para crear una relación intermedia y luego vuelve a unirla con la relación de la izquierda
    • Si solo hay un atom en el body, solo transforma la forma al head
  • JoinPlan contiene la siguiente información
    • bodys, que reordena y filtra los atoms del body para adaptarlos al join
    • joins, que guarda la aridad de clave de cada join intermedio y la proyección de salida
    • heads, que representa las coordenadas o literales que se insertarán en el atom del head
    • La aridad del join final que genera el head
  • El plan actual es un right-linear join plan simple
  • Al crear JoinPlan, se usan las posiciones de aparición más a la izquierda y más a la derecha de cada variable para decidir hasta cuándo conservar cada valor de variable, y se dividen las columnas del body atom en columnas dead, key y value
  • La función central es implement_plan(rule, plan, pos, stable, facts)
    • Cuando se agrega una regla nueva, empieza sobre todos los hechos con stable = true
    • En la aplicación repetida de reglas existentes, calcula solo nuevas derivaciones con stable = false

Join incremental y merge join

  • El join es bilineal, así que se descompone así
    • (A + a) ⋈ (B + b) = A ⋈ B + A ⋈ b + a ⋈ B + a ⋈ b
  • A ⋈ B, que ya se construyó entre conjuntos stable, no necesita recalcularse
  • Si solo se necesitan nuevas derivaciones, basta con hacer tres joins
    • A ⋈ b
    • a ⋈ B
    • a ⋈ b
  • join_with incluye o excluye el join stable-stable según la bandera stable
  • El join real es un merge join que recorre secuencialmente dos entradas ordenadas
    • Si las claves coinciden, llama a action para todas las combinaciones de esa clave
    • Si las claves difieren, usa gallop para saltar rápido hasta el siguiente punto de coincidencia posible
  • gallop es una idea tomada de EmptyHeaded: avanza exponencialmente mientras se cumple una condición monótona y luego acota la búsqueda de forma binaria

Experimento de análisis de nullability

  • Los datos del experimento provienen del proyecto Graspan y también siguen disponibles en Google Drive
  • La entrada del análisis de flujo de datos tiene dos relaciones: e y n
    • n(?a, ?b): el valor ?a puede escribirse en la posición ?b
    • e(?a, ?b): el valor de una posición ?a puede moverse a otra posición ?b
  • La regla de reachability es la siguiente
    • n(?a, ?c) :- n(?a, ?b), e(?b, ?c) .
  • En la entrada httpd, el .list inicial muestra lo siguiente
    • e: 9,905,624
    • n: 138,331
  • Ejecutar la regla directamente toma unos 15 segundos, y n llega a 9,393,283 elementos
  • Una de las razones de la lentitud es que la relación temporal .temp-0-0-in, que reordena n para ajustarlo a la clave del join, crece hasta 9,393,283 elementos
  • Si el usuario reescribe la regla, el rendimiento mejora
    • m(?loc, ?val) :- n(?val, ?loc) .
    • m(?loc, ?val) :- m(?mid, ?val), e(?mid, ?loc) .
  • Con la misma entrada httpd, tras la reescritura la segunda regla se ejecuta en unos 8.43 segundos
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
datatoad 8.43s 24.33s 55.01s
datafrog 1.30s 4.06s 8.03s
  • La cifra de Graspan para lnx_kernel lleva *: el artículo reportó el tiempo total junto con otros datos, y por conflictos de identificadores de entrada es difícil considerarlo exactamente la misma ejecución
  • Si se quiere comparar con una herramienta que use gente de práctica, quizá Soufflé sea un objetivo más adecuado

Análisis de aliasing y optimización manual

  • El segundo análisis es el análisis de aliasing de Zheng y Rugina que Graspan tomó
  • Hay dos relaciones de entrada
    • A(?val, ?loc): ?loc <- ?val
    • D(?val, ?loc): ?loc se usa en la forma *?val
  • El objetivo es obtener alias de memoria y alias de valor
    • alias de memoria: dos expresiones lvalue pueden apuntar a la misma ubicación de memoria
    • alias de valor: dos expresiones pueden evaluarse al mismo valor de puntero
  • En la notación del artículo aparecen ^T, ^? y ^*
    • ^T: transposición de relación
    • ^?: término opcional
    • ^*: repetición de cero o más veces
  • En Datalog, ^? se expresa dividiéndolo en dos reglas, y ^* se maneja agregando explícitamente una relación identidad
  • La ejecución inicial de las reglas tarda mucho
    • Tras ingresar las dos últimas reglas de inicialización de identidad, tarda 686.57 s y 736.34 s
    • El proceso usa 50.13 GB
    • V: 361,947,256
    • M: 92,806,768
    • F: 2,669,647
  • Al usar explícitamente las relaciones transpuestas -V, -M, -a y -d, se elimina la relación temporal -in
    • Total: 815.92 s, alrededor de 13.6 min
    • Memoria: 31.96 GB
  • El enfoque de Zheng y Rugina es demand-driven y en la práctica solo se necesita M, así que V se integra en M
    • Ya no se construyen los 361,947,256 elementos de -V
    • La memoria baja a 18.96 GB
  • Se le da el nombre Fd a un fragmento de join repetido para reutilizarlo, y después se calcula directamente Fd en lugar de F, reduciendo también el problema de la identidad
  • La forma final, con una relación intermedia MFd, produce estos resultados
    • Tiempo de ejecución: 119.34 s
    • Memoria: 5.32 GB
    • -M: 92,806,768
    • Fd: 1,858,986
    • MFd: 73,474,947
  • Solo con reescritura manual, la memoria y el tiempo de ejecución mejoran casi 10 veces frente al intento inicial
  • Crear resultados intermedios con nombre permite construir en cierta medida el join plan bushy-tree deseado de forma manual, pero si se le pone nombre a una relación que en realidad no hace falta, como V, se paga el costo de generarla

Consultas demand-driven y magic sets

  • Una consulta demand-driven explora solo la parte necesaria para un hecho objetivo específico
  • Como solución aproximada, pueden usarse los magic sets
    • Es una transformación que incorpora el literal objetivo en la consulta
    • Podría pensarse en empezar solo desde los d de interés, en lugar de desde todos los d, pero si se aplica de forma simple puede dar resultados incorrectos
  • Los magic sets no son la respuesta óptima, y planea leer más artículos relacionados para encontrar enfoques que puedan ser más eficientes
  • Los enlaces relacionados son los siguientes

Optimización de join plans e IR paralela de datos

  • El atractivo de Datalog no está tanto en la Horn clause en sí, sino en que expone de forma pura el problema central de la computación paralela de datos: el data rendezvous
  • La regla h(x, y, z) :- b1(x, y), b2(y, z) . puede verse como el problema de reunir en un mismo lugar los x y z relacionados para cada y
  • La operación básica de la computación paralela de datos consiste en agrupar registros por clave y entregarlos a la lógica del usuario; el join expresa dentro de eso un enrutamiento selectivo
  • Un IR simple usa los siguientes opcodes
    • Var(String): colección con nombre
    • Map(Action): filtro, permutación, projection
    • Key(usize): marca como clave las primeras columnas
    • Mul(usize): combina varias colecciones con la misma longitud de clave
  • Después, Map y Key se integran en Action.key_arity
  • Action contiene filtros de literales, filtros de igualdad de variables, projection y aridad de clave
  • El punto de partida más simple es hacer cross join de todos los átomos del body y luego aplicar filtros y projection para cada head, pero aunque produce la respuesta correcta, el rendimiento es muy malo

Optimización basada en e-graph

  • Para la optimización se usan e-graph y equality saturation.
  • Como material de referencia se usan la página de egg, un artículo anterior y egg.
  • El term graph se representa como un mapa de ENode<T> con Id, compartiendo nodos idénticos para representar el programa de forma más compacta.
  • Se aplicaron tres reglas de e-graph.
    • MulPermute: hace equivalentes las permutaciones de entrada de Mul(k).
    • MulPartition: divide Mul(k) de varias maneras y las hace equivalentes.
    • MapPushdown: empuja Map debajo de Mul(2) para formar una especie de join con claves.
  • La regla de ejemplo es la siguiente.
    • head(?a, ?b) :- a(?x, ?a), b(?y, ?x), b(?y, ?z), a(?z, ?b) .
  • Después de equality saturation, en la etapa de extraction se asignan costos.
    • El costo de Map es la cantidad de columnas de salida.
    • El costo de Mul es la suma de la cantidad de columnas clave y las columnas no clave de las entradas.
    • El costo de Var es 0.
    • En caso de empate, se minimiza primero la cantidad de Map y luego la de Mul.
  • En el ejemplo, el plan seleccionado se encontró en wave two con un máximo de dos columnas no correlacionadas.
    • map sobre las entradas a y b
    • un join
    • una proyección intermedia
    • un join consigo mismo
    • proyección final
  • Esta búsqueda del plan toma unos 40 ms incluso en release build, y la mayor parte del tiempo se usa en equivalence saturation.

Actualización de la ejecución del plan optimizado

  • En la actualización del 2025-06-29 se implementó la ejecución del plan optimizado.
  • El plan sale como Vec<ENode<Op>>, pero en la ejecución real no se ejecuta cada nodo de manera independiente.
  • La forma de ejecución prevista es la siguiente.
    • Para cada Var, aplicar varios Map dependientes en un solo escaneo de la colección externa.
    • Para cada Mul, aplicar varios Map dependientes en un solo escaneo del join.
  • Op::Map(action) no es tanto una operación que se ejecute directamente, sino un trabajo que se encola en la operación de la que depende.
  • Para esto se introdujo TempAction.
    • filtro de literales
    • filtro de igualdad de variables
    • proyección que puede contener referencias a columnas o literales de cadena
  • La etapa de preparación del plan de ejecución separa body y head, y reúne las acciones Map por nodo de entrada.
  • En la ejecución de Var, el manejo de nombres se divide en tres casos.
    • la generación de head usa el nombre de la relación head
    • la transformación identidad reutiliza el nombre de entrada existente
    • la transformación no trivial se guarda en un nombre temporal .temp-*
  • La ejecución de Mul(2) verifica la key arity y los nombres de las dos entradas, y llama a join_with para acumular los resultados en varios builders.
  • En el ejemplo complejo de aliasing, la ejecución del plan optimizado tardó 114.28 segundos, unos 5 segundos menos que los 119 y tantos anteriores, pero la razón no está clara.
  • La optimización multi-rule todavía no está implementada, y puede que haya que replantear por completo el enfoque del plan.

Optimización de la representación de facts

  • Se redujo de 50 GB a 5 GB, pero aun así parece usar unas 10 veces más memoria de la necesaria.
  • La largest layer de la relación grande -M contiene 57,289,225 facts y usa alrededor de 2,098,253,766 bytes.
    • límites de facts: 458,313,800 bytes
    • límites de terms: 916,627,600 bytes
    • datos reales en bytes: 723,312,366 bytes
  • La primera optimización aprovecha que la arity es constante.
    • Si todos los facts tienen 2 columnas, los límites de facts pueden representarse solo con stride y length.
    • Esto elimina en la práctica unos 458 MB de datos de límites.
  • La segunda optimización consiste en hacer que la longitud de los terms sea uniforme.
    • Si los números se convierten en cadenas de ancho fijo de 7 dígitos, los límites de terms también pueden representarse con stride y length.
    • A cambio, la cantidad real de bytes puede aumentar.
  • La tercera optimización consiste en representar los números en binario en lugar de texto.
    • Un número de 7 dígitos cabe en los 4 bytes de un u32.
    • También cabe en 3 bytes, así que queda en 57,289,225 × 2 × 3 = 343,735,350 bytes.
    • Baja de unos 2 GB a unos 350 MB, una reducción de aproximadamente 6.10 veces.
  • Si se comprime la repetición del primer term, se reduce aún más.
    • Hay 57,289,225 facts, pero solo 1,147,612 distinct first terms.
    • Si se guarda como (Term, [Term]) en lugar de (Term, Term), la largest layer baja a unos 184,491,407 bytes.
    • Es una reducción de aproximadamente 11.37 veces frente a los 2 GB iniciales.
  • En la actualización del 2025-07-02 se aplicó la primera optimización.
    • El largest batch pasa a ser 343,735,382 bytes, es decir, el valor teórico de 343,735,350 bytes más 32 bytes.
    • El tiempo de ejecución bajó de unos 115 segundos a unos 95 segundos, una mejora de alrededor del 20%.

Representación layered trie

  • En la actualización del 2025-07-20, layered trie ya pudo funcionar.
  • Se compara la representación row-oriented con la representación layered trie orientada a columnas.
    • 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
  • layered trie es un método que suprime la repetición de las columnas iniciales en una representación row ordenada.
  • Cada columna es una lista de listas de valores.
    • Cada lista es un conjunto ordenado de valores distinct que corresponde al prefix de la columna anterior.
    • La cantidad de listas de una columna es igual al total de ítems de la columna anterior.
  • Puede verse como un árbol, pero la implementación real se mantiene por columnas.
  • La ventaja es que permite realizar búsqueda, join, diferencia y merge por unidades de prefix.
  • Cuando casi no hay valores distinct y conviene más ver la fila completa de una vez, el enfoque row-oriented puede ser más ventajoso.
  • Como abstracción común se introdujo el trait FactContainer.
    • form
    • len
    • apply
    • join
    • except
    • merge
  • apply rastrea los rangos de cada layer con un stack explícito en lugar de recursión, construye filas y se las pasa a action.
  • align es un helper común que alinea los prefix de dos layered trie para compararlos.
    • Ordering::Less: rango presente solo en self
    • Ordering::Greater: rango presente solo en other
    • Ordering::Equal: el prefix de longitud arity está presente en ambos lados
  • join, except y merge están implementados sobre align.
    • join despliega las extensiones restantes sobre el prefix común y hace un cross join.
    • except injerta en TrieBuilder los rangos que existen solo en self.
    • merge injerta una vez cada uno de los rangos solo-self, solo-other e iguales, según corresponda.

Optimización de ancho fijo y rendimiento

  • Cuando se puede subir a [u8; 4] de ancho fijo, el rendimiento de comparación mejora mucho.
  • layered trie puede aplicar optimización de ancho fijo por columna, así que a largo plazo podría tener ventaja sobre row.
  • En except y merge fue fácil aplicar upgrade y downgrade, pero aplicarlo a join fue más difícil por problemas de tipos en 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
  • Actualmente, cerca de 2/3 del tiempo se consume dentro de join
  • Parece haber margen para al menos otra mejora de ~2x en la optimización de joins
  • Un intento de simplemente reordenar el inner loop no produjo una mejora medible

Especialización al nivel de código compilado

  • Si se detectan términos del mismo largo y hechos con la misma aridad, se puede ver Vec<u8> como algo tipo Vec<[[u8; B]; T]>
  • Esta forma permite que Rust conozca mejor la forma de los datos, reduciendo el costo de verificar bounds y longitudes, y haciendo las comparaciones especialmente baratas
  • Las comparaciones se usan en varios puntos de datatoad
    • ordenamiento y eliminación de duplicados de batches de hechos
    • fusión de batches
    • fusión de claves de join
    • filtrado de hechos nuevos comparándolos con hechos existentes
  • El rendimiento base es el siguiente
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
  • La optimización de ordenamiento se probó haciendo unsafe transmute de Vec<u8> a Vec<[u8; 8]> para aplicar sort y 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
  • La optimización de fusión se implementó con un enfoque simple: concatenar las dos entradas y luego aplicar sort y 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
  • Aún no se alcanza el rendimiento compilado de datafrog
  • El costo restante de las comparaciones también está en join y antijoin, y el plan es volver a revisar la misma oportunidad de optimización al pasar a una estructura basada en trie
  • Se está buscando una forma de eliminar unsafe, y se agrega la conclusión de que el código unsafe debería evitarse

Trabajo que aún queda

  • Spill a disco

    • El almacenamiento columnar está compuesto por pocas asignaciones grandes
    • Al crearlo, se puede escribir a archivo en lugar de memoria y volver a usarlo mediante memory map

  • Evaluación distribuida

    • Join, eliminación de duplicados y verificación de distinctness se basan en igualdad de claves
    • Las claves y sus datos correspondientes pueden distribuirse entre varios workers
    • Se puede escalar incluso a múltiples procesos con timely_communication

  • Evaluación de reglas en streaming

    • El join actual usa joins binarios y salida materialized
    • Si existen los índices necesarios, se puede construir un plan que no materialice el estado interno
    • Aquí también se abordará worst-case optimal join

  • Especialización de custom representation

    • Existe la idea de detectar transitive closure y especializarla para strongly connected component decomposition
    • Para equivalence relation se puede usar una estructura union-find
    • bddbddb y factorized databases también tratan temas relacionados

  • Búsqueda de hechos relacionados

    • Hay que entender y aplicar demand transform
    • Se considera una transformación necesaria para la exploración interactiva de Datalog

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-06-16
Opiniones en Hacker News

  • Me parece curioso ver que este artículo llegó al primer lugar.
    Ahora mismo estoy creando un juego de estrategia en tiempo real con Differential Datalog y Rust, y hago que DDL se encargue de la lógica del juego.
    En gran parte es más bien una excusa para conocer ideas nuevas y meterme en una interminable cadena de yak shaving.
    https://github.com/vmware-archive/differential-datalog

    • Parece una demo genial hecha con ddlog.
      Como referencia, el equipo de ddlog ahora fundó Feldera, y también vale la pena considerar usar DBSP directamente desde Rust.
      https://github.com/feldera/feldera
    • Me pregunto si, mezclando el repositorio del artículo original con salsa, el crate que impulsa el analizador de Rust, se podría crear una especie de differential datalog a lo Frankenstein.
      https://github.com/salsa-rs/salsa
    • Me da curiosidad cuál es el estado de la implementación y hasta dónde podría llegar.
      DDLog ya no se mantiene activamente, así que resulta todavía más interesante.

  • “Yo, el infame villano, fui invitado medio convencido de que iba a recibir el castigo que hacía tiempo merecía.” — la mejor primera frase que he leído este año en un blog técnico.
    Las intervenciones del narrador también fueron excelentes, y es raro encontrar un texto tan profundo técnicamente que además se lea de forma tan entretenida.
    El recorrido para optimizar las consultas de alias se sintió como una novela policial, y uno como lector también termina sufriendo con el uso de 50 GB de memoria y celebrando cuando baja a 5 GB.
    Tanto el código como el texto son excelentes.

  • Avancé un poco en el port de mangle datalog a Rust.
    Está en https://github.com/google/mangle/tree/main/rust y vive en el mismo repositorio que la implementación en Go.
    No es de alta prioridad y además hay algo de síndrome del segundo sistema, así que el progreso es lento.
    Mangle Rust apunta a manejar datos de tamaño arbitrario leyendo y escribiendo hechos desde disco mediante memory mapping, mientras que la implementación en Go funciona en memoria.
    Este artículo me gusta porque parsea Datalog y también trata los árboles LSM, y es mucho más fácil de seguir que el material relacionado con datafrog.
    En Rust hay muchas implementaciones de Datalog que usan macros procedurales, como ascent y crepe, pero tienen la desventaja de que es difícil recibir consultas en tiempo de ejecución.
    Para usos de análisis estático donde las consultas y el programa son fijos, el enfoque con macros procedurales quizá sea mejor.

  • Aunque el actual renacimiento de Datalog parece estar perdiendo fuerza, da gusto ver que el núcleo de entusiastas sigue resistiendo.
    La reciente conferencia Datalog 2.0 fue bastante más pequeña que antes, y la segunda conferencia HYTRADBOI también tuvo menos presencia de Datalog.
    En la primera HYTRADBOI, una cuarta parte de las propuestas estaban relacionadas con Datalog.
    También es alentador ver que otras personas compartan proyectos recientes de Datalog.
    Ahora estoy preparando una migración de software a gran escala y creando un pipeline de calidad de datos para una base de datos SQL legacy.
    Si se estructuran bien las consultas, quedan muy legibles, así que creo que Datalog es mucho más útil que SQL para identificar y localizar problemas de calidad de datos.

    • Aunque esté de acuerdo con la dirección general, es difícil tomar la baja asistencia a Datalog 2.0 como un ejemplo representativo del declive de Datalog.
      Datalog 2.0 es un workshop satélite de LPNMR, una conferencia europea relativamente poco conocida, y dio la casualidad de que esa conferencia se realizó en Dallas.
      Cuando asistí en persona, el evento también se sintió algo vacío; incluso presenté un paper en el workshop, pero no vi a mucha gente del área.
      Como excepción, sí se notaba la presencia de gente de Europa que presentó el solver Nemo.
      Creo que la baja asistencia de este año muestra mejor que era un workshop satélite de una conferencia que ya no era tan famosa, y que el evento principal además era ICLP, más que una falta de interés por las implementaciones de Datalog.
      Claro que no intento refutar la afirmación más amplia de que queda poca novedad en implementar motores Datalog puros.
      El espacio de investigación ya fue mucho más allá y se movió hacia problemas más exóticos, como streaming (HydroFlow), elección (Dusa) y cosas más cercanas al chase general (el motor de chase de Egglog).
      En general casi nadie discrepa en que el Datalog vanilla es aburrido, pero la saturación hacia adelante monótona y las cláusulas de Horn son una línea base rica y con un panorama de ingeniería de rendimiento bien entendido, sobre la cual es bueno construir teorías más interesantes como semiring o Z-set.

  • Si te parecieron interesantes la máquina de estados y la parte de parsing, también recomiendo la vieja charla de Rob Pike Lexical Scanning in Go.
    https://www.youtube.com/watch?v=HxaD_trXwRE
    Está en Go, pero la mayor parte se puede aplicar fácilmente a otros lenguajes.
    Me gusta que lenguajes modernos como Rust, Zig y Go tengan soporte nativo para Unicode/rune/grafemas.
    Comparados con Java, .NET, C++ o lenguajes de scripting, muchos problemas simplemente desaparecen.

  • En general me gusta el trabajo del autor sobre Datalog, pero preferiría que en los materiales introductorios no enseñara joins binarios.
    Fuera de los casos ideales, los interiores se ensucian rápidamente, y los métodos de joins generales me resultaron mucho más fáciles de generalizar mentalmente.
    https://en.wikipedia.org/wiki/Worst-case_optimal_join_algorithm

  • Hace mucho, durante mis estudios, tuve un breve contacto con Prolog, y tengo una idea general de para qué se usa y en qué es útil, pero no lo entendí en profundidad.
    Desde entonces sigo oyendo que Datalog es increíble, pero no termino de entender qué mejora Datalog respecto de Prolog.
    Acabo de hojear la página de Datalog en Wikipedia y parece que Prolog tiene un rendimiento relativamente malo, mientras que Datalog reduce expresividad y funcionalidades a cambio de mejorar mucho el rendimiento, lo que permite conjuntos de datos más grandes y procesamiento más paralelizado.
    Parece incluir también la pérdida de completitud de Turing, pero me pregunto si eso es lo central o si estoy totalmente errado.

    • Por lo que sé, Prolog parece declarativo en el sentido de que, si uno solo codifica relaciones, encuentra la respuesta; pero en la práctica depende mucho del orden de las reglas y también necesita directivas adicionales como “cut”.
      cut no solo evita cálculos desperdiciados, sino que también puede afectar el resultado.
      En cambio, Datalog en general se parece más a una base de datos relacional con otra sintaxis.
    • Datalog es más simple, no es Turing completo y, si mal no recuerdo, usa razonamiento hacia adelante, lo que tiene efectos en cadena sobre sus características de rendimiento y memoria.
      Incluso un espacio de búsqueda trivial pero enorme en Prolog puede consumir tanta memoria en Datalog que ni siquiera sea posible expresarlo.
      Datalog es como un auto de uso diario con CVT, mientras que Prolog se parece más a un auto de F1.
      Más que una mejora, es como una versión parcialmente recortada de Prolog para que la gente no se vuele el pie, y también es mucho más fácil de implementar e incrustar en otras aplicaciones.
      Si estás acostumbrado a Prolog, Datalog por lo general se sentirá frustrante.
      No hay call/3, no hay expansión de términos/objetivos, y Datalog básicamente está diseñado tomando el mínimo común de funcionalidades de Prolog para usarlo en búsquedas interactivas en bases de datos.
      Es fácil escribir código Datalog rápido, pero su techo también es mucho más bajo.
      Prolog también puede escribirse de forma que permita concurrencia, pero es una tarea de nivel intermedio que requiere entender la implementación.
      Guarded Horn Clauses y lenguajes derivados se desarrollaron para formalizar esa parte, pero los avances japoneses posteriores a Prolog son muy difíciles de entender.
      El rendimiento de Prolog depende mucho del programador, de la implementación usada y del contexto en que se use.
      Como Lisp, Prolog también puede usarse para generar código máquina nativo desde un DSL en tiempo de compilación.
      Si entiendes cómo funciona la implementación subyacente y escribes código alineado con eso, puede ser suficientemente rápido.
      Pero para eso hay que escribir código Prolog durante años con una misma implementación.
      También hay mucha investigación sobre optimización de compiladores Prolog, además de casos de implementaciones propietarias.
      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/

  • Si quieres usar Datalog y Rust, cozodb está escrito en Rust y también ofrece una sintaxis de consultas Datalog.

    • Cozodb se ve genial, pero parece estar casi inactivo.
      Lo estuve revisando alrededor de noviembre de 2024 y encontré algunas mejoras fáciles en el backend de almacenamiento SQLite.
      https://github.com/cozodb/cozo/issues/285
    • Cozodb en general funcionó bien según la documentación y fue agradable trabajar con él.
      También lo usé para análisis estático de programas, y por dentro usa árboles ordenados y técnicas de tipos.
      La documentación es suficientemente buena como para compararla con la explicación paso a paso del blog, y el trabajo de optimización de consultas es especialmente interesante.
      Dicho eso, si no trabajas en memoria desde Rust, el costo de serialización de datos es alto, y el proyecto, siendo generosos, está en un estado silencioso.

  • Antes, los fans de Clojure decían que Datalog era mejor que SQL, y que era una pena que todas las bases de datos relacionales usaran SQL.
    Nunca llegué a investigar lo suficiente por qué pensaban eso.

    • Básicamente, Datalog es mucho menos verboso que SQL, separar vistas cuesta mucho menos y ofrece un soporte abrumadoramente mejor para clausuras transitivas.
      http://canonical.org/~kragen/binary-relations empezó como una consulta simple no recursiva, pero la traducción a SQL ya es criminal, y una solución SQL correctamente separada merecería la pena de muerte.
      Hace poco se agregó recursión a ANSI SQL, así que ya no es completamente imposible, pero tiene tres grandes desventajas.
      Primero, accidentalmente hicieron que SQL fuera Turing-completo; en cambio, las consultas Datalog tienen terminación garantizada.
      Segundo, sigue siendo terriblemente tosco de usar.
      Tercero, por la primera razón, muchas veces no se implementa por completo, así que es difícil confiar en él.
    • El dialecto Clojure/Datomic es difícil de entender, pero estoy de acuerdo con la dirección general.
      Si quieres probar Datalog en línea en un entorno de notebook amigable, recomiendo Percival.
      https://percival.ink/
      En las implementaciones de Datalog en general no existe un estándar equivalente a “ANSI SQL”, pero una vez que aprendes las ideas centrales, los demás Datalog no son tan difíciles.
      También inicié un fork de Percival que compila Datalog a SQLite, así que si quieres ver cómo ambos expresan lo mismo, puedes revisarlo.
      https://percival.jake.tl/
      Las agregaciones y los joins más avanzados todavía están incompletos, pero las formas básicas funcionan bien.
      Logica es un compilador Datalog→SQL mucho más serio y completo, creado por un investigador de Google, que compila a BigTable, DuckDB y algunos dialectos SQL.
      https://logica.dev/
      Donde Datalog se vuelve más de un orden de magnitud más fácil es al manejar consultas/reglas recursivas.
      También es posible en SQL, pero se siente más o menos como beber Play-Doh con un popote.
      Materialize.com de Frank tiene una forma SQL “WITH MUTUALLY RECURSIVE” mucho mejor que el antiguo enfoque recursivo de ANSI SQL, y Notion la está evaluando para consultas de carga de páginas y sincronización de datos.
      https://materialize.com/blog/recursion-in-materialize/
      Feldera también tiene una forma parecida para vistas recursivas.
      https://www.feldera.com/blog/recursive-sql-queries-in-feldera
      Me gusta que Feldera permita crear cada “regla” o subvista como una sentencia separada, en lugar de meterlo todo en una única sentencia enorme.
      La principal desventaja que vi al probarlo es que el dialecto SQL de Feldera tiene bastantes restricciones heredadas de Apache Calcite, mientras que el dialecto SQL de Materialize se esfuerza mucho por mantener compatibilidad con PostgreSQL.

  • Qué bueno, un nuevo artículo de McSharry.
    La última vez que revisé, parecía que VMWare se había alejado de differential datalog.

    • El equipo de Differential Datalog fundó Feldera.
      https://www.feldera.com/
      Parece que pasaron de differential Datalog a differential SQL, probablemente porque se dieron cuenta de que vender Datalog es realmente difícil.