Query optimization is a common task performed by database administrators and application designers in order to tune the overall performance of the database system. In several applications, the currently available Database Management System is inadequate to support the comparison between the group of tuples with their attributes and values. Currently, databases are used in almost all corporate and business applications that handle a huge amount of data. The complex SQL queries consist of scalar-level operations are often formed to obtain even very simple set-level semantics. Such queries are not only difficult to write but also challenging for a database engine to optimize. To overcome this problem, in this paper we developed an effective algorithm using Filtered Bitmap Index Approach for processing queries with set predicates. It eliminates the necessity of processing the entire Bitmap array index for the required tables and speeds up the query processing significantly. Experimental results show that our approach outperforms the existing algorithm to process queries with set predicates.

Bitmap array Index, Set predicates, Set-level semantics, SQL, Filtered Bitmap index, Processing queries, Optimizing queries

[1] S. Helmer and G. Moerkotte, “Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates,” Proc. Int’l Conf. Very Large Databases (VLDB), 1996.
[2] K. Ramasamy, J. Patel, R. Kaushik, and J. Naughton, “Set Containment Joins: The Good the Bad and the Ugly,” Proc. 26th Int’l Conf. Very Large Data Bases (VLDB), 2000.
[3] Surajit Chaudhuri, Kyuseok Shim, “Query optimization in the presence of Foreign functions”, Published in the Proceedings of the 19th International Conference on Very Large Data Bases 03/2000;
[4] J. Chen, D. J. DeWitt, F. Tian, and Y. Wang. NiagaraCQ, “A scalable continuous query system for internet databases”, Published in Proc. SIGMOD, pages 379–390, 2000.
[5] J. Albrecht, W. Hümmer, W. Lehner, L. Schlesinger, “Query Optimization By Using Derivability In a Data Warehouse Environment”, Published in the Proceedings of the 3rd ACM international workshop on Data warehousing and OLAP, DOLAP -2000, pages 49-56.
[6] Ying Wah Teh, A. B. Zaitun, “Query Processing Techniques in Data Warehousing Using Cost Model”, Published in the Electronic Journal of Information Systems in developing Countries, Volume 3, 2000.
[7] D. Rinfret, P. O’Neil, and E. O’Neil, “Bit-Sliced Index Arithmetic,” Proc. ACM SIGMOD Int’l Conf. Management of Data, pp. 47-57,2001.
[8] Ralf Rantzaua, Leonard D,. Shapirob, Bernhard Mitschanga and Quan Wangc, “Algorithms and Applications for Universal Quantification in Relational Databases”, Published in Information Systems, Special issue: Best papers from EDBT 2002, Volume 28, Issue 1-2, 01 March 2003.
[9] R. Fagin, A. Lotem, and M. Naor, “Optimal Aggregation Algorithms for Middleware”, Published in Computer and System Sciences, vol. 66, no. 4, pp. 614-656, 2003.
[10] M. A. Hammad, M. J. Franklin, W. G. Aref, and A. K.Elmagarmid, “Scheduling for shared window joins over datastreams”, published in Proc. VLDB, pages 297–308, 2003.
[11] N. Mamoulis, “Efficient Processing of Joins on Set-Valued Attributes,” Proc. ACM SIGMOD Int’l Conf. Management of Data,pp. 157-168, 2003.
[12] S. Melnik and H. Garcia-Molina, “Adaptive Algorithms for Set Containment Joins,” ACM Trans. Database Systems, vol. 28, no. 1,pp. 56-99, 2003.
[13] I.F. Ilyas, W.G. Aref, and A.K. Elmagarmid, “Supporting Top-k Join Queries in Relational Databases”, Published in VLDB J., vol. 13, no. 3, pp. 207-221, 2004.
[14] Bernd Hafenrichter, Werner Kießling, “Optimization of Relational Preference Queries”, published in Proc. ADC `05 Proceedings of the 16th Australasian database conference - Volume 39.
[15] Alaa Aljanaby, Emad Abuelrub, Jordan and Mohammed Odeh, “A Survey of Distributed Query Optimization”, published in The International Arab Journal of Information Technology, Vol. 2, No. 1, January 2005.
[16] Giovanni Maria Sacco, “Truly Adaptive Optimization: The Basic Ideas”, published in Database and Expert Systems Applications(DEXA), volume 4080 of Lecture Notes in Computer Science, page 751-760, Springer, 2006.
[17] C. Olston, B. Reed, U. Srivastava, R. Kumar, and A. Tomkins, “Pig Latin: A Not-so-Foreign Language for Data Processing,” Proc. ACM SIGMOD Int‟l Conf. Management of Data, pp. 1099-1110, 2008.
[18] Mingsheng Hong, Mirek Riedewald, Christoph Koch, Johannes Gehrke, Alan Demers, “Rule-Based Multi-Query Optimization”, Published in Proce..
[19] Pawan Meena, Arun Jhapate & Parmalik Kumar, "Framework for Query Optimization", published in the International Journal of Computer Science and Information Security, Vol. 9, No. 10, October 2011.
[20] Hui Zhao, Shuqiang Yang, Zhikun Chen, Songcang Jin, Hong Yin and Long Li, ”MapReduce model-based optimization of range queries”, Published in 2012, 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2012).
[21] Bin He,Hui-l Hsiao, Member IEEE, Ziyang Liu ,Yu Huang,and Yi Chen,Member,IEEE, “Efficient Iceberg Query Evaluation Using Comressed Bitmap Index”, IEEE Transactionson K1nowledge and Data Engineering , Vol. 24, No. 9, SEPTEMBER 2012.
[22] Davide Martinenghi and Marco Tagliasacchi, ” Cost-Aware Rank Join with Random and Sorted Access”, Published in the IEEE Transactions On Knowledge And Data Engineering, VOL. 24, NO. 12, DECEMBER 2012.
[23] Christian Politz and Ralf Schenkel,” Ranking under tight budgets”, Published in 2012 23rd International Workshop on Database and Expert Sytems Applications.
[24] Swati Jain and Paras Nath Barwal, “Performance Analysis of Optimization Techniques for SQL Multi Query Expressions over Text Databases in RDBMS”, Published in the International Journal of Information & Computation Technology, Volume 4, no. 8, 2014.
[25] Chengkai Li, Bin He, Ning Yan, Muhammad Assad Safiullah ”Set Predicates in SQL: Enabling Set-Level Comparisons for Dynamically Formed Groups” IEEE Transactions on Knowledge and Data Engineering , Vol. 26, No. 2, FEBRYARY 2014.
[26] Jayant Rajurkar1 T. Khan2, "A System for Query Processing and Optimization in SQL for Set Predicates using Compressed Bitmap Index", International Journal for Scientific Research & Development Vol. 3, Issue 02, 2015.
[27] A.K. Dwivedi1, A.K. Sharma,“A Framework For Processing Keyword-Based Queries In Relational Databases For Exact Record”, International Journal of Computer Sciences and Engineering, Vol. 2, issue 8, 2014.