Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

Speculative Query Execution in Relational Databases with Graph Modelling.

DOI: http://dx.doi.org/10.15439/2016F123

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 1383–1387 ()

Full text

Abstract. In computer architecture, speculative execution is the process of executing instructions ahead of their normal schedule[1]. Grama et al.[2] introduce the concept of speculative decomposition as a possibility to execute one or more of possible branches in parallel with computation which are expected to determine the branch choice. The following paper introduces the method of speculative query execution in relational databases. Query queue can be seen as a line of sequential instructions and thus changing their order can result in some errors. Authors introduce a middleware called the Speculative Layer which, based on a specific graph representation, executes some additional Speculative Queries. Results of those Speculative Queries can be used while executing queries from the queue providing a befit which is a shorter response time. The paper describes the process of graph modelling for groups of queries in order to initiate speculative computations, metrics used to evaluate Speculative Queries and experimental results for a test database and a group of input queries.

References

  1. D. Kaeli, P. Yew, “Speculative Execution in High Performance Computer Architectures,” Chapman Hall/CRC, 2005, ISBN:978-1-584-88447-7.
  2. A. Grama, A. Gupta, G. Karypis, V. Kumar, “Introduction to Parallel Computing (Second Edition),” Addison Wesley, 2003, ISBN: 978-0-201-64865-2.
  3. E. A. Jr. Liles, B. Wilner, “Branch prediction mechanism.,” IBM Technical Disclosure Bulletin, 1979, Vol.22(7), p. 3013-3016.
  4. J. E. Smith, “A study of branch prediction strategies.,” ISCA 98 Conference Proceedings, 1998, New York, p.202-215, http://dx.doi.org/10.1145/285930.285980.
  5. D. Padua, “Encyclopedia of Parallel Computing A-D.,” Springer, 2011, ISBN: 978-0-387-09765-7.
  6. A. Kejariwal, X. Tian, W. Li, M. Girkar, S. Kozhukhov, H. Saito, U. Banerjee, A. Nicolau, A.V. Veidenbaum, C.D. Polychronopoulos, “On the performance potential of different types of speculative thread-level parallelism.,” International Conference on Supercomputing Proceedings., 2006, Cairns, p.24, http://dx.doi.org/10.1145/1183401.1183407.
  7. J. Šilc, T. Ungerer,B. Robič, “Dynamic branch prediction and control speculation.,” Int. Journal of High Performance Systems Architecture, 2007, Vol.1(1), p.2-13, http://dx.doi.org/10.1504/IJHPSA.2007.013287.
  8. D. Kaeli, P. Yew, “Speculative Execution in High Performance Computer Architectures.,” Chapman & Hall,CRC, 2005, ISBN:978-1-584-88447-7.
  9. S.T. Pan, K. So, J.T. Rahmeh, “Improving the accuracy of dynamic branch prediction using branch correlation.,” International Conference on Architectural Support for Programming Languages and Operating Systems, 1992, Boston, p.76-84, http://dx.doi.org/10.1145/143371.143490.
  10. N. Polyzotis, Y. Ioannidis, “Speculative query processing,” CIDR Conference Proceedings, Asilomar, 2003, p.1-12, http://dx.doi.org/10.1.1.11.8541.
  11. R. M. Karp, R. E. Miller, S. Winograd, “The Organization of Computations for Uniform Recurrence Equations,” Journal of the ACM, 1967, Vol. 14(3): p. 563-590, http://dx.doi.org/10.1145/321406.321418.
  12. G. Barish, C.A. Knoblock, “Speculative Plan Execution for Information Gathering,” Artificial Intelligence, 2008, Vol. 172(4-5), p. 413-453, http://dx.doi.org/10.1016/j.artint.2007.08.002.
  13. G. Barish, C.A. Knoblock, “Speculative Execution for Information Gathering Plans,” AIPS Conference Proceedings, Toulouse, 2002, p. 184-193, http://dx.doi.org/10.1.1.11.3505.
  14. V. Hristidis, Y. Papakonstantinou, “Algorithms and Applications for answering Ranked Queries using Ranked Views,” The VLDB Journal, 2004, Vol. 13(1), p. 49-70, http://dx.doi.org/10.1007/s00778-003-0099-8.
  15. 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, http://dx.doi.org/10.1109/TKDE.2004.1269595.
  16. T. Ragunathan, R. P. Krishna, “Performance Enhancement of Read-only Transactions Using Speculative Locking Protocol,” IRISS - Sixth Annual Inter Research Institute Student Seminar in Computer Science, Hyderabad, 2007.
  17. T. Ragunathan T, R. P. Krishna, “Improving the performance of Read-only Transactions through Speculation,” Databases in Networked Information System, 2007, Vol.4777, p.467-474, http://dx.doi.org/10.1007/978-3-540-75512-8_15.
  18. A. Sasak-Okoń, M. Brzuszek, Speculative execution plan for multiple query execution systems, Annales UMCS Informatica, 2010, Vol 10(2), p.41-50,
  19. A. Sasak-Okoń, M.Brzuszek, The example of speculative execution for multiple query execution systems, Metody Informatyki Stosowanej, 2011, Vol.3(28), p.157-166, ISSN 1898-5297.
  20. A. Sasak-Okoń, M. Brzuszek, Graph modeling as a support technique for speculative computations in multiple query execution systems, Data Analysis Selected Problems, 2013, p.55-68, ISBN 978-83-7518-602-4.
  21. TPC benchmarks, http://www.tpc.org/tpch/default.asp, 2015.
  22. G. Koutrika, A. Simitsis, Y. Ioannidis, “Conversational Databases: Explaining Structured Queries to Users”, 2009, Technical Report Stanford InfoLab.
  23. G. Koutrika, A. Simitsis, Y. Ioannidis, “Explaining Structured Queries in Natural Language.”, ICDE Conference Proceedings, Long Beach, 2010, p. 333-344, http://dx.doi.org/10.1109/ICDE.2010.5447824.