Research

We study constant-delay enumeration after linear preprocessing for acyclic conjunctive queries with self-joins and projections, with atoms of arity at most two. We give new sufficient conditions through recursive patching and identify structural obstructions under standard fine-grained assumptions. These results narrow the gap toward a dichotomy, while leaving open cases related to enumeration with delay linear in the domain size.

Query optimization remains difficult even for worst-case optimal join algorithms: on the same database, two variable orders can differ by orders of magnitude in runtime. We present FRANTIC, which brings factorization to adaptive worst-case optimal join processing. FRANTIC uses reinforcement learning to choose variable orders during execution, avoiding a separate upfront optimization phase. To speed up convergence, we introduce Factorized UCT, a new Upper Confidence Bound approach that exploits the factorized structure of the variable-order search space. We will present early results on both components of FRANTIC: the runtime of our factorized join algorithm, which can improve over earlier systems by more than two orders of magnitude, and the convergence behavior of the adaptive optimizer.

Columnar databases start to leverage indexes to enhance bottleneck queries efficiency. To decide if an index may be useful or not in row-oriented systems, a commonly used tool is a “What-If” API. It returns an estimation of the benefit of an index without constructing it, saving time and resources at the cost of possible mistakes in the prediction. Moreover, to have a complete auto-tuning database, recent researches leverage Machine Learning to have an automatic database administrator that tunes the database configuration using workload knowledge and “What-If” calls. As column-oriented databases are just starting to leverage indexes, there is yet no such tool specifically designed for these systems. In this work, we propose three contributions: heuristics for segment-aware access paths costs estimations in column-oriented databases, a hypothetical index benefit estimation designed for column-oriented databases (limited to hash indexes), and the use of quantile regression to trade-off precision and risk.

This work studies the enumeration of answers to conjunctive queries. Research on this topic typically focuses on conjunctive queries without self-joins. We want to work towards a dichotomy that allows us to know if a conjunctive query with self-joins can be enumerated with optimal time guarantees: linear time before the first answer and constant delay between answers. In this work, we have found a sufficient and necessary conditions. However, we have examples that we can not classify and can lead to new work on the subject.

Some CQs are in DelayCLin: we can enumerate all their answers with constant delay between answers after linear preprocessing. We have a dichotomy for classifying which CQs without self-joins are in DelayCLin, but this dichotomy is not correct for CQs with self-joins. As CQs often have self-joins, our goal with this internship is to find a sufficient condition and a necessary condition for acyclic CQs with self-joins.

Columnar databases start to leverage indexes to enhance bottleneck queries efficiency. To decide if an index may be useful or not in row-oriented systems, a commonly used tool is a “What-If” API. It returns an estimation of the benefit of an index without constructing it, saving time and resources at the cost of possible mistakes in the prediction. Moreover, to have a complete auto-tuning database, recent researches leverage Machine Learning to have an automatic database administrator that tunes the database configuration using workload knowledge and “What-If” calls. As column-oriented databases are just starting to leverage indexes, there is yet no such tool specifically designed for these systems. In this work, we propose three contributions: heuristics for segment-aware access paths costs estimations in column-oriented databases, a hypothetical index benefit estimation designed for column-oriented databases (limited to hash indexes), and the use of quantile regression to trade-off precision and risk.

This work studies the enumeration of answers to conjunctive queries. Research on this topic typically focuses on conjunctive queries without self-joins. We want to work towards a dichotomy that allows us to know if a conjunctive query with self-joins can be enumerated with optimal time guarantees: linear time before the first answer and constant delay between answers. In this work, we have found a sufficient and necessary conditions. However, we have examples that we can not classify and can lead to new work on the subject.