Making big data small

1. Introduction

Big data analytics appeals for a departure from the classical computational complexity theory and conventional query evaluation paradigm. Textbooks tell us that a computational problem is tractable if its cost can be expressed as a polynomial in the size n of the input [1]. When it comes to big data, however, it may no longer be the case. As an example, let us consider queries on relational datasets, i.e. tables of records (a.k.a. tuples). It was reported that it took days to join two tables of 100 million tuples each [2]. While join is a routine operation in relational queries and its cost is in O(n²) time on tables of n tuples, it can no longer be considered ‘tractable’ if it takes days on big relations. That is, computational problems that are labelled tractable in the classical complexity theory may become infeasible or ‘intractable’ in the context of big data [3].

The industrial solution to big data analytics is typically by parallel computation with a cluster of machines. When data grows big, it scales out the cluster by adding more machines. The solution assumes the parallel scalability, i.e. the computation would get faster when given more machines. However, few parallel algorithms in the literature offer this performance guarantee. Worse still, some computational problems are not parallel scalable, i.e. there exist no algorithms for these problems that guarantee to substantially reduce running time by adding more machines; for instance, no parallel algorithm for graph simulation, an O(n²) problem for social network analyses, is able to further reduce running time by adding more processors, after the number of processors used reaches a point [4] (see [5] for more real-life examples). Furthermore, even when dealing with computational problems that are parallel scalable, small businesses typically have limited resources and cannot afford large-scale parallel computation.

Is big data analytics beyond the reach of small companies with limited resources?

We tackle this question by presenting an alternative solution, as an effort to provide small companies with a capacity of big data analytics under constrained resources. We focus on relational query answering, since relational data accounts for 75% of business data in the real world [6], relational databases dominate big data [7], and analytics of the data is typically carried out with queries expressed in SQL (structured query language, the standard query language for relational databases). Given an SQL query Q and a relational dataset D, our job is to compute the answer to Q in D, denoted by Q(D), which is a set of tuples. The query answering problem is non-trivial. It is NP-complete (intractable) to decide whether a given tuple is in the answer Q(D) when Q is in SPC, a special case of SQL defined with selection, projection and Cartesian product (join) operators only.

The idea is to make big data small, based on the following observation. Given a query Q posed on a dataset D, in practice it often suffices to compute Q(D) by accessing a small fraction D_Q of D, even when D is big. In the light of this, we propose (a) bounded evaluation [8–12]. Given a query Q, it identifies D_Q such that Q(D_Q) = Q(D) and computes the exact answer to Q in D by accessing small data D_Q; moreover, it fetches D_Q of a bounded size when possible. When exact answers are beyond reach of a bounded fraction of D, we propose (b) a data-driven approximation scheme [13]. Also identifying and fetching a small fraction D_Q of D, it computes Q(D_Q) as approximate answer to Q in D and offers a deterministic accuracy bound. Both (a) and (b) are carried out under available limited resources and reduce queries on big data to computations on small data.

As proof of concept, we have developed a prototype system BEAS (Boundedly EvAlable SQL) [14], which implements the new query evaluation paradigm to answer SQL queries under constrained resources. Our industry collaborators have evaluated BEAS with call-detailed-record (CDR) queries and found that BEAS is able to compute exact answers to more than 90% of their CDR queries, reduce big datasets from PB (10¹⁵) to GB (10⁹) and improve the performance by orders of magnitude [15].

Organization. In the remainder of the paper, we give a brief introduction to bounded evaluation (§2) and the data-driven approximation scheme (§3). Putting these together, we present BEAS, our resource-bounded query evaluation system (§4). We focus on SQL queries on big data in this paper, which account for a large part of big data analytics.

2. Bounded evaluation

Given an SQL query Q posed on a big dataset D, bounded evaluation [9] aims to compute the exact answer Q(D) to Q in D by accessing only a bounded subset D_Q of D that includes necessary information for answering Q in D, instead of the entire D. The idea is simple, but it is non-trivial to identify D_Q. To this end, it makes use of an access schema $\mathcal{A}$, which is a set of access constraints, i.e. a combination of simple cardinality constraints and their associated indices on the data.

