AAE: An Active Auto-Estimator for Improving Graph Storage

Nowadays, graph becomes an increasingly popular model in many real applications [6]. For example, in FaceBook, the relationships among users are stored as property graph. In machine cognitive learning, the knowledge of experience is stored as knowledge graph [2]. Efficient graph storage is the key step for improving the economic income in these applications by accelerating the workload execution.

Generally speaking, the graph storage tuning tasks mainly rely the database administrators (DBAs) in real applications. However, DBAs complete the tuning by utilizing their experiences and intuition, which may conduct performance degradation. For example, a graph has two properties, age and gender. There exist many queries about gender property. DBAs may establish an index in gender according to the frequency. But the gender property only has two kinds of values in which the index is useless. It is unreliable to tune the graph storage only relying on manual work. Importantly, in real applications, any performance degradation will influence the economic income. So, we need an estimator to help DBAs guarantee the efficiency of the storage tunes.

Unfortunately, existing workload estimators [8] [9] [10] [11] [12] which are mainly designed for the sample data models like relational model, key value model and document model is unsuitable for the graph model. For example, the learned model [12] proposed by R.J et al could only process some sample filters, like ‘range’, ‘in’ and etc. while do not support the traversal filters of graph data. Specifically, due to the complexity of graph workload evaluation, there exists no mature work for this task. In this paper, we pay attention to construct an estimator for evaluating the graph workload to guarantee the tune performance in real applications.

Firstly, we conclude three aspect reasons why evaluating graph workload is difficult as follows:

• 1.

  Complex Structures In order to save various entities and relationships, graph data has very complex structures. For example, there exist more than 1000 million edges in LinkedGeoData. And DBpedia has more than 3000 million triples. Big graph has more complex structural features and statistical features [16]. Evaluating the graph workload in such big graph is very difficult.

• 2.

  Diverse Query Operations To make full use of graph data information, the query patterns in graph are usually diverse including ’create nodes’, ’read nodes’, ’update nodes’, ’delete nodes’ and ’traverse nodes’. And every kind has diverse basic operations [7]. Only the ’read nodes’ contains four basic operations seen in Table 2. Evaluate graph workload under diverse query operations is very difficult.

• 3.

  Dynamic Workloads In real applications, the workload is changing with the user’s requests. The dynamic workloads also bring big challenges to the evaluation method. On the one hand, changing workloads require fast evaluation to guarantee the efficient self-tuning. On the other hand, too many factors in workloads, which have great impact on graph workload execution, need to carefully evaluate. It is necessary for the estimator to quickly complete the evaluation task with high accuracy.

Thus, it is necessary to design a special evaluation model for graph workloads. Inspired by the recent machine learning methods [49] [36] in database committee, we firstly observe how to construct an automatic graph workload estimator to carry the above difficulties. We formulate the graph workload evaluation task into a classification task and explore how to utilize deep learning classifiers to complete this evaluation task. The input consists of the graph workload, the graph data, old-graph storage and new-graph storage. The output presents if the new revision of storage structure is better than the old storage structure.

However, deep learning based models need a large number of labeled data. The result of our preliminary investigation in Table 1 shows that it is incredible to obtain enough labeled data in limited time. We can find that the first item in Table 1 would take 11.57 hours in New4J and LDBC dataset. In order to reduce the cost of data labeling, we combine the active learning structure [17] to our estimator and propose an active auto-estimator (AAE) for graph workload to decrease the demand of training sets. Our experimental results prove that only using a bit labeled data can still make good performance. For example, AAE reach 72% accuracy only with 42% training set. And our estimator could complete the evaluation task with milliseconds.

The contributions of this paper are summarized as follows:

• 1.

  We firstly formulate the definition of graph workload evaluation problem which could help to improve the graph storage and increase the economic efficiency of applications.

• 2.

  We carefully design the features of graph data, graph workload and graph storage, containing the structural features and statistical features of graph data, various graph query pattern features, basic storage schema and indexes features.

• 3.

  We design a graph workload estimator, AAE which combines the deep learning and active learning. Our model could process the complex features, including data features, workload features and graph storage features. And AAE could quickly complete the graph workload evaluation with the limited training set.

• 4.

  We examine our active estimator with two widely used dataset, LDBC and Freebase in microbenchmark [43]. The experimental result shows that AAE could largely reduce the demand of training dataset. And our estimator could complete evaluation with milliseconds.

The structure of this paper is as follows. Section 2 presents some related works about graph storage and graph query acceleration. Section 3 introduces the overview of AAE. Section 4 discuss the feature engineering of three key components of AAE, including graph data, graph workload and graph storage. And Section 5 carefully introduce the active auto-estimator. Finally, we clarify the experimental result in section 6, containing experimental dataset and result analysis.

Because of the lacks of the graph workload evaluation methods, we only introduce some related works about graph storage and graph workload acceleration.

Graph Storage The storage of graph data is divided into native graph database storage [23] and non-native graph database storage [24, 25]. The native graph database implements point-to-point data structure and indexing; the non-native graph database uses other database systems to store graph data and implement query interfaces. Native graph database systems such as Neo4j, InfiniteGraph, Sparksee [21]. Non-native graph database systems such as OrientDB, ArangoDB and various relational databases. Compared with native storage, non-native storage systems [26, 27] have more mature support in terms of concurrency [22], locks, security, and query optimization.

