Adaptive Index Utilization in Memory-Resident Structural Joins

Bingsheng He, Qiong Luo, Byron Choi

Research output: Contribution to journalJournal articlepeer-review

2 Citations (Scopus)


We consider adaptive index utilization as a fine-grained problem in autonomic databases in which an existing index is dynamically determined to be used or not in query processing. As a special case, we study this problem for structural joins, the core operator in XML query processing, in the main memory. We find that index utilization is beneficial for structural joins only under certain join selectivity and distribution of matching elements. Therefore, we propose adaptive algorithms to decide whether to use an index probe or a data scan for each step of matching during the processing of a structural join operator. Our adaptive algorithms are based on the history, the look-ahead information, or both. We have developed a cost model to facilitate this adaptation and have conducted experiments with both synthetic and real-world data sets. Our results show that adaptively utilizing indexes in a structural join improves the performance by taking advantage of both sequential scans and index probes.

Original languageEnglish
Pages (from-to)772-788
Number of pages17
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number6
Publication statusPublished - Jun 2007

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • Adaptive query processing
  • Index utilization
  • Memory-resident systems
  • Structural joins


Dive into the research topics of 'Adaptive Index Utilization in Memory-Resident Structural Joins'. Together they form a unique fingerprint.

Cite this