DSG Seminar Series • ASTral: Fast Rewriting for Query Optimization

Speaker: Darshana Balakrishnan, University at Buffalo

Location: DC 1304

Abstract:

A compiler's optimizer operates over abstract syntax trees (ASTs), continuously applying rewrite rules to replace subtrees of the AST with more efficient ones. Especially on large source repositories, even simply finding opportunities for a rewrite can be expensive, as optimizer traverses the AST naively. Moreover some of the search tasks may be repeated across rewrites which making the search a redundant effort.  In this talk, we look at two orthogonal approaches and explore options for making the search faster through indexing, incremental view maintenance (IVM) and state machines.

Bio: Darshana Balakrishnan is a Software Developer at Amazon Web Services with the Redshift team in Toronto and a final semester Phd candidate at the University at Buffalo. Her prior work on incremental and declarative compilers titled Tree Toaster and Fluid Data Structures has been published at SIGMOD and DBPL.