Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Horton: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs

Mohamed Sarwat, Sameh Elnikety, Yuxiong He, and Mohamed F. Mokbel

Abstract

Horton is a graph query processing system that executes declarative reachability queries on a partitioned attributed multi-graph. It employs a query language, query optimizer, and a distributed execution engine. The query language expresses declarative reachability queries, and supports closures and predicates on node and edge attributes to match graph paths. We introduce three algebraic graph operators, select, traverse, and join, and a query is compiled into an execution plan containing these operators. As graph reachability queries access the graph elements in a random access pattern, the graph is therefore maintained in the main memory of a cluster of servers. We develop a distributed execution engine that processes a query plan in parallel on the graph servers. Since the query language is declarative, we build a query optimizer that uses graph statistics to estimate predicate selectivity. We experimentally evaluate the system performance using synthetic graphs as well as a real graph from an application that uses reachability queries in a production deployment. The evaluation shows (1) the efficiency of the optimizer in reducing query execution time, (1) system scalability with the size of the graph and with number of servers, and (3) the convenience of using declarative queries.

Details

Publication typeInproceedings
Published inVLDB
> Publications > Horton: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs