A framework for the performance analysis of concurrent B-tree algorithms

ABSTRACT

Many concurrent B-tree algorithms have been proposed, but they have not yet been satisfactorily analyzed. When transaction processing systems require high levels of concurrency, a restrictive serialization technique on the B-tree index can cause a bottleneck. In this paper, we present a framework for constructing analytical performance models of concurrent B-tree algorithms. The models can predict the response time and maximum throughput. We analyze three algorithms: Naive Lock-coupling, Optimistic Descent, and the Lehman-Yao algorithm. The analyses are validated by simulations of the algorithms on actual B-trees. Simple and instructive rules of thumb for predicting performance are also derived. We apply the analyses to determine the effect of database recovery on B-tree concurrency.

REFERENCES

• 1: R. Bayer and E.M. McCreight. Organization and maintainance of large ordered indices. Acta fnformalica, 1(3):173-189, 1972.
• 2: R. Bayer and M. Schkolnick. Concurrency of operations on B-trees. Ac~a Informatica, 9"1-21, 1977.
• 3: M. Carey and C.Y. Cheng. B+-tree locking: a performance perspective. 1986. manuscript.
• 4: V. Lanin D. Shasha and J. Schmidt. An Analytical Model for ~he Performance of Concurren~ B- tree algorithms. NYU Ultraeomputer Note 311, NYU Ultracomputer lab, 1987.
• 5: C.S. Ellis. Concurrent search and inserts in 2-3 trees. Ac~a Informatica, 14(1):63-86, 1980.
• 6: J. Gray et. al. One thousand transactions per second. In IEEE Corapcon, pages 96-101, 1985.
• 7: Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983 [doi>10.1145/289.291]
• 8: Theodore Johnson, Approximate analysis of reader and writer access to a shared resource, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.106-114, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 9: T. Johnson and D. Shasha. Random B-~rees wi~h Insert8 and Deletes. Technical Report 453, NYU Dept. of C.S., 1989.
• 10: T. Johnson , D. Shasha, Utilization of B-trees with inserts, deletes and modifies, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.235-246, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73745]
• 11: Leonard Kleinrock, Communication nets; stochastic message flow and delay, Dover Publications, Incorporated, 1972
• 12: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 13: L. Kleinrock. Queueing Systems. Volume 2~ John Wiley, New York, 1976.
• 14: H. T. Kung , Philip L. Lehman, Concurrent manipulation of binary search trees, ACM Transactions on Database Systems (TODS), v.5 n.3, p.354-382, Sept. 1980 [doi>10.1145/320613.320619]
• 15: Vladimir Lanin , Dennis Shasha, A symmetric concurrent B-tree algorithm, Proceedings of 1986 ACM Fall joint computer conference, p.380-389, November 1986, Dallas, Texas, United States
• 16: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• 17: J.K. Metzger. Managi~zg Simultaneous Open- ,ions in Large Ordered Indezes. Technical Report, Teehnisehe Universitat Munehen, Institut fur informatik, 1975. TUM-Math. report.
• 18: Y. Mond and Y. Raz. Concurrency control in B+-trees databases using preparatory operations. In Ii~h International Conference on Ver~/ Large Databases, pages 331-334~ Stockholm, Aug. 1985.
• 19: N. Goodman P.A. Bernstein and V. Hadzilaeos. Recovery algorithms for database systems, in Proc. iFIP Congress, 1983.
• 20: M. Jipping R. Ford and R. Sehultz. On the Performanee of Concurren~ Tree Algorithms. Technical Report 85-07, University of I~wa, 1985.
• 21: M. Jipping R. Ford, R. Sehultz, and B. Wenhardt. On the performance of concurrent tree algorithms, submitted for publication.
• 22: In Kyung Ryu , Alexander Thomasian, Performance analysis of centralized databases with optimistic concurrency control, Performance Evaluation, v.7 n.3, p.195-211, August 1, 1987 [doi>10.1016/0166-5316(87)90040-X]
• 23: Yehoshua Sagiv, Concurrent operations on B-trees with overtaking, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.28-37, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325409]
• 24: D. Shasha. What good are concurrent search structure algorithms for databases anyway? Da~abase Engineering, 8(4):84-90, 1985.
• 25: H. Wedekind. On the selection of access paths in a data base system, in J.W. Klimbie and K.L. Koffeman, editors, Database Management, pages 385-397, North Holland Publishing Company, 1974.
• 26: Y. C. Tay , Nathan Goodman , R. Suri, Locking performance in centralized databases, ACM Transactions on Database Systems (TODS), v.10 n.4, p.415-462, Dec. 1985 [doi>10.1145/4879.4880]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory