Relational e-matching

Abstract

We present a new approach to e-matching based on relational join; in particular, we apply recent database query execution techniques to guarantee worst-case optimal run time. Compared to the conventional backtracking approach that always searches the e-graph “top down”, our new relational e-matching approach can better exploit pattern structure by searching the e-graph according to an optimized query plan. We also establish the first data complexity result for e-matching, bounding run time as a function of the e-graph size and output size. We prototyped and evaluated our technique in the state-of-the-art egg e-graph framework. Compared to a conventional baseline, relational e-matching is simpler to implement and orders of magnitude faster in practice.

BibTeX

@article{2022-popl-rematch,
  title     = {Relational E-Matching},
  author    = {Zhang, Yihong and Wang, Yisu Remy and Willsey, Max and Tatlock, Zachary},
  journal   = {Proceedings of the ACM on Programming Languages},
  number    = {POPL},
  year      = {2022},
  url       = {https://doi.org/10.1145/3498696},
  doi       = {10.1145/3498696},
  publisher = {Association for Computing Machinery},
}

📝 publications index