APPLICATION OF DYNAMIC PROGRAMMING FOR THE TASK OF SELECTING A QUERY PLAN IN POSTGRESQL RELATIONAL DATABASE MANAGEMENT SYSTEM

Modern databases used in various fields of science and technology operate with huge amounts of information. As a consequence, the task of accelerating the work with such data is undoubtedly urgent. The article presents one of the possible approaches to solving such a problem – optimization of query plan construction. A query plan is a specific series of data access operations or string joins that the DBMS needs to perform to obtain the result. The main idea is to find the optimal solution that achieves the minimum cost of all the operations required to execute the query. The method for upward dynamic programming was adapted to solve the extremal problem. The comparison of the considered approach with the traditional method of query plan selection on the basis of genetic algorithm has been carried out. It is shown that when the number of tables is more than 28 the presented method of upward dynamic programming requires execution time two times less than the standard method based on genetic algorithm. According to the computational experiment, the query planning time using the method decreases 3–4 times compared to the standard method. The article states that it is more rational to use upward dynamic programming when executing a query with a large number of tables. The planning and execution time during the experiment was considered to be actual.