When accessing data from a database, a database management system has to accomplish many tasks. Checking the conformity of the query, generating a reasonably good query plan and executing it in a concurrent system are just a few of them. During query execution, there are some points at which the main execution thread must stop and wait for data. This synchronous waiting can have a major impact on the overall query performance. In this paper we introduce the idea of a ticket-based fetch, which supports the database management system by waiting for data asynchronously. This can improve the query-execution performance in database systems.
Large database systems (DBS) depend heavily on fast access to huge volumes of data, which can easily exceed the capacity of a server's random-access memory (RAM) by orders of magnitude.
These data can be stored in three di erent storage spaces, the primary, secondary and archive storage space [9]. They all have di erent properties that allow them to be used for di erent tasks. Primary storage uses RAM, while solid-state and hard-disk drives are found in secondary storage, which is orders of magnitude slower. If the data a query is to be executed on is stored in the secondary storage space, they must be transferred to the much faster primary storage space to perform operations on them. It is therefore crucial that algorithms of the DBS depend as little as possible on data in slower storage spaces and try to rely only on data that has already been loaded into primary storage. However, if data are not in main memory, they still must be fetched from disk, which can cause long latencies and slows down the execution of queries.
G. Graefe [
These ideas about parallelism focus more or less on data already accessible in primary storage, or on nding data in the storage spaces, ignoring the fact that the transfer of these data to primary storage adds latency to the execution of each single query. The question is whether we can support these parallelism ideas even better by providing an asynchronous data ow inside a DBS.
This can be useful in a query that connects many tuples from di erent tables to create one large result tuple, as it is done in star-shaped queries (e. g. Listing 1.1). A star-shaped query is similar to a star query, which uses a main table (fact table) that contains information about how to connect the other tables (dimension tables). The only di erence is that star queries are bound to datawarehouse systems and use information from the dimension tables mostly for reducing the result-set size1. With a limited number of values in the dimension tables, star queries can be optimized by using bitmap indices, while star-shaped queries cannot use this kind of optimization and are thus much harder to optimize.
In this paper we present some rst steps of the idea of a ticket-based data loading from secondary storage. We do this by introducing a ticket system for database operators. It desynchronizes data and execution ow of query processing.
We begin our journey with a simple example. We describe the problem (Section 2), nd a rst solution (Section 2.1), explain that solution in depth (Section 2.2), and try to expand that solution, so it can be executed in a more general work ow of query execution (Section 2.3). After that we discuss related work (Section 3), draw a conclusion, and present future work (Section 4). 2
To work with the data, a classical DBS must transfer it from secondary or archival storage to primary storage. This process is shown in Figure 1a for a star-shaped query. Because the data-tranfer rate of secondary storage is limited, access to the data takes some time, so any query execution in need of these data must interrupt its execution ow and wait some time for the data to arrive.
This pause can become large depending on the exact location on disk and the access path for it, and the query execution must wait, even if the data is 1 http://www.orafaq.com/tuningguide/star%20query.html not needed immediately. To improve the search, indices have been introduced, which can help to nd the required data faster on secondary storage. Once the data is collected, query execution proceeds to the next step, which may require some more data. These steps must be repeated for each tuple-fetch operation, until the result set is complete and can be returned to the caller. So waiting for data can take a large portion of the execution time of a single query.
To reduce this data latency, we present an initial idea of ticket-based data access, describe it in depth, and expand it towards a more general query execution. 2.1
A
rst step
To make the idea understandable, we simplify the problem a bit. We ignore some
ideas on parallelism presented in [
With our idea we want to intervene exactly where the query execution must wait for data and try to improve the execution time with asynchronous data access. As shown in Figure 1c, our rst step towards asynchronous data access focuses on an index scan (a scan operator using an index) combined with a special Data Access Manager, our abstraction for access to secondary storage and moving data to primary storage.
Traditionally, an index scan performs three steps in accessing the data from secondary storage. First it uses a secondary index and checks whether and where the corresponding tuple can be found. Because of our assumption, this is done in main memory and thus very quickly. So the location of the tuple on secondary storage is known. In the second step, this tuple is loaded to primary storage, where the third step continues and returns the tuple to the calling operator. In our example, this is a join operator.
If we now rework this index-scan operator to use the Data Access Manager, we obtain two operators. We get a \check for existence, get the storage-space address and start loading" (9) and a \wait for loading and combine the loaded tuple with the existing tuple" (m) operator, as seen in Figure 1b. We describe these operators and the Data Access Manager in detail in Section 2.2. You can easily see that the second step has been delegated to the Data Access Manager.
Now that we have refactored our index scan into two operators, we move them in our query-execution tree to optimize it, as shown in Figure 1c. The 9 operator remains in the same place where the scan was, while the m operator is moved to where the data is actually needed. In our example, this is the end of query execution just before returning the result tuple, where we insert the \wait and combine all data" operator. Because the data from R1 are needed right now, we can use the old scan operator for simplicity.
SELECT ∗ FROM R1 , R2 , R3 , R4 , R5 WHERE R1 . i d = 42 AND R1 . 2 i d = R2 . i d AND R1 . 3 i d = R3 . i d AND R1 . 4 i d = R4 . i d AND R1 . 5 i d = R5 . i d ; Listing 1.1: Exemplary SQL for a star-shaped query ./R1:5 id=R5:id ./R1:4 id=R4:id ScanR5 ./R1:3 id=R3:id ScanR4 ./R1:2 id=R2:id ScanR3 R1:id=42 ScanR2 ScanR1 (a) Traditional access approach e g a r o t S y r a d n o c e S ./R1:4 id=R4:id ./R1:3 id=R3:id ./R1:5 id=R5:id mR3 9R3 mR4 9R4 mR5 9R5 ./R1:2 id=R2:id R1:id=42 mR1 9R1 mR2 9R2
mall ./R1:5 id=R5:id ./R1:4 id=R4:id 9R5 ./R1:3 id=R3:id 9R4 ./R1:2 id=R2:id 9R3 R1:id=42
9R2
ScanR1 (b) Traditional access approach with our newly designed operators and the Data Access Manager r e g a n a M s s e c c A a t a D r e g a n a M s s e c c A a t a D e g a r o t S y r a d n o c e S e g a r o t S y r a d n o c e S (c) The complete ticket-based system approach
We can now easily see that the main execution path just informs the Data Access Manager which tuples need to be moved from secondary storage to primary storage for easy access. This has several advantages, as described in the details (Section 2.2).
We expect that this change in strategy can already improve the execution time of quite small star-shaped queries in huge DBS, and we hope to show in the future that this also holds for other query types. 2.2
Here we explain in more detail our thoughts on the two operators and the Data Access Manager mentioned above.
The 9 operator is designed to be called with a table and an expression (e. g. simple search argument). It queries a secondary index structure for the position of the tuple in secondary storage space. With this address and a certain priority, it calls the Data Access Manager and receives a ticket (e. g. a pointer or \future object"2) with information later allowing access to the fetched tuple. This ticket is then forwarded to the next operator. Now the data ow is separated from the execution ow and the current tuple is much smaller, since data not currently needed are not yet part of the tuple. This may have the additional advantage of being able to store the tuple closer to the CPU.
The ticket is now part of the tuple and is resolved by the m operator when the data are needed. The m operator looks at the ticket and determines whether the data is already stored in primary storage. If this is not the case, it recalls the Data Access Manager with the ticket, requests a higher priority and waits for the data to be delivered. This results in a delay that should not be greater than the normal access delay in a synchronous call. Hopefully the data can already be found and can be accessed directly without any delay. Now the data can be combined with the tuple and can be presented to the next operator. If the m operator needs to get the data from multiple tickets at the same time, it can prioritize the already loaded data and can give the Data Access Manager more time for completing the other tickets.
The Data Access Manager has a list of all tuples that must be moved to primary storage and can therefore improve throughput by taking advantage of the secondary storage device's properties, reorganizing the tuples' access order accordingly3. If a tuple is needed right now, the access order can be rescheduled to make that data accessible sooner. 2.3
The rst step exploits some simpli cations, like reducing the parallelism and keeping the secondary indices in primary storage. We see no problem in bringing 2 https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Future.
html 3 http://www.cs.iit.edu/~cs561/cs450/disksched/disksched.html the two other parallelism ideas back. The secondary indices in primary storage gives us the advantage of knowing how many tuples to expect without needing to access the secondary storage. Additionally we have dropped the idea of batch execution, where at the same time multiple tuples are given to an operator as input.
We now like to expand the idea to overcome these simpli cations.
For querying a secondary index that is not in primary storage, we move the querying of the secondary index into the Data Access Manager. The 9 operator then does not give an address to the Data Access Manager, but just the table and the expression. By limiting the information, we force the Data Access Manager to do a normal index scan, where the index might not be stored in primary storage. This way we cannot predict how many tuples are going to be returned. Based on our ticket system, the Data Access Manager now creates a data structure that stores from zero to multiple tuples in it. The m operator reacts to this by either dropping the given tuple (it has no join partner), or by iterating through the data structure and creating a combination with each of the retrieved tuples, resulting in multiple tuples for the next operator. Depending on the query and the expected drop rate, the query optimization may place the m operator closer to or farther away from the 9 operator to balance between reduced unnecessary workload and increased parallel execution.
With this change, we can use arbitrary scan operators with the Data Access Manager, and may also be able to include basic operations such as a projection or selection to increase the amount of parallel execution and to reduce the amount of space on primary storage needed to store the tuples.
To handle batch execution, we expect the 9 operator to open a ticket for each of the tuples in the batch. No further adjustments are needed, because the remainder of the execution can be kept as if there was only one tuple, only that we now have to do this for each tuple of the batch. The m operator has another small advantage in being able to check tickets from multiple tuples at once, rather than waiting for the data of a particular tuple to be accessible right now.
With these steps we expect to be able to handle arbitrary queries in current DBS. 3
We found the idea of increasing the speed of slower devices already in the work of Sarawagi [12], where the optimization of access to tertiary memory (archival storage) is discussed. Here the author suggest using a scheduler to rst bring all needed data in the secondary storage space and then start executing the query on it. Even if you do not consider that we are talking about secondary to primary storage data transfer and not archival to secondary, we still di er in the idea, because we try to make data accessible while running the query and not to load the data into a faster storage space before executing the query, which may not need all the data.
Codd described a restriction in [
For asynchronous data access there are some implementation concepts like asynchronous I/O4 or future objects5. These are some basic techniques for adding asynchronism to software systems and we plan to use them for implementing the Data Access Manager.
The idea of splitting an operator into smaller bits and looking at these bits
was recently proposed by Dittrich and Nix [
Gurumurthy et al. [7] gave an overview of constructing operators from smaller
parts and adapting more easily to new specialized hardware like GPUs [8] and
FPGAs [
There have been some ideas for operators that can take advantage of better
disk-scheduling algorithms, e. g. [
We found the idea of optimizing star queries inside the Oracle Documentation [11], but this is very speci c for star queries in data warehouses. The data from the dimension tables is only used for comparison with constraints and is dropped afterwards. This way they use bitmap indices for the dimension tables to say whether a tuple ts the constraint, which can increase the speed of star queries in data warehouses. We just use star-shaped queries as an easy example and must return the data from the \dimension" tables.
In HyPer [10] a data-aware computing method was introduced by switching the execution direction inside of a pipe from pulling to pushing. By doing this, the data can be kept in CPU registers and need not be stored and loaded from slower storage areas. We do not focus on keeping the data close to the CPU, but instead try to minimize the waiting time when loading the data into a faster storage space. We think it might be possible to combine these two ideas. 4 https://man7.org/linux/man-pages/man7/aio.7.html 5 https://en.cppreference.com/w/cpp/thread/future
In this paper we present our idea of desynchronizing the data and execution ow in query processing. We do this by introducing a Data Access Manager and by splitting scan operators into new operators focused on data access. This way we are able to place them independently in the query-operator tree. We expect to reduce the latency for data access in a DBS and the overall query-execution time.
We are fully aware that this idea increases the search space of query optimization even more, but we rather see this as a challenge for research than a problem.
As future work we plan to implement and test our idea. Because we expect the rework of the software to be quite large, we have decided to use a lightweight, relatively simple, and open-source database management system, namely Apache Derby6.
We plan to do this by dividing the task into subtasks, which are: the implementation and evaluation of the Data Access Manager with the ticket system, the splitting of the scan operator, and an additional optimizer step for the physical execution plan that replaces the standard operators with our operators and moves them to t our idea. Afterwards, we would like to extend the implementation with ideas from our next steps (Section 2.3). For evaluation we plan to run some queries from the TCP-H benchmark on datasets magnitudes larger than the RAM of the speci c machine. Furthermore, we think about adding the idea to distributed or federated DBS, to reduce the data-access latency of an access to a remote system. 6 https://db.apache.org/derby/ 7. Gurumurthy, B., Broneske, D., Drewes, T., Pionteck, T., Saake, G.: Cooking dbms operations using granular primitives. Datenbank-Spektrum 18(3), 183{193 (Nov 2018). https://doi.org/10.1007/s13222-018-0295-8 8. He, B., Lu, M., Yang, K., Fang, R., Govindaraju, N.K., Luo, Q., Sander, P.V.: Relational query coprocessing on graphics processors. ACM Trans. Database Syst. 34(4) (Dec 2009). https://doi.org/10.1145/1620585.1620588 9. Kemper, A., Eickler, A.: Speichermedien. In: Datenbanksysteme, pp. 211{212. Oldenbourg Wissenschaftsverlag GmbH (2013), 9th edition 10. Neumann, T.: E ciently compiling e cient query plans for modern hardware. Proc. VLDB Endow. 4(9), 539{550 (Jun 2011). https://doi.org/10.14778/2002938.2002940 11. Rich, B.: Oracle database reference, 12c release 1 (12.1) e17615-20 (2017), https: //docs.oracle.com/database/121/DWHSG/schemas.htm#DWHSG9069 12. Sarawagi, S.: Database systems for e cient access to tertiary memory. In: Proceedings of IEEE 14th Symposium on Mass Storage Systems. pp. 120{126 (1995). https://doi.org/10.1109/MASS.1995.528222