Bounded evaluation. Under an access schema $\mathcal{A}$, query Q is boundedly evaluable if for each dataset D that conforms to $\mathcal{A}$, there exists a fraction D_Q⊆D such that

Intuitively, query Q is boundedly evaluable under $\mathcal{A}$ if Q(D) can be computed by accessing a bounded fraction D_Q of D, no matter how big the dataset D grows. We identify D_Q by reasoning about the cardinality constraints in $\mathcal{A}$ and fetch D_Q by using the indices in $\mathcal{A}$. A dataset D conforms to $\mathcal{A}$ if D satisfies the cardinality constraints of $\mathcal{A}$ and has indices of $\mathcal{A}$ built on it.

Bounded evaluation suggests that given an application that requires querying big datasets, we can first discover an access schema $\mathcal{A}$ offline, based on an analysis of historical queries. We then take SQL queries Q online and check whether Q is boundedly evaluable under $\mathcal{A}$. If so, query Q is guaranteed to be answered on big datasets by accessing a bounded amount of data.

Effective algorithms are in place for discovering access schema from historical queries, incrementally maintaining the access schema in response to updates, checking the bounded evaluability of input queries and generating query plans for bounded queries by accessing a bounded amount of data. As an example, below we consider how to check the bounded evaluability.

Deciding bounded evaluability. A challenge is that it is undecidable to check whether an SQL query is boundedly evaluable under an access schema $\mathcal{A}$ [9]. The undecidability remains intact for relational algebra (RA), denoted by RA, which is SPC extended with set union and difference, and is the first-order logic fragment of SQL. To cope with this, an effective syntax$\mathcal{L}$ was developed [12]. That is, $\mathcal{L}$ is a class of RA queries such that under access schema $\mathcal{A}$,

That is, $\mathcal{L}$ identifies the core subclass of boundedly evaluable RA queries under access schema $\mathcal{A}$, without sacrificing their expressive power up to equivalence. This is analogous to how database management systems (DBMSs) support range-safe relational calculus queries, which is undecidable [18]. Based on the effective syntax, we can efficiently check whether a query Q is boundedly evaluable, and if so, generate a query plan to answer Q by accessing a bounded amount of data [12].

The unique features of bounded evaluation. The foundation of bounded evaluation was established in [8–10]. The theory was first put in action for SPC [11] and then extended to RA [12]. A prototype system was developed in [14] and offers the following:

(1) Bounded evaluability. It is able to check whether an input SQL query Q is boundedly evaluable, and if so, answer Q by accessing a bounded amount of data from a (possibly big) dataset.

(2) Plug and play. Bounded evaluation can be readily built on top of commercial DBMSs and provides the DBMSs with a convenient capability of querying big relations under limited resources.

(3) Join reduction. Access constraints provide us with new optimization rules, to replace costly join operations with simple data fetch by leveraging their associated indices at the query level.

We found that about 77% of SPC queries [11] and 67% of SQL queries [12] are boundedly evaluable. Our industry collaborators found that more than 90% of their CDR queries are boundedly evaluable.

The study of bounded evaluation is among the first efforts to compute exact answers to queries in big datasets under limited resources. In contrast to commercial DBMSs, it decides whether an input query is boundedly evaluable, and if so, it generates a bounded query plan, by reasoning about access schema. Access schema is implemented with indices, but as opposed to conventional indices, it allows us to reason about cardinality constraints at the query level, reduce costly join operations and deduce bounded query plans. Moreover, conventional indices retrieve entire tuples [19]. In contrast, with access constraints, we fetch distinct partial tuples consisting of only attributes needed for answering a query. For instance, as shown in example (2.1), we only fetch the name, rating and city attributes of restaurant, but not price, street and country, since answering Q₁ does not need the latter. That is, bounded evaluation does not retrieve duplicated and unnecessary attributes or tuples; the redundancies get inflated rapidly with joins in conventional query evaluation.

3. Data-driven approximation

