Skip to Main content Skip to Navigation
Conference papers

A Cost Estimation Technique for Recursive Relational Algebra

Muideen Lawal 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 : With the increasing popularity of data structures such as graphs, re-cursion is becoming a key ingredient of query languages in analytic systems. Recursive query evaluation involves an iterative application of a function or operation until some condition is satisfied. It is particularly useful for retrieving nodes reachable along deep paths in a graph. The optimization of recursive queries has remained a challenge for decades. Recently, extensions of Codd's classical relational algebra to support recursive terms and their optimisation gained renewed interest [10]. Query optimization crucially relies on enumeration of query evaluation plans and on cost estimation techniques. Cost estimation for recursive terms is far from trivial, and received less attention. In this paper, we propose a new cost estimation technique for recursive terms of the extended relational algebra. This technique allows to select an estimated cheapest query plan, in terms of computing resources usage e.g. memory footprint, CPU and I/O and evaluation time. We evaluate the effectiveness of our cost estimation technique on a set of recursive graph queries on both generated and real datasets of significant size, including Yago: a graph with more than 62 millions edges and 42 million nodes. Experiments show that our cost estimation technique improves the performance of recursive query evaluation on popular relational database engines such as PostgreSQL.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-03004218
Contributor : Tyrex Equipe <>
Submitted on : Friday, November 13, 2020 - 3:23:00 PM
Last modification on : Tuesday, November 24, 2020 - 4:00:19 PM

File

master.pdf
Files produced by the author(s)

Identifiers

Collections

UGA | CNRS | INRIA | LIG

Citation

Muideen Lawal, Pierre Genevès, Nabil Layaïda. A Cost Estimation Technique for Recursive Relational Algebra. CIKM 2020 - 29th ACM International Conference on Information and Knowledge Management, Oct 2020, Virtual Event, France. ⟨10.1145/3340531.3417460⟩. ⟨hal-03004218⟩

Share

Metrics

Record views

22

Files downloads

67