TimelyDataflow / differential-dataflow

An implementation of differential dataflow using timely dataflow on Rust.
MIT License
2.59k stars 184 forks source link

Demonstrate Equality Saturation #525

Open frankmcsherry opened 1 month ago

frankmcsherry commented 1 month ago

A demonstration of (my understanding of) equality saturation, where one represents AST using identifiers, introduce exogenous equivalences between identifiers (e.g. as from a WHERE foo = bar predicate), and then iteratively establish further equivalences based on the equivalence of AST node inputs (equivalent inputs + equivalent operator = equivalent result, I think).