Optimisation des requêtes distribuées par apprentissage
Martínez-Medina, Lourdes Angélica · HAL (Le Centre pour la Communication Scientifique Directe) · 2014
Distributed data systems are becoming increasingly complex. They interconnect devices (e.g. smartphones, tablets, etc.) that are heterogeneous, autonomous, either static or mobile, and with physical limitations. Such devices run applications (e.g. virtual games, social networks, etc.) for the online interaction of users producing / consuming data on demand or continuously. The characteristics of these systems add new dimensions to the query optimization problem, such as multi-optimization criteria, scarce information on data, lack of global system view, among others.Traditional query optimization techniques focus on semi (or not at all) autonomous systems. They rely on information about data and make strong assumptions about the system behavior. Moreover, most of these techniques are centered on the optimization of execution time only. The difficulty for evaluating queries efficiently on nowadays applications motivates this work to revisit traditional query optimization techniques.This thesis faces the previous challenges by adapting the Case Based Reasoning (CBR) paradigm to query optimization process. This adaptation, associated to a pseudo-random exploration of the search of solutions provides a way to optimize queries when there is no prior knowledge of data. This approach focuses on the optimization of queries using cases generated from the evaluation of similar past queries. A query case comprises: (i) the query (the problem), (ii) the query plan (the solution) and (iii) the measures of computational resources consumed during the query plan execution (the evaluation of the solution). This thesis also concerns the way the CBR process interacts with the query plan generation process, allowing the exploration of the space of solutions. This process uses classical query optimization heuristics and makes decisions randomly when information on data is not available (e.g. for ordering joins, selecting algorithms or choosing message exchange protocols). This process also exploits the CBR principle for generating plans for subqueries, thus accelerating the learning of new cases. The propositions of this thesis have been validated with the CoBRa optimizer developed in the context of the UBIQUEST project.