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.