Speculative support for query execution in Relational Database Management Systems (RDBMSs) based on a graph-analytic approach is the subject of this paper. Optimized speculative queries are defined by analyzing graph representations of a stream of input queries arriving to a RDBMS. The analysis is permanently performed based on a Speculation Window moving on the RDBMS input query queue. The proposed optimization concerns both the definition of the speculative queries to be executed and the methods of speculative query results assignment to incoming input queries. The paper shows how to design RDBMS query execution speculative support using two kinds of the query graph representations: the query multigraphs and the query hypergraphs. In particular, the paper proposes an improvement of the use of the speculative query results defined based on the Speculative Window query multigraph analysis by an additional assignment of speculative results to queries in the input query queue which follow the Speculative Window. The additional assignment is based on the analysis of the speculative and user input queries represented jointly in a common hypergraph. Two approaches to the proposed speculative results improvement are discussed which increase the speculative result life time. The properties of the speculative query execution support based on the mentioned query graph representations and algorithmic approaches have been assessed by the experiments with the simulated execution of the query testbed sets based on the popular TPC-H benchmark.

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 was 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.

The paper presents an insight into a speculative execution model of queries in RDBMS based on the analysis of the stream of current queries appearing at the database input. A specific multigraph representation of input query stream is created and used to determine the speculative queries for execution. A group of worker threads execute the chosen speculative queries in parallel with the execution of the standard input stream of user queries. The obtained speculative results are then used to support faster query execution. First, the paper briefly reminds the assumed graph modelling and analysis methods. Then, additional rules are presented which enable combining results of multiple speculative queries in execution of a single user input query. The quality of executed and used speculations is then analysed based on the defined quality metrics and structural details of speculative queries. Conclusions from this analysis are used to modify the selection method of target queries for speculative execution. It aims at intensification of the use of multiple speculative query results and further reduction of the user query execution time. Experimental results are presented in a multi-threaded speculative experimental environment cooperating with a SQLite database. They show that with the improved algorithm we can obtain more varied speculative query results, and thus, more intensive use of multiple speculative query results by the stream of user queries sent to the database.

The paper is concerned with the methodology for speculative query execution support in distributed Relational Database Management Systems (RDBMS). The proposed approach is based on the analysis of the multigraph representations of the stream of input queries arriving to a RDBMS. As a result, the optimized set of speculative queries is found to support execution of current queries. The speculative query results are used to speed-up execution of the query input stream. The paper presents how the proposed speculative query execution approach can be implemented inside a novel distributed program design framework PEGASUS DA in which program execution decisions are taken based on the system-supported monitoring of the distributed application global states. The paper shows the architecture of the speculative support provided by such framework for the distributed RDBMS and the assumed speculation approach. The implementation issues of the multithreaded distributed support based on the RDBMS SQLite engines are discussed. Distributed data synchronization and speculative query execution strategy as well as speculation results distribution are discussed. The proposed approach to distributed implementation of the speculative support to RDBMSs using the PEGASUS DA framework is illustrated on the example of the modifying query handling in a RDBMS facing the presented speculative query support for query execution.

The paper presents a method for parallel speculative query execution support to be applied in relational database systems. The method is based on dynamic analysis of input query stream in databases serviced in SQLite. A special representation of queries in the form of multigraphs is employed. A middleware called the Speculative Layer is introduced which determines the most promising speculative queries for execution based on analysis of current stream of user queries. The proposed approach assumes a dynamic query speculation window organized in the query queue, which is converted into a query multigraph subdue to the analysis. The paper presents the query graph modelling method and the query graph analysis algorithms based on specific metrics. They aim in finding best candidate queries for speculative execution which fit currently accumulated query window. Experimental results are presented based on the proposed algorithms assessment using a real testbed database serviced in SQLite.

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.Author 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.

This paper concerns speculative parallelization as a method of improving computations efficiency and also as a method of reducing the problem solving time with reference to its sequential version. Speculative parallelization is proposed for a particular class of problems, described as recursive functions taking values from finite sets. It refers to speculative execution of consecutive iteration steps. Each of them, except the first one, depends on the preceding iteration step yet before it ends. Assuming that in the sequential version one iteration is performed in one linear execution time step (hereinafter referred to as computational step), then the aim of the speculative parallelization is the reduction of the total number of computational steps and thus execution of more than one iteration in one time step. The essence of the problem is that we assume some mapping schemes of arguments into the set of possible values of the function in speculative computing, i.e. there exists precise information about the possible values that the function can take for particular arguments. This paper presents simulation results for the chosen mapping schemes, illustrating how the number of steps, required to compute the value of the function for the given argument, depends on the structure of the mapping scheme and on the number of used parallel threads.