The Journal of the Korea institute of electronic communication sciences (한국전자통신학회논문지)

Korea Institute of Electronic Communication Science (한국전자통신학회)
권호 표지
DOI QR코드

DOI QR Code

A Range Query Method using Index in Large-scale Database Systems

대규모 데이터베이스 시스템에서 인덱스를 이용한 범위 질의 방법

  • 김치연 (목표해양대학교 해양컴퓨터공학과)
  • Received : 2012.08.22
  • Accepted : 2012.10.05
  • Published : 2012.10.31
Download PDF
⟨ Previous Next ⟩

Abstract

As the amount of data increases explosively, a large scale database system is emerged to store, retrieve and manipulate it. There are several issues in this environments such as, consistency, availability and fault tolerance. In this paper, we address a efficient range-query method where data management services are separated from transaction management services in large-scale database systems. A study had been proposed using partitions to protect independence of two modules and to resolve the phantom problem, but this method was efficient only when range-query is specified by a key. So, we present a new method that can improve the efficiency when range-query is specified by a key attribute as well as other attributes. The presented method can guarantee the independence of separated modules and alleviate overheads for range-query using partial index.

최근 데이터 양이 폭발적으로 증가함에 따라, 데이터를 저장하고 검색하고 다루기 위한 대규모 데이터베이스 시스템이 등장하였다. 이 환경에서는 일관성과 가용성, 결함 허용 등 다양한 이슈가 존재한다. 이 논문에서는 데이터 관리와 트랜잭션 관리가 분리된 구조를 갖는 대규모 데이터베이스 시스템에서, 효율적인 범위 질의 방법에 대하여 다룬다. 동일한 구조에서 두 모듈의 독립성을 보장하고, 팬텀 문제를 해결하기 위하여 파티션을 이용한 범위 질의 방법에 대한 연구가 있었지만, 범위 질의가 키 값으로 명세되는 경우에만 효율적이었다. 이에 이 논문에서는 키 값이 아닌 다른 속성으로 범위 질의가 주어질 때 효율을 개선할 수 있는 방법을 제안하고자 한다. 제안하는 방법에서는 분리된 두 모듈의 독립성은 보장하며, 부분 인덱스를 사용함으로써 범위 질의를 위한 오버헤드를 줄일 수 있다.

Keywords

References

  1. So Youn Lee, Esteban Meneses, "Survey of Large-scale Database Systems," [Online] https://wiki.engr.illinois.edu/download/attach ments/197298696/survey.pdf
  2. G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. "Dynamo: amazon's highly available key-value store," SIGOPS Oper. Syst. Rev., Vol. 41, pp. 205-220, Oct. 2007. https://doi.org/10.1145/1323293.1294281
  3. F. Chang, J. Dean, S. Ghemawat, W. Hsieh, D. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. Gruber, "Bigtable: A distributed storage system for structured data," In Proceedings of the 7th Conference on USENIX Symposium on Operating Systems Design and Implementatio, Vol. 7, pp. 205-218, 2006.
  4. Jason Baker, Chris Bond, James C. Corbett, JJ Furman, Andrey Khorlin, James Larson, Jean-Michel Leon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. "Megastore: Providing scalable, highly available storage for interactive services," In Proc. CIDR, pp. 223-234, 2011.
  5. A. Lakshman and P. Malik, "Cassandra: a decentralized structured storage system," Operating Systems Review, Vol. 44, No. 2, pp. 35-40, 2010. https://doi.org/10.1145/1773912.1773922
  6. http://en.wikipedia.org/wiki/Range_query
  7. D. Lomet, M. F. Mokbel, "Locking Key Ranges with Unbundled Transaction Services," Proceedings of the VLDB Vol. 2, pp. 265-276, August 2009. https://doi.org/10.14778/1687627.1687658
  8. S. Wu, D. Jiang, B. C. Ooi, and K. L. W. "Towards elastic transactional cloud storage with range query support," In Int'l Conference on Very Large Data Bases (VLDB), Vol. 3, pp. 506-514, 2010.
  9. D. Beaver, S. Kumar, H. C. Li, J. Sobel, and P. Vajgel, ""Finding a needle in haystack: Facebook's photo storage," in OSDI, pp. 47-60, 2010.
  10. David B. Lomet, "Key range locking strategies for improved concurrency," In VLDB '93: Proceedings of the 19th international conference on Very Large Data Bases, pp. 655- 664, 1993
  11. D. DeWitt and J. Gray, ""Parallel database systems: the future of high performance database systems," Commun. ACM, Vol. 35, pp. 85-98, June 1992.