Indexing techniques and structured queries for relational databases management systems

Isah Charles  Saidu; Musa Yusuf; Florence Chukwuemeka  Nemariyi; Ayenopwa Comfort  George

doi:10.46481/jnsps.2024.2155

Authors

Isah Charles Saidu
[email protected]

Department of Computer Science, Baze University,Abuja, Nigeria
Musa Yusuf
Department of Computer Science Bingham University, Nasarawa, Nigeria
Florence Chukwuemeka Nemariyi
IT Unit, Bingham University, Nasarawa, Nigeria
Ayenopwa Comfort George
IT Unit, Bingham University, Nasarawa, Nigeria

Keywords:

Relational database systems, Btree index, Hash index, Structured Query Language

Abstract

Indexing has long been used to improve the speed of relational database systems, and choosing an adequate index at design time is critical to the database's efficiency. In this study, it was demonstrated empirically that data access time and data insertion time for moderately large datasets are influenced by the index chosen at design time. However, deletion time is approximately the same. As a result, regardless of the query optimization strategy utilized at runtime, record access/insertion time depends on the type of index employed at design time. This paper presents a comparison of BTree indexes with Hash indexes. It was demonstrated empirically that insertion is substantially faster with the Hash index than with the Btree index, at the expense of a larger Hash index file size. The Btree index is slower due to the rebuild time of Btree indexes during insertion. The empirical results of this study complement that of theoretical results for both Btree and Hash indexes. On the other hand, hash index files are large, restricting their use for applications with rapidly increasing dataset sizes; thus, a tradeoff employing Hash index or Btrees is required. In general, this study proposes Hash indexes for small dataset applications and Btree indexes for large dataset applications on systems with limited memory.

Dimensions

REFERENCES

A. Silberschatz, H. F. Korth & S. Sudarshan,“Indexing and Hashing”, in Database system concepts, 5th Edition ed., Singapore, McGrawHill, 2006, pp. 1–134. https://www.db-book.com/Previous-editions/db5/slide-dir/index.html.

S. Choenni, H. Blanken & T. Chang, “Index selection in relational databases”, in Proceedings of ICCI’93: 5th International Conference on Computing and Information, Sudbury, ON, Canada, 1993, pp. 491-496. https://doi.org/10.1109/ICCI.1993.315323.

A. Arteta, N. G. Blas & L. F. Lopez, “Intelligent indexing—boosting per-´ formance in database applications by recognizing index patterns”, Electronics 9 (2020) 2079. https://doi.org/10.3390/electronics9091348.

MySQL 2015. [Online]. https://dev.mysql.com/doc/refman/5.0/en/history.html. [Accessed 21 May 2015].

T. Lahdenmaki & M. Leach, “SQL Processing”, in¨ Relational Database Index Design and the Optimizers, T. Lahdenmaki and M. Leach (Eds.),¨ John Wiley & Sons, Inc., Hoboken, New Jersey, U.S, 2005, pp. 29–45. https://doi.org/10.1002/0471721379.

R. Ramakrishnan & J. Gehrke, “Database Management Systems”, 3rd Edition ed., Singapore McGrwa-Hill, 2003. https://raw.githubusercontent.com/pforpallav/school/master/CPSC404/Ramakrishnan%20-%20Database%20Management%20Systems%203rd%20Edition.pdf

A. Gani, A. Siddiqa, S. Shamshirband & F. Hanum,“A survey on indexing techniques for big data: taxonomy and performance evaluation”, Knowledge and Information Systems 46 (2016) 0219. https://doi.org/10.1007/s10115-015-0830-y.

R. Ramakrishnan & J. Gehrke, Database Management Systems, McGraw-Hill Inc., Ithaca, New York USA, 2002, pp. 25–29. https://raw.githubusercontent.com/.

S. Chaudhuri, M. Datar & Narasayya, “V.Index selection for databases: A hardness study and a principled heuristic solution”, IEEE transactions on knowledge and data engineering 16 (2004) 1313. https://doi.org/10.1109/TKDE.2004.75.

R. Schlosser, J.Kossmann & M. Boissier, “Efficient scalable multiattribute index selection using recursive strategies”, in 2019 IEEE 35th International Conference on Data Engineering (ICDE), Macao, China, 2019, pp. 1238–1249. https://doi.org/10.1109/ICDE.2019.00113.

R. Yadav, S. Valluri & M. Za¨?t, “AIM: A practical approach to automated index management for SQL databases”, in 2023 IEEE 39th International Conference on Data Engineering (ICDE), Anaheim, California, USA, 2023, pp. 3349-3362. https://doi.org/10.1109/ICDE55515.2023.00257.

P. K. Sadineni, “Comparative study on query processing and indexing techniques in big data”, in 2020 3rd International Conference on Intelligent Sustainable Systems (ICISS), Coimbatore, India, 2020, PP. 933–939. https://doi.org/10.1109/ICISS49785.2020.9315935.

M. Desai, R. G. Mehta & D. P. Rana, “A Survey on Techniques for Indexing and Hashing in Big Data”, in 2018 4th International Conference on Computing Communication and Automation (ICCCA), Noida, India, 2018, pp. 1–6. https://doi.org/10.1109/CCAA.2018.8777454.

Y. Shin, J. Ahn & D. H. Im, “Join optimization for inverted index technique on relational database management systems”, Expert Systems with Applications 198 (2022) 116956. https://doi.org/10.1016/j.eswa.2022.116956.

Z. He, J. Yu, T. Gu & D. Yang, “Query execution time estimation in graph databases based on graph neural networks”, Journal of King Saud University-Computer and Information Sciences 36 (2024) 102018. https://doi.org/10.1016/j.jksuci.2024.102018.

T. Whairit, B. Phadermrod & V. Attasena, “JINDEX: JSON and index search system for plant germplasm database”, Journal of King Saud University-Computer and Information Sciences 35 (2023) 101701. https://doi.org/10.1016/j.jksuci.2023.101701.