Logo PTI Logo FedCSIS

Proceedings of the 17th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 30

Flexible user query order for the speculative query support in RDBMS

DOI: http://dx.doi.org/10.15439/2022F154

Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 467471 ()

Full text

Abstract. This paper concerns speculative query execution support for RDBMS based on the dynamic analysis of input (user) query stream. A middleware called the Speculative Layer is presented. Based on a specific multigraph representation of groups of consecutive input queries, called the Speculation Window, the Speculative Layer generates speculative queries for look-ahead execution. These speculatively obtained results are then used while executing user queries. This paper shortly presents the structure of the Speculative Layer and the adopted graph modelling method. Then, a new strategy of queries in the Speculation Window is introduced. Depending on the availability of executed speculative queries results we allow order of user queries in the Speculation Window changes. If a user query were to be executed without the speculative support, we prefer to delay its execution in favour of one of the consecutive user queries, expecting that speculative results obtained in the nearest future will by useful for the delayed query.The experimental results presented in a multithreaded environment, cooperating with a SQLite database, show that the proposed strategy reduces the number of user queries executed without the speculative results. Additional series of experiments verifies that the certain parameters describing the speculative support system, like Speculation Window size, are properly chosen.


  1. A. Estebanez, D.R.Llanos, A.Gonzales-Escribano, “A Survey on Thread-Level Speculation Techniques,” ACM Computing Surveys, vol. 49(2), pp. 1-39, 2017, https://doi.org/10.1145/2938369
  2. A. Sasak-Okoń, “Speculative query execution in Relational databases with Graph Modelling,” in Proceedings of the FEDCSIS 2016, ACSIS, Vol. 8., pp.1383-1387, 2016, https://doi.org/10.15439/2016F123
  3. A. Sasak-Okoń, M.Tudruj, “Graph-Based speculative Query Execution in Relational Databases,” in ISPDC 2017, Innsbruck, Austria, IEEE Explore, https://doi.org/ 10.1109/ISPDC.2017.14
  4. A. Sasak-Okoń, M. Tudruj, “Graph-Based Speculative Query Execution for RDBMS,” in PPAM 2017, LNCS, Vol. 10777, pp. 303-313, https://doi.org/ 10.1007/978-3-319-78024-5_27
  5. A. Sasak-Okoń, M. Tudruj, “Speculative Query Execution in RDBMS Bsed in Analysis of Query Stream Multigraphs,” in 24th IDEAS 2020, Seoul, Korea, pp. 208-218, https://doi.org/10.1145/3410566.3410604
  6. A. Sasak-Okoń, “Modifying Queries Strategy for Graph-Based Speculative Query Execution for RDBMS,” in PPAM 2019, LNCS, Vol. 12043, pp. 408-418, 2020, https://doi.org/10.1007/978-3-030-43229-4_35
  7. J. Silc, T. Ungerer, B. Robic, “Dynamic branch prediction and control speculation,” Int. Journal of High Performance Systems Arch., Vol. 1(1), pp.2-13, 2007, https://doi.org/10.1504/IJHPSA.2007.013287
  8. S. Pan, K. So, J. T. Rahmeh, “Improving the accuracy of dynamic branch prediction using branch correlation,” in Int. Conference on Architectural Support for Programming Languages and Operating Systems, Boston, 1992, pp.76-84, https://doi.org/10.1145/143371.143490
  9. A. Moshovos, S. E. Breach, T. N. Vijaykumar, G. S. Sohi, “ Dynamic Speculation and Synchronization of Data Dependences,” in 24th ISCA, ACM SIGARCH Computer Architecture News, 1997, Vol.25(2), https://doi.org/10.1145/264107.264189
  10. N. Polyzotis, Y.Ioannidis, “Speculative query processing,” CIDR Conference Proceesings, Asilomar, 2003, pp. 1-12,
  11. G. Barish, C.A. Knoblock, “ Speculative Plan Execution for Information Gathering,” Artificial Inteligence, 2008, vol. 172(4-5), pp. 413-453, https://doi.org/10.1016/j.artint.2007.08.002
  12. P.K. Reddy, M. Kitsuregawa, “Speculative locking Protocols to Improve Performance for Distributed Database Systems,” IEEE Transactions on Knowledge and Data Engineering, 2004, Vol.16(2), p.154-169, https://doi.org/10.1109/TKDE.2004.1269595
  13. T. Ragunathan T, R.P. Krishna, “Improving the performance of Readonly Transactions through Asynchronous Speculation,” SpringSim Conference Proceedings, Ottawa, 2008, p.467-474
  14. V. Hristidis, Y. Papakonstantinou, “Algorithms and Applications for answering Ranked Queries using Ranked Views,” VLDB Journal, 2004, Vol.13(1), p.49-70.
  15. X.Ge, B.Yao, M.Guo, et al., “LSShare: an efficient multiple query optimization system in the cloud,” Distrib. Parallel Databases, 2014, Vol.32(4), pp. 593-605, https://doi.org/10.1007/s10619-014-7150-1
  16. M.B.Chaudhari, S.W.Dietrich, “Detecting common subexpressions for multiple query optimization over loosely-coupled heterogeneous data sources,” Distrib. Parallel Databases, 2016, Vol.34, pp.119-143, https://doi.org/10.1007/s10619-014-7166-6
  17. G.Preti, M.Lissandrini, D.Mottin, Y.Velegrakis, “Mining patterns in graphs with multiple weights,” Distributed and Parallel Databases, Special Issue on extending Database Technology, 2019, pp.1-39, https://doi.org/10.1007/s10619-019-07259-w
  18. O.Goonetilleke, D.Koutra, K.Liao, T.Sellis, “On effective and efficient graph edge labeling,” Distributed and Parallel Databases, 2019, Vol.37, pp.5-38, https://doi.org/10.1007/s10619-018-7234-4
  19. H.M. Faisal, M.A. Tariq, Atta-ur-Rahman, A. Alghamdi, N. Alowain, “A Query Matching Approach for Object Relational Databases Over Semantic Cache,” Chapter in Application of Decision Science in Business and Management, 2020, https://doi.org/10.5772/intechopen.90004
  20. M. Ahmad, M. A. Qadir, M. Sanaullah, “Query Processing Over Relational Databases with Semantic Cache: A Survey,” 2008 IEEE International Multitopic Conference, Karachi, 2008, pp. 558-564, https://doi.org/10.1109/INMIC.2008.4777801.
  21. F.Wang, G. Agrawal, “Query Reuse Based Query Planning for Searches over the Deep Web,” Database and Expert Systems Applications. DEXA 2010. LNCS, Vol 6262, 2010, https://doi.org/10.1007/978-3-642-15251-1_5
  22. P. Cybula, K. Subieta, “Query Optimization by Result Caching in the Stack-Based Approach,” Objects and Databases. ICOODB 2010, LNCS, Vol.6348, 2010, https://doi.org/10.1007/978-3-642-16092-9_7
  23. TPC benchmarks, http://www.tpc.org/tpch/default.asp, 2020.