Although DBMS (Database Management Systems) are often hidden for a user, they are a part of many applications utilized in day-by-day life. In general, we can suppose two main types of DBMS: OLTP (On-Line Transaction Processing) and OLAP (On-Line Analytical Processing). We can also distinguish another classi cation related to the connection of a client and DBMS: client-server and embedded DBMS. The embedded DBMS enable to achieve the maximum performance since an often slow network connection is not used. As a result, they are utilized by in-memory computations where the maximum throughput is required. Although it seems that a lot of high quality DBMS exist and another DBMS are not required, there is not a system to meet all demands of the real world. In this paper, we introduce our prototype of embedded database system called QuickDB. We show that it includes a wide variety of data structures and it provides more e cient performance in many cases compared to up-to-date (embedded) DBMS.
Firebird [
Although it seems that a lot of high quality DBMS exist and another DBMS
are not required, there is not a system to meet all demands of the real world.
For example, Berkeley DB provides the high performance of the B-tree and the
paged queue, but it does not support any multidimensional data structure. On
the other hand, in the case of libraries including an R-tree implementation (see
Table 1), they support especially in-memory implementations, which penalizes
them in the case of huge data. Moreover, they do not often support any other
data structures. In this paper, we introduce a long-time project of the Database
Research Group3, a prototype DBMS called QuickDB [
This paper is organized as follows. In Section 2, we describe an architecture of QuickDB. In Section 3, we put forward a comparison of QuickDB with other DBMS. In the last section, the paper content is resumed and the possibility of a future work is outlined. 2
In Figure 2, we see an architecture of QuickDB4. The cache bu er preserves pages of data structures to prevent disk accesses when a page is required. The overhead of the page size compared to the size on a disk is approximately 20%, i.e. the in-memory page size is 9,830B in the case of the 8kB page size. When a data structure operation returns a result, e.g. the range query, the result is stored in a ResultSet and returned to a user. After the user closes the ResultSet, it is returned to QuickDB.
There exists an implementation of the B-tree, R-tree, and paged queue utilizing the core of QuickDB. The goal of QuickDB is to provide the maximum performance instead of an implementation of rich functionalities like a support of methods stored in a database and so on. 4 QuickDB is implemented in C++.
Testing Environment We perform a set of various tests where we compare our QuickDB with state-ofthe-art implementations in each area. By the term area we mean a data structure type. Moreover, in Section 3.4, we show results of an application of QuickDB { a native XML database.
All experiments are executed in a single thread on an Intel Xeon 2.9 GHz CPU. We use a real data set of meteorological measurements of the Czech Hydrometeorological Institute5, where the dimension of each record is 5. The collection contains 57,852,305 records and the total size of its textual representation is 1.12 GB. Queries used during the tests are randomly generated. 3.2
Comparison of Basic Data Structures
In this test, we compare the performance of two QuickDB basic data structures:
the B-tree and the heap table (paged queue). The B-tree is a traditional data
structure used by all relational DBMS [
B-tree We compare the QuickDB's B-tree performance of the insert and point query operations with the Berkeley DB and SQLite here. The performance of the insert operation can be in uenced by several di erent aspects where we consider the following: (1) whether the data t into the main memory cache or not, and (2) whether the data are sorted before the insert or not. All combinations for each B-tree are tested and the results are summarized in Table 2.
We can observe that SQLite performs worst in all cases. An overhead of SQLite is probably induced by the SQL interface and lack of its own bu er cache. Clearly, QuickDB and Berkeley DB have very similar performance on our data set, however, QuickDB slightly outperforms Berkeley DB in all tests. The only disadvantage of QuickDB is its a slightly bigger index.
Heap Table (Paged Queue) Now we compare the performance of the QuickDB's heap table with the Berkeley DB's queue. We use the Berkeley DB's queue since it supports the insert and sequential scan operations. The insert operation is preformed with limited memory, however, it is not very important here since only a sequential write is utilized. Then we perform the sequential scan with both cold and warm caches. The term warm cache means that all the data are already stored in the main memory.
Results are shown in Table 3. QuickDB is twice faster during the insert than Berkeley DB. Surprisingly, the performance of the Berkeley DB queue scan is 5 http://www.chmi.cz/
Sorted insertion 80% of data [thousands per second] t in the main Random insertion memory [thousands per second]
Sorted insertion All data [thousands per second] t in the main Random insertion memory [thousands per second] Queries [s] Index size [GB] 531 289 674 357
the same no matter whether the cache is cold or not. It leads us to a conclusion that Berkeley DB uses the OS le system cache which in uences the results. However, QuickDB signi cantly outperforms Berkeley DB during in-memory sequential scan. On the other hand, the size of the Berkeley DB index le is quarter of the data set size, whereas, the QuickDB index le is equal to the data size.
Inserting [thousands
per second]
Sequential scan (warm) [s]
Sequential scan (cold) [s]
Index size [GB]
2,244
In this section, we compare a performance a multidimensional data structure
called the R-tree [
The performance of inserting and query processing is compared with several
libraries, namely Boost [
Since all tested libraries (except QuickDB and libSpatialIndex) support only
an in-memory storage, no secondary storage has been used during the
experiments and we do not measure the size of the indices. The page size is 8kB
in all cases. In Table 5, we see that QuickDB and Boost provide the highest
performance. While Boost is more e cient in the case of the insert operation,
QuickDB slightly outperforms it in the case of query processing. We see that
other implementations are outperformed by QuickDB and Boost.
In this section, we present an application of the QuickDB framework. It is a
native XML database called QuickXDB introduced in [
Data structures There are two indexes representing an XML data collection,
namely document index and partition index [
The B-tree of the document index has a node label as a key. There are two fundamental purposes of the node label: (1) it uniquely identi es each XML data node and (2) we are able to resolve a structural relationship of two nodes, e.g., one is a parent of another. The leaf nodes of the B-tree contain tags (node names) of XML nodes and pointers into the paged queue where text values are stored. The records for XML nodes in the leaf nodes of the B-tree are stored in the same order as in the original XML document or collection. Consequently, we can pro t from using range queries to obtain the whole subtree of an XML node.
The partition index is the secondary access path. It is also a combination of the B-tree and the paged queue. However, here a tag name serves as a key and items of the B-tree leaf nodes include pointers to paged queues where corresponding node labels are stored in the document order.
Experimental evaluation We have performed a time comparison with 2 other native XML databases: MonetDB7 and BaseX8. We have picked up 4 data collections: XMark9 with factor f = 10 (1.1 GB), Swissprot (109 MB), TreeBank (82 MB), and DBLP (127 MB)10.
For each collection, we have generated 3 sets of 50 distinct random XPath queries oriented purely on searching structural relationships between XML nodes. The sets di er in the upper range of their selectivity 11: (1) selectivity up to 100%, (2) selectivity up to 10%, and (3) selectivity up to 1%. Di erent query selectivity can cause a di erent utilization of indexes. The complexity of queries vary for a di erent number of location steps (from 2 to 11) and also for a di erent number of branching predicates (from 0 to 4). Both ancestor-descendant and parent-child tree axes are randomly used. Branching predicates contain either single XPath subqueries or more subqueries connected by a logical conjunction.
Summarized results are presented in Figure 2. The values on the vertical axis stand for the total processing time of a set of queries. Each single query was evaluated 5 times, only arithmetic means of 3 times (without the best and the worst case) are considered.
We can see that our QuickXDB outperforms BaseX on all query sets except XMark with selectivity up to 1% and 10%. We also evaluate queries with the higher selectivity (up to 1% and 10%) on DBLP, Swissprot, and TreeBank collections faster than MonetDB. On the Swissprot query set with selectivity up to 1%, QuickXDB is more than 20 faster than BaseX and 8 faster than MonetDB. On the other hand, our QuickXDB is approximately 2:5 slower than MonetDB on DBLP and XMark query sets with selectivity up to 100% and 3:3 slower than BaseX on XMark with selectivity up to 10%. 7 http://www.monetdb.org/XQuery/ 8 http://www.basex.org 9 http://www.xml-benchmark.org/ 10 http://www.cs.washington.edu/research/xmldatasets/www/repository.html 11 If we for example have a query //a[./b]//c, selectivity can be computed as count(//a[./b]//c) div count(//c) [s] 30 25 20 15 10 5 0
P L B D ) % 0 0 1 (
P L B D ) % 0 1 (
P L B D ) % 1 ( t o r p s s i w S ) % 0 0 1 ( t o r p s s i w S ) % 0 1 ( t o r p s s i w S ) % 1 ( k n a B e e r T ) % 0 0 1 ( k n a B e e r T ) % 0 1 ( k n a B e e r T ) % 1 ( k r a M X ) % 0 0 1 ( k r a M X ) % 0 1 ( In this paper, we introduced a comparison of our prototype of embedded database system called QuickDB with other up-to-date embedded DBMS and libraries. As mentioned, the main goal of QuickDB is to provide the maximum performance. The results show that QuickDB outperforms these DBMS and libraries in a lot of cases. In our future work, we want to compare other features of DBMS, for example, scalability performance, transaction processing performance and so on.