A knowledge-based approach for index selection in relational databases

摘要

DINNER is a knowledge-based tool that assists the administrator of a relational database in the selection of index configurations. Given a set of tables, their statistical properties, and a set of queries on these tables, DINNER recommends an index configuration that includes for each table a primary index and a set of secondary indexes. Although it was proved that the problem is NP-hard, DINNER is capable of handling a practically-useful number of queries (10 queries, half of which are join queries).The database can perform a query with several possible access paths, according to the available indexes. DINNER builds for each query a graph that represents the set of possible solutions (indexes) to be used by the query. For each solution it finds the access path that the database is most likely to choose to perform the query, and estimates the time it takes to perform the access path.In order to find the possible indexes, the access paths that use these indexes, and the time cost of the access paths, DINNER uses knowledge that was elicited from several sources (database administrator (DBA), literature), and represented using several AI representation methods (frames, rules, and logic).After finding the possible indexes, DINNER uses several heuristics to eliminate bad solutions. Then, solutions for all queries are generated. These solutions are searched to find the best one which is the recommendation given by DINNER.The validity of DINNER's recommendations were demonstrated in three ways: examination of a detailed example, a demonstration of the changes in the recommendations as the input is changed, and the evaluation of an expert DBA.