Estimating page fetches for index scans with finite LRU buffers

ABSTRACT

We describe an algorithm for estimating the number of page fetches for a partial or complete scan of a B-tree index. The algorithm obtains estimates for the number of page fetches for an index scan when given the number of tuples selected and the number of LRU buffers currently available. The algorithm has an initial phase that is performed exactly once before any estimates are calculated. This initial phase, involving LRU buffer modeling, requires a scan of all the index entries and calculates the number of page fetches for different buffer sizes. An approximate empirical model is obtained from this data. Subsequently, an inexpensive estimation procedure is called by the query optimizer whenever it needs an estimate of the page fetches for the index scan. This procedure utilizes the empirical model obtained in the initial phase.

REFERENCES

• 1: Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975 [doi>10.1145/360762.360766]
• 2: S. Christodoulakis. Estimating Block Selectivities. Information Systems, 9(1):69-79, 1984.
• 3: Tom Keller , Goetz Graefe , David Maier, Efficient assembly for complex objects, ACM SIGMOD Record, v.20 n.2, p.148-157, June 1991
• 4: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 5: Lothar F. Mackert , Guy M. Lohman, Index scans using a finite LRU buffer: a validated I/O model, ACM Transactions on Database Systems (TODS), v.14 n.3, p.401-424, Sept. 1989 [doi>10.1145/68012.68016]
• 6: Michael V. Mannino , Paicheng Chu , Thomas Sager, Statistical profile estimation in database systems, ACM Computing Surveys (CSUR), v.20 n.3, p.191-221, Sept. 1988 [doi>10.1145/62061.62063]
• 7: R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger. Evaluation Techniques for Storage Hierarchies. IBM Systems Journal, 9(2):78-117, 1970.
• 8: G. C. Steindel and H. G. Madison. A Benchmark Comparison of DB2 and the DBC/1012. In CMG '87, International Conference on Management and Performance Evaluation of Computer Systems, pages 360-369, Orlando, FL, 1987. The Computer Measurement Group, Inc.
• 9: S. J. Waters. Hit Ratios. Computer Journal, 19:21- 24, 1976.
• 10: Joel L. Wolf , Daniel M. Dias , Philip S. Yu, An effective algorithm for parallelizing sort merge joins in the presence of data skew, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.103-115, July 02-04, 1990, Dublin, Ireland [doi>10.1145/319057.319072]
• 11: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]
• 12: Brad T. Vander Zanden , Howard M. Taylor , Dina Bitton, Estimating Block Accessses when Attributes are Correlated, Proceedings of the 12th International Conference on Very Large Data Bases, p.119-127, August 25-28, 1986

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees
  E.5 FILES
      Subjects: Organization/structure

General Terms:
Algorithms, Experimentation, Performance