Index Merging

Indexes play a vital role in decision support systems by reducing the cost of answering complex queries. A popular methodology for choosing indexes that is adopted by database

administrators as well as automatic tools is: (a) Consider poorly performing queries in the workload. (b) For each query, propose a set of candidate indexes that potentially

benefits the query. (c) Choose a subset from the candidate indexes in (b). Unfortunately, such a strategy can result in significant storage and index maintenance cost. In this paper,

we present a novel technique called index merging to address the above shortcoming. Index merging can take an existing set of indexes (perhaps optimized for individual queries in the workload), and produce a new set of indexes with significantly lower storage and maintenance overhead, while retaining almost all the querying benefits of the initial set of

indexes. We present an efficient algorithm for index merging, and demonstrate significant savings in index storage and maintenance by virtue of index merging, through experiments

on Microsoft SQL Server 7.0.

PDF file

In  15th International Conference on Data Engineering

Publisher  IEEE Computer Society
Copyright © 2007 IEEE. Reprinted from IEEE Computer Society. This material is posted here with permission of the IEEE. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to By choosing to view this document, you agree to all provisions of the copyright laws protecting it.


> Publications > Index Merging