For queries Q that are boundedly evaluable under an access schema, we can answer Q by accessing a bounded amount of data. What can we do if query Q is not boundedly evaluable? Is it still possible to compute Q(D) in a big dataset D under constrained resources? We tackle this question next.

Approximation. We propose a data-driven scheme for approximate query answering. It is parameterized with a resource ratioα∈(0, 1], indicating that our available resources can only afford to access an α-fraction of a big dataset D. Given ratio α, dataset D and an SQL query Q over D, the approximation scheme identifies D_Q⊆D and computes Q(D_Q) and a ratio η∈(0, 1] such that

Intuitively, the scheme computes a set Q(D_Q) of tuples as the approximate answer to query Q in big dataset D, by accessing at most α|D| tuples in the entire process. Thus, it can scale with D when D grows big by setting the ratio α small. Moreover, Q(D_Q) assures a deterministic accuracy bound η [13]:

That is, the set Q(D_Q) consists only of ‘relevant’ answers, i.e. each tuple in Q(D_Q) is a sensible answer to users, up to distance η; here, the distance between s and t is the sum of the pairwise distances of their attributes, which is in turn measured in terms of a distance function in the domain of the corresponding attribute (see an example shortly and [13] for a definition). Moreover, Q(D_Q) ‘covers’ the exact answer, i.e. each tuple in the exact answer Q(D) finds a tuple s∈Q(D_Q) within distance η, and no tuple in Q(D) is missed by Q(D_Q) up to bound η. It finds sensible answers in users' interest and suffices for exploratory queries, e.g. real-time problem diagnosis on logs [20]. The larger the ratio α is, i.e. the more resources we can afford, the higher the accuracy bound η we can get.

As observed in a recent survey [21], approximate query answering is challenging, and little practical use has emerged from it. Nonetheless, we can make data-driven approximation work in practice by employing a mild extension of the access schema that we have seen earlier.

It has been shown [13] that for any dataset D, there exists an access schema $\mathcal{A}$ such that for any resource ratio α∈(0, 1] and any SQL query Q over D, one can effectively identify a subset D_Q of D by reasoning about the constraints in $\mathcal{A}$ and deduce a deterministic accuracy bound η such that |D_Q| ≤ α|D| and accuracy(Q(D_Q), Q, D)≥η. Moreover, the larger the resource ratio α is, the higher the accuracy bound η is. The access schema $\mathcal{A}$ can be effectively computed offline and efficiently maintained online in response to updates to dataset D [13].

Unique features of data-driven approximation. There has been a host of work on approximate query answering, typically based on one of the following two approaches (see [21,22] for surveys): (a) synopsis [23–27] or (b) dynamic sampling, e.g. [20,28–30]. The first approach computes an one-size-fit-all synopsis D′ of a dataset D and uses D′ to answer all queries posed on D. A representative method of the second approach is BlinkDB [20]. Assuming predictable QCSs (query column sets), i.e. ‘the frequency of columns used for grouping and filtering does not change over time’, BlinkDB selects samples from historical QCS patterns and caches them as views. It targets aggregate queries, i.e. queries to compute max, min, count, sum and average values grouped by certain attributes. It answers such aggregate queries by using the samples instead of accessing the original datasets and offers probabilistic error rates for the approximate answers computed.

As opposed to the prior approaches, the data-driven approximation scheme makes use of an access schema to identify an α-fraction D_Q of dataset D. It offers the following:

(1) Unpredictable queries. The scheme does not assume the availability of any prior knowledge about user queries Q. By contrast, previous approaches make various assumptions on future queries, e.g. they assume that workloads, query predicates or QCSs of future queries are known in advance.

(2) Generic queries. The scheme is able to handle generic SQL queries, aggregate or not. For instance, query Q₂ in example (3.1) is not an aggregate query. By contrast, previous approaches ‘substantially limit the types of queries they can execute’ [20] and typically focus on aggregate queries.

