Eugene Inseok Chong
Jagannathan Srinivasan
ABSTRACT
Any auxiliary structure, such as a bitmap or a B+-tree index, that refers to rows of a table stored as a primary B+-tree (e.g., tables with clustered index in Microsoft SQL Server, or index-organized tables in Oracle) by their physical addresses would require updates due to inherent volatility of those addresses. To address this problem, we propose a mapping mechanism that 1) introduces a single mapping table, with each row holding one key value from the primary B+-tree, as an intermediate structure between the primary B+-tree and the associated auxiliary structures, and 2) augments the primary B+-tree structure to include in each row the physical address of the corresponding mapping table row. The mapping table row addresses can then be used in the auxiliary structures to indirectly refer to the primary B+-tree rows. The two key benefits are: 1) the mapping table shields the auxiliary structures from the volatility of the primary B+-tree row addresses, and 2) the method allows reuse of existing conventional table mechanisms for supporting auxiliary structures on primary B+-trees. The mapping mechanism is used for supporting bitmap indexes on index-organized tables in Oracle9i. The analytical and experimental studies show that the method is storage efficient, and (despite the mapping table overhead) provides performance benefits that are similar to those provided by bitmap indexes implemented on conventional tables.
- Chan, C. Y., Ioannidis, Y.E., "Bitmap Index Design and Evaluation," Proceedings of the ACM SIGMOD Int. Conf. on Management of Data, pp.355--366, 1998. Google Scholar
Digital Library
- Chaudhuri, S. and Dayal, U., "An Overview of Data Warehousing and OLAP Technology," ACM SIGMOD Record, 26(1), pp.65--74, 1997. Google ScholarDigital Library
- Chong, E.I., Das, S., Freiwald, C., Srinivasan, J., Yalamanchi, A., Jagannath, M., Tran, A., Krishnan, R., "B+-Tree Indexes with Hybrid Row Identifiers in Oracle8i," Proceedings of the 17th Int. Conf. on Data Engineering, pp.341--348, Apr. 2001. Google ScholarDigital Library
- Comer, D., "The Ubiquitous B-Tree," Computing Surveys, 11(2), pp.121--137, June 1979. Google ScholarDigital Library
- Helman, P., The Science of Database Management, Richard D. Irwin, Inc., 1994. Google ScholarDigital Library
- Microsoft SQL Server, SQL Server 2000, Sept. 2001. Google ScholarDigital Library
- O'Neil, P. and Quass, D., "Improved Query Performance with Variant Indexes," Proceedings of the ACM SIGMOD Int. Conf. on Management of Data, pp. 38--49, 1997. Google ScholarDigital Library
- Shmueli, O. and Itai, A.: "Maintenance of Views," Proceedings of the ACM SIGMOD Int. Conf. on Management of Data, pp. 240--255, 1984. Google ScholarDigital Library
- Srinivasan, J., Das, S., Freiwald, C., Chong, E.I., Jagannath, M., Yalamanchi, A., Krishnan, R., Tran, A., DeFazio, S., Banerjee, J., "Oracle8i Index-Organized Table and its Applications to New Domains," Proceedings of the 26th Int. Conf. on Very Large Data Bases, pp. 285--296, Sept. 2000. Google ScholarDigital Library
- Srinivasan, J., Murthy, R., Sundara, S., Agarwal, N., DeFazio, S., "Extensible Indexing: A Framework for Integrating Domain-Specific Indexing into Oracle8i," Proceedings of the 16th International Conference on Data Engineering, pp. 91--100, 2000. Google ScholarDigital Library
- Sybase SQL Server, Transact-SQL User's Guide, Document ID:32300-01-1250-02, May 2001.Google Scholar
- The Tandem Database Group, NonStop SQL: "A Distributed, High-performance, High-availability Implementation of SQL," Proceedings of 2nd Int. Workshop on High Performance Transaction Systems, Springer Lecture Notes in Computer Science No. 359. Google ScholarDigital Library
Index Terms
- A mapping mechanism to support bitmap index and other auxiliary structures on tables stored as primary B+-trees
Recommendations
A mapping mechanism to support bitmap index and other auxiliary structures on tables stored as primary B+-trees
Any auxiliary structure, such as a bitmap or a B+-tree index, that refers to rows of a table stored as a primary B+-tree (e.g., tables with clustered index in Microsoft SQL Server, or index-organized tables in Oracle) by their physical addresses would ...
Inverted indexes vs. bitmap indexes in decision support systems
CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge managementBitmap indexes are widely used in Decision Support Systems (DSSs) to improve query performance. In this paper, we evaluate the use of compressed inverted indexes with adapted query processing strategies from Information Retrieval as an alternative. In a ...
Bitmap index-based decision trees
ISMIS'05: Proceedings of the 15th international conference on Foundations of Intelligent SystemsIn this paper we propose an original approach to apply data mining algorithms, namely decision tree-based methods, taking into account not only the size of processed databases but also the processing time. The key idea consists in constructing a ...
Comments