Optimizing Branching Path Expressions

Abstract

Path expressions form the basis of most query languages for semistructured data and XML, specifying traversals through graph-based data. We consider the query optimization problem for path expressions that "branch," or specify traversals through two or more related subgraphs; such expressions are common in nontrivial queries over XML data. Searching the entire space of query plans for branching path expressions is generally infeasible, so we introduce several heuristic algorithms and post-optimizations that generate query plans for branching path expressions. All of our algorithms have been implemented in the Lore database system for XML, and we report experimental results over a variety of database and query shapes. We compare optimization and execution times across our suite of algorithms and post-optimizations, and for small queries we compare against the optimal plan produced by an exhaustive search of the plan space.