(3) Deterministic accuracy bound. As remarked earlier, the data-driven scheme proposes an accuracy measure in terms of both relevance and coverage, to ensure that each tuple in the approximate answer computed is sensible and all tuples in the exact answer are covered. By contrast, previous approaches provide either no accuracy guarantee at all or probabilistic error rates for aggregate queries only. Such error rates do not tell us how ‘good’ each approximate answer is, which is one of the reasons why approximate query answering has not been widely used in practice.

Our preliminary study using real-life data finds that the data-driven approximation scheme computes approximate answers to SQL queries, aggregate or not, with accuracy η≥0.82, even when α is as small as 5.5 × 10⁻⁴ [13]. That is, it reduces D of PB size to D_Q of 550 GB.

4. A resource-bounded query evaluation framework

Putting bounded evaluation and data-driven approximation together, we develop BEAS (Boundedly EvAluable Sql), a system for querying big relations under constrained resources.

BEAS. For a big dataset D in an application, BEAS takes a resource ratioα∈(0, 1] as a parameter, which is estimated by an analysis of available resources and the size of dataset D. It discovers an access schema $\mathcal{A}$ offline, by striking a balance between the speedup of query evaluation and the space cost introduced by the indices in the access schema $\mathcal{A}$. Then, BEAS answers SQL queries posed on dataset D online. Given an SQL query Q, BEAS works as follows:

That is, under the resource constraint α, BEAS computes exact answers Q(D) when possible, and approximate answers Q(D_Q) otherwise with accuracy η. In the entire process, it accesses a small fraction of data that can be afforded by available resources. BEAS also supports incremental maintenance of the indices in $\mathcal{A}$ in response to updates to dataset D and guarantees that the maintenance cost is determined by the size of changes, not by the size of dataset D [11,13].

Unique features of BEAS. BEAS departs from commercial DBMS by promoting an unconventional query evaluation paradigm. It is unique in the following:

(1) Querying big relations. It is parameterized with a resource ratioα, i.e. it is able to scale with arbitrarily large datasets D by adjusting ratio α based on available resources.

(2) Separating exact answers from approximate answers. By effectively deciding whether an input query is boundedly evaluable under an access schema, BEAS is capable of telling its users whether the answers to their queries are exact or approximate. Moreover, for approximate answers, it provides deterministic accuracy bounds η in terms of both relevance and coverage.

(3) Generic. BEAS is able to answer SQL queries that are unpredictable, without assuming prior knowledge about future queries, and generic, no matter whether the queries are aggregate or not.

(4) Ease of implementation. BEAS can be built on top of commercial DBMS and provide the DBMS with an immediate capacity to query big relations under constrained resources. It offers its own optimization strategies and is also able to further improve its query plans, bounded or approximate, by making use of existing DBMS optimizers that have been developed for decades.

In light of these, BEAS is promising for providing small companies with the capability of big data analytics under limited resources. It can also help big companies to reduce the cost and improve efficiency [15]. In particular, for computational problems that are not parallel scalable, bounded evaluation and data-driven approximation offer a feasible solution that does not rely on large-scale parallel computation. This said, bounded evaluation and data-driven approximation can be parallelized to benefit from parallel processing provided that resources are available.

The idea of resource-bounded query answering is not limited to querying big relations. It has been shown that bounded evaluation improves the performance of graph pattern matching via subgraph isomorphism, an intractable problem [1] that is widely used in social media marketing, knowledge base extension and graph data cleaning, by four orders of magnitude on average [31]. For personalized social search via subgraph isomorphism, data-driven approximation retains 100% accuracy (i.e. η = 1) when α is as small as 1.5 × 10⁻⁶ [32], i.e. when processing graphs G of 1 PB, they access only 15 GB of data, i.e. reducing G from PB to GB while retaining high accuracy.

Data accessibility

This article has no additional data.

Competing interests

I declare I have no competing interests.

Funding

W.F. is supported in part by ERC 652976, Royal Society Wolfson Research Merit Award WRM/R1/180014, NSFC 61421003, EPSRC EP/M025268/1, Foundation for Innovative Research Groups of NSFC, Joint Lab between Edinburgh and Huawei, Beijing Advanced Innovation Centre for Big Data and Brain Computing and Shenzhen Institute of Computing Sciences.

Footnotes