Tree-Based Query Optimization

Concepts: pyQueryPlanTree, pyPredicatePushdown, pyOptimizerDFS

Every SQL query you write gets parsed into a tree. SELECT, FROM, WHERE, JOIN, GROUP BY — these become nodes in an abstract syntax tree (AST). The database's query optimizer traverses this tree, applies transformation rules, and rewrites it into a more efficient form. The two most important transformations — predicate pushdown and join reordering — are both tree traversal algorithms. Understanding this at a conceptual level is staff-level data engineering knowledge. Interviewers at companies with custom query engines (Databricks, Snowflake, Meta, Google) ask about this in senior design rounds. Query Plan as a Tree Predicate Pushdown: DFS Tree Rewriting Predicate pushdown moves Filter nodes as far down the tree as possible, toward the leaf Scan nodes. The goal: filter rows before they enter