Embed Size (px)
Citation preview
ProgressiveDB – Progressive Data Analyticsas a Middleware
Lukas BergTU Darmstadt
darmstadt.de
Tobias ZieglerTU Darmstadt
darmstadt.de
Carsten BinnigTU Darmstadt
darmstadt.de
Uwe RohmUniversity of Sydney
ABSTRACTProgressiveDB transforms any standard SQL database intoa progressive database capable of continuous, approximatequery processing. It introduces a few small extensions to theSQL query language that allow clients to express progres-sive analytical queries. These extensions are processed inthe ProgressiveDB middleware that sits between a databaseapplication and the underlying database providing interac-tive query processing as well as query steering capabilitiesto the user. In our demo, we show how this system allowsa database application with a graphical user interface to in-teract with different backends, while providing the user withimmediate feedback during exploratory data exploration ofan on-time flight database. ProgressiveDB also supports ef-ficient query steering by providing a new technique, calledprogressive views, which allows the intermediate results ofone progressive query to be shared and reused by multipleconcurrent progressive queries with refined scope.
PVLDB Reference Format:Lukas Berg, Tobias Ziegler, Carsten Binnig and Uwe Rohm. Pro-gressiveDB – Progressive Data Analytics as a Middleware. PVLDB,12(12): 1814-1817, 2019.DOI: https://doi.org/10.14778/3352063.3352073
1. INTRODUCTION
Motivation. Interactive visualisations are arguably the mostimportant tool to explore, understand and convey facts aboutdata. For example, as part of data exploration visualisationsare used to quickly skim through the data and look for pat-terns along various dimensions of the data. This requires togenerate a sequence of visualisations and allow the user tointeract with them. A recent study [6] has shown that visual
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. To view a copyof this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. Forany use beyond those covered by this license, obtain permission by [email protected]. Copyright is held by the owner/author(s). Publication rightslicensed to the VLDB Endowment.Proceedings of the VLDB Endowment, Vol. 12, No. 12ISSN 2150-8097.DOI: https://doi.org/10.14778/3352063.3352073
delays of 500ms tend to decrease both end-user activity anddata set coverage, due to the reduction in rates of user inter-action that is crucial for overall observation, generalizationand hypothesis.
Unfortunately, existing database systems are ill-suited forthese types of interactive workloads that result from visualexploration tools for different reasons: (1) Unfortunately,when the data sets are larger, computing results for even asingle visualisation can take seconds or even minutes, creat-ing a significant barrier to interactive data analysis. Onepromising route to compute continuously refining resultsthat was already published in the late 1990’s was onlineaggregation [4]. Different from offline-sampling, which isused in BlinkDB [1] or VerdictDB [8], online aggregationcan provide interactive response times for arbitrary aggre-gate group-by queries over single tables and more recent ex-tensions also support queries including joins [7, 5]. However,online aggregation has not yet made its way into any of thecommercial DBMSs available today. (2) In interactive dataexploration, users often want to quickly refine a query. Forexample, in some customer analysis a user might quickly tryout different age ranges as filter criteria. In today’s DBMS,every user interaction results in a new SQL query putting ahigh overhead on the performance of the system.
Contribution. In this paper, we propose ProgressiveDB , amiddleware that provides progressive execution capabilitieson top of non-progressive databases such as PostgreSQL,MonetDB, etc. That way, ProgressiveDB transforms anystandard SQL database into a progressive DBMS.
In order to provide progressive query execution to ap-plications, ProgressiveDB introduces a few but importantextensions to the SQL query language (called progressiveextensions) that allow clients to express progressive analyt-ical queries and consume continuously refining results. Fur-thermore, the SQL extensions of ProgressiveDB additionallysupport query steering that can be used by applications tochange running queries without the need to start a separatequery for each user interaction.
For executing the progressive SQL extensions, Progres-siveDB rewrites the incoming queries into a set of smallerqueries that are continuously executed against the underly-ing database. ProgressiveDB is that way capable of contin-
1814
Q1) SELECT PROGRESSIVE
AVG(delay)
FROM OnTime
GROUP BY origin
Q2) SELECT AVG(delay)
FROM OnTime
WHERE …
J
D
B
C
Query Router
Progressive Executor
ExactExecutor
Meta + Results
Progressive Table
OnTime_1
OnTime_2
OnTime_N
…
Q11
Q12
Q1N
Q2
Figure 1: System Architecture of ProgressiveDB
uous query processing to answer analytical queries at inter-active speeds and refine results in a progressive manner.
The contributions of this demo paper are as follows:
• We define several extensions of SQL that allow users toexpress progressively executed queries with additionalquery steering capabilities.
• We present the design of ProgressiveDB , a middlewareengine that transforms any SQL database system intoa progressive DBMS and discuss progressive query pro-cessing algorithms of ProgressiveDB that are imple-mented in our middleware which is based on ApacheCalcite.
• We discuss our demonstration scenario, where an ap-plication on top of ProgressiveDB can be used to ex-plore and analyse a flight delay database [3].
Outline. In the remainder of this paper, we first introducethe system architecture of ProgressiveDB (Section 2), beforewe define our progressive extensions of SQL (Section 3) thatProgressiveDB supports. Section 4 describes the demo ap-plication that allows attendees to interact and explore Pro-gressiveDB with the flight database.
2. SYSTEM OVERVIEWThe goal of ProgressiveDB is to enable progressive query
processing and steering of queries without changing the un-derlying DBMS. Consequently, we utilize a middleware-basedapproach that provides progressive query capabilities to ap-plications via a standard JDBC interface. This middlewarehandles all query routing, intermediate result processing,and manages the internal state of the progressive query exe-cution as depicted in Figure 1. To support progressive queryexecution, a table has to be specifically prepared and madeavailable to Progressive-SQL as a chunked Progressive Table(depicted on the right side of Figure 1). What is importantis that chunking can be typically implemented by simply us-ing the partition functions of an underlying database. SeeSection 3.1 for details.
As a query interface, ProgressiveDB supports both —standard SQL queries, like Q2, which are directly executedon the underlying DBMS on the whole table, and progressivequeries as shown for Q1 formulated in our Progressive-SQLlanguage (which is a SQL extension). Both are handled bythe Progressive Executor of the middleware. For execut-ing a query formulated using our progressive extensions forSQL like Q1, the Progressive Executor translates the in-coming progressive queries into a series of sub-queries (Q11
- Q1N ) on the prepared Progressive Table. Each sub-queryis executed on the underlying DBMS on a per chunk basis– typically a single partition of the table (cf. Section. 3.1).
The Progressive Executor progressively combines the partialresults over individual chunks with the current state of thequery execution. Every time a new sub-query has finishedthe approximate overall result is progressively updated andsent to the application. Consequently, the more of the tableis processed (i.e., the more sub-queries have been finished)the lower the relative error. See Section 3.2 for details.
Furthermore, the middleware is also responsible to provideefficient execution strategies for query steering that are alsopart of our progressive SQL extensions. For example, partof our SQL extensions are so called progressive views thatallow an application to refine an already running query withadditional filtering predicates or to drill-down its groupingcategories. In this case, the ProgressiveDB middleware man-ages all necessary intermediate state to do so without havingto re-run any already completed (sub-)query. See Section 3.3for details.
Our implementation of ProgressiveDB is based on theApache Calcite data management framework [2]. For Pro-gressiveDB , we extended Calcite with the Progressive-SQLsyntax, and added the progressive executor components.
3. PROGRESSIVE SQLApplications using ProgressiveDB can express analytical
queries in Progressive SQL which allows them to executequeries progressively with interactive latency on the under-lying database, and also with the possibility to further refinean already running progressive query (i.e., query steering).
3.1 Database PreparationIn order to be used by Progressive SQL, a table has to be
prepared for progressive queries first. ProgressiveDB parti-tions tables into chunks holding data such that each parti-tion is small enough to be queried by an analytical querywithin a given query latency. An important aspect of thispreparation step is that tuples are assigned randomly toeach chunk so that the individual sub-queries sent by Pro-gressiveDB access indeed a random sample of the table.
Note that chunking can be implemented without the needto copy the data of a table in the underlying database sys-tem. Instead, if a database system natively supports parti-tioning (e.g., most commercial DBMS or PostgreSQL) Pro-gressiveDB makes use of this capability: the table will bepartitioned into n randomized ’chunks’ such that the av-erage response time of a simple aggregation query is belowthe configured threshold latency. Note that for most systemspartitioning is natively supported. For systems without par-titioning support, a chunking column and an index on thatcolumn are used by ProgressiveDB .
1815
3.2 Progressive QueriesWith progressive query execution, clients continuously
receive approximate query results which are progres-sively getting more accurate approaching the final result.Clients initiate a progressive query by adding the keywordPROGRESSIVE to an aggregation query:
SELECT PROGRESSIVE aggregation˙listFROM relationWHERE condition
GROUP BY group˙attrs
ProgressiveDB translates such a progressive aggregationquery Q internally into a series of sub-queries qi such thateach sub-query queries only a single chunk (partition) of theprepared progressive table. The results of each sub-query qiare then combined in the middleware with the current stateof the progressive query execution to produce an approxi-mate overall aggregation result at stage i.
ProgressiveDB computes the aggregation approximationi
based on the combined result of all previous sub-queries qj(j < i) and the additional partial result of sub-query qi. Thisis possible for all decomposable aggregation functions, suchas SUM, COUNT and AVG, where the result can be computed byaggregating over sub- or auxiliary-aggregates for subsets ofthe data. In case of SUM and COUNT, the sub-aggregate valuesare simply added; in case of AVG, the final aggregate valueis computed from the queried partial SUM and COUNTauxiliary-aggregate values. These intermediate aggregationvalues are further scaled based on the query progress, andthe number and size of the chunks of the progressive table.
Clients receive a continuous refining query result that con-sists of the progression of approximate aggregation resultsafter each sub-query. Each result row is tagged with the cor-responding sub-queries sequence number and a confidencevalue for the approximation (note that a general groupingquery could have multiple result rows, one per group, whichwould all be tagged with the same sequence number):
0, group attr, aggregation approximation 0, confidence 0
1, group attr, aggregation approximation 1, confidence 1
2, group attr, aggregation approximation 2, confidence 2
...
This way, from the viewpoint of a client, the aggregationresults are progressively getting closer to the exact result.It is the responsibility of the client application to use thesepartial approximate query results to progressively updatetheir user interface. Basically, query results with sequencenumber i replace query results with sequence number i− 1.
The current implementation is limited to single table queries.In future, we plan to support joins in ProgressiveDB follow-ing the ideas of [5], but adapted to use the table chunksavailable in ProgressiveDB .
3.3 Query SteeringDuring interactive data exploration, users often want to
quickly refine a query, for example to further filter a resultor drill-down into a result. While the progressive queriesas introduced above give fast (low latency) and progressivefeedback to users, they do not allow the user to steer thequery at runtime. With our SQL syntax so far, refining aquery would require for each step a new query which hasto be processed by the underlying database from scratch –
resulting in both execution overhead and a delay in achievinga result accuracy comparable to the already running query.
To facilitate the steering of progressive queries, Progres-sive SQL introduces the concept of a PROGRESSIVE VIEW forwhich some FUTURE grouping attributes and filter conditionscan be specified:
CREATE PROGRESSIVE VIEW name AS
SELECT aggregation listFROM relationWHERE condition (AND condition i FUTURE)*
GROUP BY grouping list (, group i FUTURE)*
The general semantic of a PROGRESSIVE VIEW is the sameas with a progressive query: ProgressiveDB executes a se-ries of sub-queries qi such that each sub-query queries onlya single chunk table of the prepared database schema, andprogressively combines these partial results with the currentquery execution state to new result approximations. Theexecuted sub-queries, however, include additional groupingattributes for each grouping FUTURE clause and necessaryattributes for FUTURE conditions from the view definition.The sub-queries also pre-filter the data with their filter con-ditions constructed such that any FUTURE conditions can stillbe evaluated on the view’s result approximations.
ProgressiveDB caches the processed partial results taggedwith sequence number i and confidence values in its internalstate under the view name. A client application can query aprogressive view with any combination of the grouping andfilter attributes, and ProgressiveDB will return only the ag-gregated results for the corresponding groups and matchingfilter conditions from its internal cache.
A typical use case for this is that the client initially queriesthe progressive view for only those groupings and condi-tions which are not marked as FUTURE. The user then inter-acts with the visualisation of the received progressive queryresult, for example by drilling down in one of the FUTURE
grouping attributes. The application therefore sends a newquery to the view which indicates which FUTURE grouping at-tribute should be used. Since ProgressiveDB caches the in-termediates of a previous query, it can then immediately re-turn an approximate drill-down result at the confidence levelof the state where the initial query was, which it continuousto progressively update while further sub-queries are exe-cuted. This avoids the latency and overhead of re-sendingall previous sub-queries with a new group-by clause.
4. DEMONSTRATION SCENARIOTo demonstrate the capabilities of ProgressiveDB , we use
the well-known airline-on-time database [3]. We have builta small data exploration application with an interactive webinterface on top of ProgressiveDB which allows to analyseflight delay information as shown in Figure 2a. We popu-lated a PostgreSQL and a MySQL database with all flightdata for the 40 largest US airports, resulting in a total of ca.11 GB data on disk. The following two scenarios are alsoshown in our supplementary demo video.
4.1 Scenario 1: Progressive QueriesThe first use case demonstrates the progressive query ex-
ecution of ProgressiveDB . As shown in Figure 2a, the userfirst selects one of the pre-defined queries from the drop-down menu 1©, which then gets executed concurrently intwo modes: The left-side of the window shows the result
1816
(a) Screenshot of Usage Scenario 1
Database System0s
1s
10s
100s
Res
pon
seL
aten
cy(s
)
InteractiveThreshold
2.4% Rel.Error
2.2% Rel.Error
0% Rel.Error
0% Rel.Error
Pro
gre
ssiv
eR
esu
lts
ProgressiveDB
VerdictDB
PostgreSQL
(b) Response Latencies
Figure 2: Demo Screenshot (left) and Latency Comparison of different Systems (right)
of the progressively executed query 2©, while the right-sideof the window shows the result of running the analytical di-rectly on the underlying database 3©. Attendees will see thatwhile they get an immediate feedback from the progressivequery, which also constantly updates with the latest flightstatistics until the result is exact, they have to wait for aresponse on the right-hand side.
The native execution on the underlying database only re-turns a result once the query has completed on the wholedataset, which typically means a delay much worse than thetargeted 500ms interactive latency. This can also be seen inthe graph of Figure 2b, which compares the first-responselatency of ProgressiveDB over PostgreSQL with native Post-greSQL for the same query. Just for comparison – not partof the demo – we also included the first response time of Ver-dictDB over PostgreSQL (which uses a pre-computed sam-ple) on the same dataset. The progressive query is executedby ProgressiveDB with a series of sub-queries. These in-ternal sub-queries can be inspected by attendees using the’Query Log’ button of the user interface 4©.
While the progressive query is executing, attendees canalso click on the result bar of any airport to start a secondquery which analyses the flight delay information at thisairport, but now shown per day of the week 5©. The pro-gressive result of this second query is shown below the chartof the first query, and it is also compared to a native execu-tion. Attendees can note that the second query, while start-ing immediately after being selected, does run longer andwith an initial less accurate approximation because withoutquery steering a new separate query is initiated which hasto analyse the data from scratch. We show the effects ofquery steering in the second scenario below.
Finally, the user interface also allows attendees to switchbetween different backend database engines (i.e., PostgreSQLand MySQL) to demonstrate the flexibility of the middle-ware approach of ProgressiveDB .
4.2 Scenario 2: Query SteeringThe second use case demonstrates the query steering ca-
pabilities of ProgressiveDB . While the previous use caseshowed how ProgressiveDB allows interactive response timesof single progressive queries, it also demonstrated that re-fining a query results in an initial loss of accuracy due tothe restart of a new query from scratch. However, in manyapplications the potential refinements of a query are pre-determined by the user interface, and hence ProgressiveDB
introduces the concept of a progressive view which computesan approximate query result suitable for different queries.
Our demo application therefore includes a second view 6©,which allows query steering using a progressive view (CREATEVIEW... GROUP BY origin, dayofweek FUTURE). This pro-gressive view helps to drive a cross-filter visualisation whereusers can select different airports on the first visualisation,which then instantly affects the output on the second chartwhich represents the progressive query result of a refinedquery. The benefit here is that any of the refined queriesstarts at the same progress and accuracy level as those ofthe first query, because it can rely on the intermediate re-sults in the progressive view. This also results in less loadon the backend database systems as only one sequence ofsub-queries has to be executed.
5. SUMMARYProgressiveDB provides three main innovations: Firstly,
a middleware that transforms any SQL database into a pro-gressive database. Secondly, ProgressiveSQL as a simple touse query interface for interactive applications. Finally, aprogressive view mechanism that extends ProgressiveSQLby efficient query steering capabilities.
AcknowledgementsWe thank Schloss Dagstuhl and the organizers of Seminar18411 for the opportunity and motivation to pursue the workreported in this paper.
6. REFERENCES[1] S. Agarwal et al. Blinkdb: queries with bounded errors and
bounded response times on very large data. In EuroSys, pages29–42, 2013.
[2] E. Begoli et al. Apache Calcite: A Foundational Framework forOptimized Query Processing Over Heterogeneous Data Sources.In ACM SIGMOD, 2018.
[3] Bureau of Transportation Statistics. ASA 2009 data expo.http://stat-computing.org/dataexpo/2009/.
[4] J. M. Hellerstein et al. Online aggregation. In ACM SIGMOD,pages 171–182, 1997.
[5] F. Li et al. Wander join: Online aggregation via random walks.In ACM SIGMOD, pages 615–629, 2016.
[6] Z. Liu et al. The effects of interactive latency on exploratoryvisual analysis. IEEE Trans. Vis. Comput. Graph.,20(12):2122–2131, 2014.
[7] G. Luo et al. A scalable hash ripple join algorithm. In ACMSIGMOD, pages 252–262, 2002.
[8] Y. Park, B. Mozafari, J. Sorenson, and J. Wang. Verdictdb:Universalizing approximate query processing. In ACMSIGMOD, 2018.
1817
