Optimization of Complex SPARQL Analytical Queries

Analytical queries are crucial for many emerging Semantic Web applications such as clinical-trial recruiting in Life Sciences that incorporate patient and drug profile data. Such queries compare aggregates over multiple groupings of data which pose challenges in expression and optimization of complex grouping-aggregation constraints. While these challenges have been addressed in relational models, the semi-structured nature of RDF introduces additional challenges that need further investigation. Each grouping required in an RDF analytical query maps to a graph pattern subquery with related groups leading to overlapping graph patterns within the same query. The resulting algebraic expressions for such queries contain large numbers of joins, groupings and aggregations, posing significant challenges for present-day optimizers. In this paper, we propose an approach for supporting efficient and scalable RDF analytics that follows the well known technique of simplifying algebraic expressions of RDF analytical queries in a way that enables better optimization. Specifically, the approach is based on a refactoring of analytical queries expressed in the relational-like SPARQL algebra based on a new set of logical operators. This refactoring achieves shared execution of common subexpressions that enables parallel evaluation of groupings as well aggregations, leading to reduced I/O and processing costs, particularly beneficial for scale-out processing on distributed Cloud systems. Experiments on real-world and synthetic benchmarks confirm that such a rewriting can achieve up to 10X speedup over relational-style SPARQL query plans executed on popular Cloud systems.