Systems and methods to provide two bottom up path matching solutions and one post processing solution for evaluating value predicates and tree pattern queries. The first path matching method triggers the matching whenever a leaf query step is seen and stores the prefix sub-matches in a cache for reuse. The second path matching method is an NFA (non-deterministic finite state automata) based solution through a post-order traversal of the XML document tree. The post processing method relies on a compact encoding the path results, which avoids redundant value predicate, join evaluations and any duplicate elimination, sort and grouping operations.