Optimizing sparql query evaluation with a worst-case cardinality estimation based on statistics on the data

Louis Jachiet 1 Pierre Genevès 1 Nabil Layaïda 1
1 TYREX - Types and Reasoning for the Web
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : sparql is the w3c standard query language for querying data expressed in the Resource Description Framework (rdf). There exists a variety of sparql evaluation schemes and, in many of them, estimating the cardinality of intermediate results is key for performance, especially when the computation is distributed and the datasets very large. For example it helps in choosing join orders that minimize the size of intermediate subquery results. In this context, we propose a new cardinality estimation based on statistics about the data. Our cardinality estimation is a worst-case analysis tailored for sparql and capable of taking advantage of the implicit schema often present in rdf datasets (e.g. functional dependencies). This implicit schema is captured by statistics therefore our method does not need for the schema to be explicit or perfect (our system performs well even if there are a few " violations " of these implicit dependencies). We implemented our cardinality estimation and used it to optimize the evaluation of sparql queries: equipped with our cardinality estimation, the query evaluator performs better against most queries (sometimes by an order of magnitude) and is only ever slightly slower.
Type de document :
Pré-publication, Document de travail
Domaine :
Liste complète des métadonnées

Contributeur : Tyrex Equipe <>
Soumis le : jeudi 18 mai 2017 - 09:57:46
Dernière modification le : jeudi 15 juin 2017 - 09:09:23


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01524387, version 1



Louis Jachiet, Pierre Genevès, Nabil Layaïda. Optimizing sparql query evaluation with a worst-case cardinality estimation based on statistics on the data. 2017. <hal-01524387>



Consultations de
la notice


Téléchargements du document