Analysis of a deferred and incremental update strategy for secondary indexes

摘要

Many relational database systems use secondary indexes to reduce the access cost of retrieving data in response to a user's query. However, a secondary index incurs an additional cost due to the update maintenance of the index. In some cases, this cost may be greater than the cost to update the desired tuples. This paper examines a deferred index update strategy which does an incremental update of the index. The approach introduced, which uses a differential file, can reduce the cost of updating a secondary index by slightly increasing the cost that will be associated with searching the secondary index. This is true as long as the differential file size does not become too large. As such, a model is presented for solving the distribution of the size of the differential file. The maximum size of the differential file is predicted by interpreting this distribution. In addition, the analytical results are compared with simulation results.