1. Introduction
Relational database management systems (DBMSs) let users specify queries using high level declarative languages such as SQL. The query optimizer of the DBMS is then responsible for finding an efficient execution plan to evaluate the input query. For that purpose, cost-based optimizers search a large space of alternative execution plans, and choose the one that is expected to be evaluated in the least amount of time. In doing so, query optimizers rely on a cost model that estimates the resources that are needed for each alternative plan in consideration.