Distance-Based Triple Reordering for SPARQL Query Optimization Full text

Marios Meimaris, George Papastefanatos
Data Engineering (ICDE), 2017 IEEE 33rd International Conference on, pp. 1559-1562. IEEE, 2017
Abstract. SPARQL query optimization relies on the design and execution of query plans that involve reordering triple patterns, in the hopes of minimizing cardinality of intermediate results. In practice, this is not always effective, as many existing systems succeed in certain types of query patterns and fail in others. This kind of trade-off is often a derivative of the algorithms behind query planning. In this paper, we introduce a novel join reordering approach that translates a query into a multidimensional vector space and performs distance-based optimization by taking into account the relative differences between the triple patterns. Preliminary experiments on synthetic data show that our algorithm consistently outperforms established methodologies, providing better plans for many different types of query patterns.