Graph workload Acceleration Recently, researchers mainly optimal the graph query by two key aspects. One is to construct indexes. Compared to other data models, graph data has more complex data structure and diverse query operations. For quickly scan the complex graph, researches index the subgraph [14], path [15] and etc. Different from the sample data model, using the general indexes (like B+ tree, Hash, LSM tree) do not quickly find some complex patterns [30]. Expect the index there also exists some other methods to accelerate graph query. People propose some cache and prefetching methods [18] [31] [32] [33] [34] based on similarity counting. And recent works [33] prefetch graph query by computing the graph edit distance between queries. Totally, the graph database management urgently need the evaluation modules to accelerate the graph query.

Traditional estimators could be divided into two main class, single query based [12] and workload based [37]. Considering the demand of real-world settings like FaceBook which could receive millions of queries at one time, we take the total graph workload as the evaluation target. There are two significant influential factors to graph workload performance, graph data and graph storage. In this paper, we formulate these key components of our estimator as follows:

Graph Data: $\mathcal{G}$ $=(N,R,P,T)$, where $N$ is the collection of nodes, $R$ is the collection of edges, $P$ is the collection of properties, and $T$ is the property edges.

Graph Workload: $\mathcal{W}$ $=\{q_{1},q_{2},...q_{n}\}$, where $q_{i}$ is a graph query.

Graph Storage: $\mathcal{S}$ $=<S_{S},S_{I}>$,where $S_{S}$ is the basic storage schema and the $S_{I}$ is the indexes in $S_{S}$.

The total cost of graph workload is denoted as follows. $w_{i}$ is the weight of $q_{i}$ and $c_{i}$ is the cost of $q_{i}$.

Comparing the workload execution cost of two graph storage plans could help DBAs to stably tune the graph storage. In order to improve graph storage, we formulate the graph workload evaluation task as a classification task.

Definition(the graph workload evaluation task): Give the graph data $G$ and workload $W$, We define the cost a graph workload evaluation task as follows:

The input of AAE consists of the graph workload, the graph data, the old graph storage and the new graph storage. The output presents if the new graph storage is better than the old one in the current graph data and graph workload. Our AAE could help DBAs to improve the graph storage by quickly evaluating graph workloads.

As figure 1 shows, after receiving the graph storage tune from DBAs, our system implements the evaluation to judge if the tune is positive. If so, this tune from DBAs could be implemented to database. Our estimator could help DBAs to prevent the performance degradation.

Feature engineering is the key step of constructing the graph workload estimator. Comparing with the evaluation for other sample data models (like relation, key-value), the graph evaluation has more complex characteristics, such as the complex graph structure, diverse query operations and dynamic workloads. In this section, we introduce the feature engineering of constructing graph workload estimator, including the graph data, the graph workload and the graph storage.

Dataset Feature Extraction: Generally Speaking, the characteristics of graph data mainly include statistical characteristics and structural characteristics. In this paper, we pay more attention to these two kinds of features for the representation of graph data. Considering the scale and complexity of the graph data, we conclude that some vital statistical features, including data size, number of nodes, number of edges. And some key structural features include the number of nodes or edges’ type, the number of properties and the property values of node or edge. Our estimator which use both statistical features and structural features has more complete representation for graph dataset.

Workload Feature Extraction: Graph has various basic query operations. We carefully divide these operations into five types as listed in Table 2, containing create, read, update, delete and traverse. We can find that different from other sample data models (like relation, key-value), graph has more plentiful operations. We conclude these operations by totally analyzing the graph query and existing works [18, 7]. And the rate of these operations in workload has vital influence for graph workload evaluation. For example, in native graph storage, traversal graph queries usually have higher efficiency than read queries. While in relational graph storage, read queries usually have higher efficiency than traversal queries [6]. By extracting the characteristics of the workload, we can identify the main types of operations, and improve the accuracy of our estimator. Through these workload information, we can have a more detailed judgement of the graph storage. Finally, we utilize the rate of each basic query operation and the frequency of properties as the representation of the graph workloads.

Storage Solution Features: In order to query graph data quickly, there are some different kinds of graph store engines, including New4J, Titan, ArangoDB and etc. Also, there are more other features in corresponding engines, such as index support, query optimizer and other feature of distribution design. In this paper, we choose the basic stores and indexes as the total represented features for graph storage solution. Because of the basic stores and indexes information are not numeral features, we utilize the one-hot method [39] to encode them. And one-hot method could largely retain the original characteristics. Specifically, we encode every kind of engines as a one-hot vector. For index information, we consider the indexes on graph node properties and edge properties. We also utilize the one-hot vector to identify if a property has the index.

It is difficult to obtaining a large mount of training set in graph workload evaluation task with limited time. We propose an active-based solution to reduce the time consumption of training model. In this section, we introduce the active auto-estimator module.

In this section, we express our examination results of our model. First, we introduce the experimental settings in section 6.1, containing dataset and execution environment. Then, we discuss our experimental results from three aspects, active performance in section 6.2, classifier comparison in section 6.3 and evaluation time cost in section 6.4. The source codes of our experiments are available ¹¹1https://github.com/yangmanST/Graph-Storage/tree/master.

In this paper, we design an active auto-estimator for improving the graph storage solution. We carefully design the feature engineering, including graph data features, graph workload features and graph storage solution. And we clarify the time efficiency and evaluation accuracy in two open source datasets. In the future, we expect to make more improvements in the following two aspects. On the one hand, we want to figure out if the more fine-grained features (such as the graph itself) would performs well than the processed statistical features (such as the number of nodes). After all, it would loss some information after some processing in original dataset. On the other hand, we would consider to research if the new researches about auto-ML would inspire the graph workload evaluation for obtaining a perfect deep classifier.