Towards Scalable Hybrid Stores: Constraint-Based Rewriting to the Rescue
Alotaibi, Rana
Bursztyn, Damian
Deutsch, Alin
Manolescu, Ioana
Zampetakis, Stamatis
Big data applications routinely involve diverse datasets: relations flat or nested, complex-structure graphs, documents, poorly structured logs, or even text data. To handle the data, application designers usually rely on several data stores used side-by-side, each capable of handling one or a few data models, and each very efficient for some, but not all, kinds of processing on the data. A current limitation is that applications are written taking into account which part of the data is stored in which store and how. This fails to take advantage of (i) possible redundancy, when the same data may be accessible (with different performance) from distinct data stores; (ii) partial query results (in the style of materialized views) which may be available in the stores. We present ESTOCADA, a novel approach connecting applications to the potentially heterogeneous systems where their input data resides. ESTOCADA can be used in a polystore setting to transparently enable each query to benefit from the best combination of stored data and available processing capabilities. ESTOCADA leverages recent advances in the area of view-based query rewriting under constraints, which we use to describe the various data models and stored data. Our experiments illustrate the significant performance gains achieved by ESTOCADA.
 This work is a joint project with Damian Buschentan, Aline Deutsch, Iwana Monalisco and Stamata Zamtikes. Modern application often need to manage and analyze widely diverse dataset that span multiple data models. The data can be structured, complex structure like graphs or even fully structure like logs and text. Constradating disparate data to fit into a single data model may degrade application performance. Further, creating diverse dataset and maintaining the ATL pipeline can prove to be a labor intensive. In response to this variety of data models and the processing task and all of our data models, numerous database management systems have emerged. However, these database management systems in terms of their capabilities, their performance, speed and scale make each of them unique. But none of these systems is emerging as universal one-size-fits-all DBMS system, as some systems provide excellent performance for some tasks, or may perform poorly for others, or may not support them at all. As an emerging trend is to use different database management systems side by side, better exploit their performance, which is the goal of PolyStore System. The main design principle of PolyStore Systems is to place each type of data in native data store that is specifically designed for that specific data model and mainly focus on enabling the query processing across the Petrogenous data stores by allowing a user to use a variety of query languages and interfaces, some synastic query data that resides in multiple vacant. Some examples of an existing PolyStore Systems. However, what are the unexplored opportunities in existing PolyStore System architecture? They don't exploit possible data redundancy when the same data can be stored in several data stores, some of which may support the query operations more efficiently than others. They are unable to take the advantage of the present centralized views, which can be available in one of several data stores with different data models. Our vision is to allow application to transparently exploit the existence of the data store in a set of heterogeneous data store in a PolyStore sitting, a set of overlapping views, by abuse-based query writing, and take the maximum advantages of these data stores' query processing capability. This is not a classical view-space writing problem, as user queries and views and rewritings are expressed across models and languages. In a PolyStore sitting, the views may draw data from one or several data stores of the same or different data models, and they are metallized yet again in distinct data models. And the user queries can contain various sub-expressions, each in its own query language. As an example, we have a Mimic data set containing a patient data who states in the Pet Israel Medical Center, the data set consists of the patient information, which is so relational back-end, and a patient's laptox result, and drug's information, which is so adjacent back-end, a caregiver note, which need to be processed and followed by a surgeon. And we have a query, which asks for female patients have been diagnosed with coronary indices and abnormal laptox result. We want to find the date and time for hospital admission and the dragoz of types, addictive rescapillation. Suppose that our disposal, we have a view one, which partially computes the query result, joins the data in solar with the data in adjacent back-end, and it's metallized in adjacent back-end. And suppose we have a view two, which joins the data in adjacent back-end with the data in the relational back-end, and it's metallized in relational back-end. Evaluating the query using a polystore engine, which need to access the three back-ends to answer the query, the query took about six minutes comparing by evaluating the query using the views. Yes, metallized views enhance its performance, and also they can strongly improve performance when they are stored across data stores by exploiting different strengths of each systems. The technical question to be asked, how we can exploit the existing of these cross-molder views, storage-situ-fetrogenes data stores, given across smaller and language query, and a polystore setting. In this talk first, I'll talk about our cross-molder views-based writing problem statement, our approach, architecture overview, then our experimental evaluation, finally our contributions. Our cross-molder views-based writing problem statement is the following. Given a cross-molder and language query, expressed over several data sets, which are stored across data stores, and a set of metallized views, which are expressed over these data sets, stored across data stores, we want to find the equivalent to writing of the query, using the views, which minimizes the cost estimation. So we're dealing with the views-based query writing across arbitrary set of data models. The views-based writing problem has been well studied in the literature. However, most of the work had an assumption that the views data and the application data are organized according to the same data model, which is mostly relational, or they allow different data models for storing the views, but they only consider XML as an application data model. So the query and syncing approach in their setting is mainly focused toward XML data model and query language. However, this is different in our setting. We want to have a unified approach, supporting any data model at the application level and at the view level. Our approach and the architecture overview. The key requirement in our setting is to reason about queries and views, involving multiple data models and query languages. However, this comes with several challenges. First, not every data model and query language comes with a views-based rewriting algorithm. And even without such algorithm, none of these algorithms can be extended to across model views-based writing solutions. And any cross-modal views to the writing solution that we propose need to be extendable to additional data model and query language. Our approach to address these challenges is to reduce a variety of query languages and data models into a single one for the purpose of reasoning about it, which is the relational model with integrity constraints. The architecture of our approach is the following. We are giving different data models, cross-modal query and cross-modal views. First, we encode the structure of various data models relationally with the support of integrity constraints, which capture the original feature or the key aspect of these data models. We encode the cross-modal query into relational query, and we encode the cross-modal views into a set of integrity relational constraints, which capture the correspondence between the views input and its output. Now our problem has been purely reduced to a relational setting with integrity constraints. And the rewriting engine of choice is Chase and Backchase writing engine, where we incorporated this engine and novel scale-up techniques to make it scalable in a polystore setting when we have a large number of generated constraints. The output of the rewriting engine is a set of relational reformulation, which will be decoded into an integration plan containing the sources subqueries. Of course, different evaluation plans may lead to different performance. We choose the rewriting of an evaluation plan with the minimum cost based on cost-based model. First, I'll talk about how we encode the structure of various data models relationally and I'll use JSON data model as an example. We encode, we represent the organization of JSON data model using a set of virtual relations. We call them virtual relational encoding of JSONs. For example, the first relation here, collection name relation, attach an ID for every element in the name JSON collection. And the child's relation state that the value identified by the child's ID is immediately listed within the value identified by the parent ID. And the type indicates what is the type of the parent ID. So, the parent ID could be a JSON object or it could be a JSON array. And if the parent ID is a JSON object, then the key holds the field whose associated value is the child ID. If the parent ID is a JSON array, then the key holds the index whose associated value is the child ID. For example, here I have the JSON object in a MIME collection, and here we encode relational MIME collection which attach an ID for every element in the collection. And here in the child's relation, which is state that the result field is immediately listed within the value identified by the parent IDP. And the same will represent the value which is associated with the result field. The JSON data model will not be stored relationally. However, we only use these relations to encode the queries and the views, so we can reason about them. For example, here I'm using the same JSON object, and here we have the JSON query which navigates into this JSON object. And here I'm showing you the corresponding relational encoding of this JSON query using our virtual JSON relations. Also, we need to define a set of entity constraints which capture the original feature of this data model. For example, the first constraint state that there is no JSON object that can have two distinct key value pairs having the same key. And there is no JSON array that can have two distinct elements at the same position. Here are the list of the data models in the query language that we currently supporting. The relational data model with SQL query language, the JSON data model with SQL query language, SQL query language with JSON support in PostgreSQL, and Spark SQL declarative query language, as for key value data model, RIDIS APIs, and for XML, execuity query language. Now, how about encoding the queries and the views? The queries and the views are expressed using a QBT-XM syntax, which is an integration language that we design to support queries over several data stores, each of its own data model, and query language. QBT-XM follows the block-based design introduced in System R, however, the main difference between the query block trees introduced in System R and our QBT-XM syntax is that each block in QBT-XM is expressed in different data model and query language. The QBT-XM consists of four where return clause, four clause introduce several query blocks, single by rotation, for example, PR annotation mean PostgreSQL query language for this block, PGA annotation mean PostgreSQL query language with JSON support for this block, for where clause we are dealing with the scholar quality and return clause we specify how to construct a new data based on the variable bindings introduced in the four clause. The user query will be encoded relationally using the set of virtual relation that it refers to. The views will be encoded into an integrity constraint, for example, which shows how the view input are related to this output. For example, here, I have the view definition in QBT-XM syntax, the right-hand side of the slide, and on the right-hand side of the slide, I have the view encoded into integrity constraints. The first block representing SQL query will be encoded into a conjunction of relational atoms. The second block representing SQL JSON query will be encoded relationally using our JSON virtual relations. In the conclusion of the constraints, we specify how a new JSON object can be constructed from the variable introduced in the four clause, the variable introduced in the body of the query. Now, as I mentioned earlier, the rewriting engine of choice is the chase and backjays writing engine, where we have optimized this engine to make it scalable in the polystore settings. The engine was mainly designed to work with very views and constraints. However, in the case of polystore setting, we can have high number of relevant views, the views that cannot be used to answer the query, and they can anchor an overhead to search for equivalently writing. So we have applied the optimization technique to reduce this overhead, and we mainly refer the audience to the paper for more details about the optimization. Our new optimized version of the engine outperforms the standard one by at least two orders of magnitudes in case of polystore settings. The output of the rewriting engine is a set of relational reformulation, which will be decoded into an integration plan. Different evaluation plan may lead to different performance, which was the rewriting of an evaluation plan with a minimum cost based on cost based model, how we can achieve that. First, the relational rewriting of the query will be partitioned into a view level subqueries, which will be decoded into the native syntax of the respective stores. And the decoded rewriting then will be translated into a logical plan that push the leaves of blocks into the native stores and applying the rest of the logical approaches integration engine. So we chose the rewriting based on a cost based model, which we have adopted from a classical cost based optimization, and through views and mediator systems. Now, what about the aggregation, our virtual function calls an arithmetic operation? We treat them under and we treat them as uninterpreted function samples, but we add integrity constraints to capture their intended meaning. For example, we add, for example, we modeled the add binary, the add operators as a relation with intending meaning that are equal x plus y, which can be captured by constraints stating that add relation is functional, add relation is commutative, and add relation is associative. As for the rewriting, we seek the rewriting under an interpreted function semantics, mainly the rewriting that use the same function call with the same argument as the original query. Our experimental evaluation. So as for the hardware platform, we have used a machine with a CPU with 20 cars, 123 giga gram, and we set the power cache to 60 gigs for all the system that we are using for our whole polystore configurations, Postgres, AsterixDB, MongoDB, and SparkSQL. We have used the Mimic dataset of size 46 gig. And the first experiment, we show the benefit that our approach can bring to a single model queries run in a single systems. We have loaded the Mimic dataset in a native JSON stores, AsterixDB, Postgres JSON, SparkSQL, MongoDB. We've designed and developed a benchmark based on Mimic dataset. We refer the audience to the page for more details about the benchmark. Among the queries that we have to enumerate the queries and the views, among the queries that we have enumerated, we choose a 50 queries which consists of joins selections, at least two level navigation to JSON documents and arrays. 58% of the queries consist of full text search predicates, 60% of them not highly selected, 40% of them highly selected. As for the views storage, we have metalyzed assets to views in Postgres, which can be represented relationally, and they partially compute the query results. And similarly, we have metalyzed assets to views in Postgres with JSON support. We picked Postgres for storing the JSON views as we have experimentally evaluated, shown that the Postgres eventually evaluate the join between the JSON dataset, and it takes the view in solar, which is a dedicated engine for evaluating the full text search predicates. Evaluating the query with the full text search predicates in SparkSQL and AsterixDB, these queries times out. The reason in case of SparkSQL, it lacks supporting any type of indices and evaluating the full text search predicates without the support of index given the size of the text that we have. Also, the JSON array and this operator in case of SparkSQL, the operator is highly efficient. Same observations apply to AsterixDB, which lacks the support of creating an index on an SID collection, and the main overhead came from unisting the JSON array as well. Postgres outperforms MongoDB since MongoDB lacks of supporting the join-reording optimization, and it doesn't natively support inner join. It must be simulated by lift out to join followed by a selection and a scan for non-values. Also, the choice of the join algorithms different than Postgres SQL. It is to be noted that none of these systems is capable to trans-transfer to exploit the existing of the views in a single model setting. Our cross-modal view space writing approach improved the performance of these queries by trans-transfer to exploit the cross-modal views stored in solar to evaluate the full text search predicates in the dedicated engine and Postgres, which eventually evaluated the join between JSON views and relational views. In this experiment, we show the benefit that our approach can bring to an existing polystore systems, BigDug from MIT and Tatooine Engine. We have placed the structure part of the dataset in Postgres relational instance, and the semi-structure part of the dataset in Postgres JSON instance, and the tick part of the data in solar. By evaluating the queries which need to access the backend, we have 60% of the queries containing full text search predicates, which are not highly selective. We observed the overhead of such queries in BigDug is dominated by moving and ingesting the result of the queries during the query runtime in Postgres to perform the join with other sub-queries. However, the tween engine performs better as it computes the join in memory using the bind join mediator, and it doesn't need to pay the intermediate storage cost during the query runtime. So to elevate this overhead in addition to the views that had been materialized, we've materialized a set of additional views which joined the data in solar with the data in Postgres and are materialized in Postgres JSON. Our cross-moder-based writing approach improved the performance of these cross-moder queries by finding the re-writing using the pre-materialized views stored in solar, stored in a Postgres relational instance, and Postgres JSON instance. This figure shows the distribution of re-writing over the set of queries that we have, and the time spent searching for re-writing is a small fraction of the query execution time. Our contributions, our approach improved the performance in natural scenarios for both cross-moder and single-moder queries. We have shown that our cross-moder views-based writing approach is portable across polystore engines, and we designed a reduction from multi-modal views-based re-writing to relational re-writing under constraints. We optimized the state-of-the-art algorithm to scale in a polystore setting. Thank you.
 This work is a joint project with Damian Buschentan, Aline Deutsch,  Iwana Monalisco and Stamata Zamtikes.  Modern application often need to manage and analyze widely diverse dataset  that span multiple data models.  The data can be structured,  complex structure like graphs or even fully structure like logs and text.  Constradating disparate data to fit into a single data model may degrade application performance.  Further, creating diverse dataset and maintaining the ATL pipeline can prove to be a labor intensive.  In response to this variety of data models and the processing task and all of our data models,  numerous database management systems have emerged.  However, these database management systems in terms of their capabilities,  their performance, speed and scale make each of them unique.  But none of these systems is emerging as universal one-size-fits-all DBMS system,  as some systems provide excellent performance for some tasks,  or may perform poorly for others, or may not support them at all.  As an emerging trend is to use different database management systems side by side,  better exploit their performance, which is the goal of PolyStore System.  The main design principle of PolyStore Systems is to place each type of data in native data store  that is specifically designed for that specific data model  and mainly focus on enabling the query processing across the Petrogenous data stores  by allowing a user to use a variety of query languages and interfaces,  some synastic query data that resides in multiple vacant.  Some examples of an existing PolyStore Systems.  However, what are the unexplored opportunities in existing PolyStore System architecture?  They don't exploit possible data redundancy when the same data can be stored in several data stores,  some of which may support the query operations more efficiently than others.  They are unable to take the advantage of the present centralized views,  which can be available in one of several data stores with different data models.  Our vision is to allow application to transparently exploit the existence of the data store  in a set of heterogeneous data store in a PolyStore sitting,  a set of overlapping views, by abuse-based query writing,  and take the maximum advantages of these data stores' query processing capability.  This is not a classical view-space writing problem,  as user queries and views and rewritings are expressed across models and languages.  In a PolyStore sitting, the views may draw data from one or several data stores  of the same or different data models, and they are metallized yet again in distinct data models.  And the user queries can contain various sub-expressions,  each in its own query language.  As an example, we have a Mimic data set containing a patient data  who states in the Pet Israel Medical Center,  the data set consists of the patient information, which is so relational back-end,  and a patient's laptox result, and drug's information, which is so adjacent back-end,  a caregiver note, which need to be processed and followed by a surgeon.  And we have a query, which asks for female patients have been diagnosed  with coronary indices and abnormal laptox result.  We want to find the date and time for hospital admission and the dragoz of types,  addictive rescapillation.  Suppose that our disposal, we have a view one, which partially computes the query result,  joins the data in solar with the data in adjacent back-end,  and it's metallized in adjacent back-end.  And suppose we have a view two, which joins the data in adjacent back-end  with the data in the relational back-end, and it's metallized in relational back-end.  Evaluating the query using a polystore engine, which need to access the three back-ends  to answer the query, the query took about six minutes comparing  by evaluating the query using the views.  Yes, metallized views enhance its performance,  and also they can strongly improve performance when they are stored across data stores  by exploiting different strengths of each systems.  The technical question to be asked, how we can exploit the existing  of these cross-molder views, storage-situ-fetrogenes data stores,  given across smaller and language query, and a polystore setting.  In this talk first, I'll talk about our cross-molder views-based writing problem statement,  our approach, architecture overview, then our experimental evaluation,  finally our contributions.  Our cross-molder views-based writing problem statement is the following.  Given a cross-molder and language query, expressed over several data sets,  which are stored across data stores, and a set of metallized views,  which are expressed over these data sets, stored across data stores,  we want to find the equivalent to writing of the query, using the views,  which minimizes the cost estimation.  So we're dealing with the views-based query writing across arbitrary set of data models.  The views-based writing problem has been well studied in the literature.  However, most of the work had an assumption that the views data and the application data  are organized according to the same data model, which is mostly relational,  or they allow different data models for storing the views,  but they only consider XML as an application data model.  So the query and syncing approach in their setting is mainly focused  toward XML data model and query language.  However, this is different in our setting.  We want to have a unified approach, supporting any data model at the application level  and at the view level.  Our approach and the architecture overview.  The key requirement in our setting is to reason about queries and views,  involving multiple data models and query languages.  However, this comes with several challenges.  First, not every data model and query language comes with a views-based rewriting algorithm.  And even without such algorithm, none of these algorithms can be extended  to across model views-based writing solutions.  And any cross-modal views to the writing solution that we propose  need to be extendable to additional data model and query language.  Our approach to address these challenges is to reduce a variety of query languages  and data models into a single one for the purpose of reasoning about it,  which is the relational model with integrity constraints.  The architecture of our approach is the following.  We are giving different data models, cross-modal query and cross-modal views.  First, we encode the structure of various data models relationally  with the support of integrity constraints,  which capture the original feature or the key aspect of these data models.  We encode the cross-modal query into relational query,  and we encode the cross-modal views into a set of integrity relational constraints,  which capture the correspondence between the views input and its output.  Now our problem has been purely reduced to a relational setting with integrity constraints.  And the rewriting engine of choice is Chase and Backchase writing engine,  where we incorporated this engine and novel scale-up techniques  to make it scalable in a polystore setting  when we have a large number of generated constraints.  The output of the rewriting engine is a set of relational reformulation,  which will be decoded into an integration plan containing the sources subqueries.  Of course, different evaluation plans may lead to different performance.  We choose the rewriting of an evaluation plan with the minimum cost based on cost-based model.  First, I'll talk about how we encode the structure of various data models relationally  and I'll use JSON data model as an example.  We encode, we represent the organization of JSON data model using a set of virtual relations.  We call them virtual relational encoding of JSONs.  For example, the first relation here, collection name relation,  attach an ID for every element in the name JSON collection.  And the child's relation state that the value identified by the child's ID  is immediately listed within the value identified by the parent ID.  And the type indicates what is the type of the parent ID.  So, the parent ID could be a JSON object or it could be a JSON array.  And if the parent ID is a JSON object, then the key holds the field whose associated value is the child ID.  If the parent ID is a JSON array, then the key holds the index whose associated value is the child ID.  For example, here I have the JSON object in a MIME collection,  and here we encode relational MIME collection which attach an ID for every element in the collection.  And here in the child's relation, which is state that the result field is immediately listed  within the value identified by the parent IDP.  And the same will represent the value which is associated with the result field.  The JSON data model will not be stored relationally.  However, we only use these relations to encode the queries and the views, so we can reason about them.  For example, here I'm using the same JSON object,  and here we have the JSON query which navigates into this JSON object.  And here I'm showing you the corresponding relational encoding of this JSON query using our virtual JSON relations.  Also, we need to define a set of entity constraints which capture the original feature of this data model.  For example, the first constraint state that there is no JSON object that can have two distinct key value pairs having the same key.  And there is no JSON array that can have two distinct elements at the same position.  Here are the list of the data models in the query language that we currently supporting.  The relational data model with SQL query language, the JSON data model with SQL query language,  SQL query language with JSON support in PostgreSQL, and Spark SQL declarative query language,  as for key value data model, RIDIS APIs, and for XML, execuity query language.  Now, how about encoding the queries and the views?  The queries and the views are expressed using a QBT-XM syntax,  which is an integration language that we design to support queries over several data stores, each of its own data model, and query language.  QBT-XM follows the block-based design introduced in System R,  however, the main difference between the query block trees introduced in System R  and our QBT-XM syntax is that each block in QBT-XM is expressed in different data model and query language.  The QBT-XM consists of four where return clause, four clause introduce several query blocks, single by rotation,  for example, PR annotation mean PostgreSQL query language for this block,  PGA annotation mean PostgreSQL query language with JSON support for this block,  for where clause we are dealing with the scholar quality and return clause we specify how to construct a new data based on the variable bindings introduced in the four clause.  The user query will be encoded relationally using the set of virtual relation that it refers to.  The views will be encoded into an integrity constraint, for example, which shows how the view input are related to this output.  For example, here, I have the view definition in QBT-XM syntax, the right-hand side of the slide,  and on the right-hand side of the slide, I have the view encoded into integrity constraints.  The first block representing SQL query will be encoded into a conjunction of relational atoms.  The second block representing SQL JSON query will be encoded relationally using our JSON virtual relations.  In the conclusion of the constraints, we specify how a new JSON object can be constructed from the variable introduced in the four clause,  the variable introduced in the body of the query.  Now, as I mentioned earlier, the rewriting engine of choice is the chase and backjays writing engine,  where we have optimized this engine to make it scalable in the polystore settings.  The engine was mainly designed to work with very views and constraints.  However, in the case of polystore setting, we can have high number of relevant views,  the views that cannot be used to answer the query, and they can anchor an overhead to search for equivalently writing.  So we have applied the optimization technique to reduce this overhead,  and we mainly refer the audience to the paper for more details about the optimization.  Our new optimized version of the engine outperforms the standard one by at least two orders of magnitudes in case of polystore settings.  The output of the rewriting engine is a set of relational reformulation,  which will be decoded into an integration plan. Different evaluation plan may lead to different performance,  which was the rewriting of an evaluation plan with a minimum cost based on cost based model, how we can achieve that.  First, the relational rewriting of the query will be partitioned into a view level subqueries,  which will be decoded into the native syntax of the respective stores.  And the decoded rewriting then will be translated into a logical plan that push the leaves of blocks into the native stores  and applying the rest of the logical approaches integration engine.  So we chose the rewriting based on a cost based model, which we have adopted from a classical cost based optimization,  and through views and mediator systems.  Now, what about the aggregation, our virtual function calls an arithmetic operation?  We treat them under and we treat them as uninterpreted function samples,  but we add integrity constraints to capture their intended meaning.  For example, we add, for example, we modeled the add binary, the add operators as a relation with intending meaning that are equal x plus y,  which can be captured by constraints stating that add relation is functional, add relation is commutative, and add relation is associative.  As for the rewriting, we seek the rewriting under an interpreted function semantics,  mainly the rewriting that use the same function call with the same argument as the original query.  Our experimental evaluation.  So as for the hardware platform, we have used a machine with a CPU with 20 cars, 123 giga gram, and we set the power cache to 60 gigs for all the system that we are using for our whole polystore configurations,  Postgres, AsterixDB, MongoDB, and SparkSQL.  We have used the Mimic dataset of size 46 gig.  And the first experiment, we show the benefit that our approach can bring to a single model queries run in a single systems.  We have loaded the Mimic dataset in a native JSON stores, AsterixDB, Postgres JSON, SparkSQL, MongoDB.  We've designed and developed a benchmark based on Mimic dataset.  We refer the audience to the page for more details about the benchmark.  Among the queries that we have to enumerate the queries and the views, among the queries that we have enumerated,  we choose a 50 queries which consists of joins selections, at least two level navigation to JSON documents and arrays.  58% of the queries consist of full text search predicates, 60% of them not highly selected, 40% of them highly selected.  As for the views storage, we have metalyzed assets to views in Postgres, which can be represented relationally,  and they partially compute the query results.  And similarly, we have metalyzed assets to views in Postgres with JSON support.  We picked Postgres for storing the JSON views as we have experimentally evaluated,  shown that the Postgres eventually evaluate the join between the JSON dataset,  and it takes the view in solar, which is a dedicated engine for evaluating the full text search predicates.  Evaluating the query with the full text search predicates in SparkSQL and AsterixDB, these queries times out.  The reason in case of SparkSQL, it lacks supporting any type of indices and evaluating the full text search predicates  without the support of index given the size of the text that we have.  Also, the JSON array and this operator in case of SparkSQL, the operator is highly efficient.  Same observations apply to AsterixDB, which lacks the support of creating an index on an SID collection,  and the main overhead came from unisting the JSON array as well.  Postgres outperforms MongoDB since MongoDB lacks of supporting the join-reording optimization,  and it doesn't natively support inner join.  It must be simulated by lift out to join followed by a selection and a scan for non-values.  Also, the choice of the join algorithms different than Postgres SQL.  It is to be noted that none of these systems is capable to trans-transfer to exploit the existing of the views in a single model setting.  Our cross-modal view space writing approach improved the performance of these queries  by trans-transfer to exploit the cross-modal views stored in solar to evaluate the full text search predicates in the dedicated engine  and Postgres, which eventually evaluated the join between JSON views and relational views.  In this experiment, we show the benefit that our approach can bring to an existing polystore systems, BigDug from MIT and Tatooine Engine.  We have placed the structure part of the dataset in Postgres relational instance,  and the semi-structure part of the dataset in Postgres JSON instance, and the tick part of the data in solar.  By evaluating the queries which need to access the backend, we have 60% of the queries containing full text search predicates,  which are not highly selective.  We observed the overhead of such queries in BigDug is dominated by moving and ingesting the result of the queries during the query runtime in Postgres  to perform the join with other sub-queries.  However, the tween engine performs better as it computes the join in memory using the bind join mediator,  and it doesn't need to pay the intermediate storage cost during the query runtime.  So to elevate this overhead in addition to the views that had been materialized,  we've materialized a set of additional views which joined the data in solar with the data in Postgres and are materialized in Postgres JSON.  Our cross-moder-based writing approach improved the performance of these cross-moder queries  by finding the re-writing using the pre-materialized views stored in solar, stored in a Postgres relational instance,  and Postgres JSON instance.  This figure shows the distribution of re-writing over the set of queries that we have,  and the time spent searching for re-writing is a small fraction of the query execution time.  Our contributions, our approach improved the performance in natural scenarios for both cross-moder and single-moder queries.  We have shown that our cross-moder views-based writing approach is portable across polystore engines,  and we designed a reduction from multi-modal views-based re-writing to relational re-writing under constraints.  We optimized the state-of-the-art algorithm to scale in a polystore setting.  Thank you.
_NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_0_131.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_132_239.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_240_851.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_852_2423.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_2424_3875.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_3876_5723.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_5724_6107.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_6108_7895.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_7896_8699.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_8700_10475.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_10476_14663.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_14664_16439.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_16440_17363.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_17364_20603.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_20604_20711.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_20712_20783.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_20784_21611.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_21612_24179.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_24180_24239.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_24240_24455.png _NEU_Alotaibi_Bursztyn_Deutsch_Manolescu_Zampetakis_24456_26574.png
This work is a joint project with Damian Buschentan, Aline Deutsch, Iwana Monalisco and Stamata Zamtikes. Modern application often need to manage and analyze widely diverse dataset that span multiple data models. The data can be structured, complex structure like graphs or even fully structure like logs and text. Constradating disparate data to fit into a single data model may degrade application performance. Further, creating diverse dataset and maintaining the ATL pipeline can prove to be a labor intensive. In response to this variety of data models and the processing task and all of our data models, numerous database management systems have emerged. However, these database management systems in terms of their capabilities, their performance, speed and scale make each of them unique. But none of these systems is emerging as universal one-size-fits-all DBMS system, as some systems provide excellent performance for some tasks, or may perform poorly for others, or may not support them at all. As an emerging trend is to use different database management systems side by side, better exploit their performance, which is the goal of PolyStore System. The main design principle of PolyStore Systems is to place each type of data in native data store that is specifically designed for that specific data model and mainly focus on enabling the query processing across the Petrogenous data stores by allowing a user to use a variety of query languages and interfaces, some synastic query data that resides in multiple vacant. Some examples of an existing PolyStore Systems. However, what are the unexplored opportunities in existing PolyStore System architecture? They don't exploit possible data redundancy when the same data can be stored in several data stores, some of which may support the query operations more efficiently than others. They are unable to take the advantage of the present centralized views, which can be available in one of several data stores with different data models. Our vision is to allow application to transparently exploit the existence of the data store in a set of heterogeneous data store in a PolyStore sitting, a set of overlapping views, by abuse-based query writing, and take the maximum advantages of these data stores' query processing capability. This is not a classical view-space writing problem, as user queries and views and rewritings are expressed across models and languages. In a PolyStore sitting, the views may draw data from one or several data stores of the same or different data models, and they are metallized yet again in distinct data models. And the user queries can contain various sub-expressions, each in its own query language. As an example, we have a Mimic data set containing a patient data who states in the Pet Israel Medical Center, the data set consists of the patient information, which is so relational back-end, and a patient's laptox result, and drug's information, which is so adjacent back-end, a caregiver note, which need to be processed and followed by a surgeon. And we have a query, which asks for female patients have been diagnosed with coronary indices and abnormal laptox result. We want to find the date and time for hospital admission and the dragoz of types, addictive rescapillation. Suppose that our disposal, we have a view one, which partially computes the query result, joins the data in solar with the data in adjacent back-end, and it's metallized in adjacent back-end. And suppose we have a view two, which joins the data in adjacent back-end with the data in the relational back-end, and it's metallized in relational back-end. Evaluating the query using a polystore engine, which need to access the three back-ends to answer the query, the query took about six minutes comparing by evaluating the query using the views. Yes, metallized views enhance its performance, and also they can strongly improve performance when they are stored across data stores by exploiting different strengths of each systems. The technical question to be asked, how we can exploit the existing of these cross-molder views, storage-situ-fetrogenes data stores, given across smaller and language query, and a polystore setting. In this talk first, I'll talk about our cross-molder views-based writing problem statement, our approach, architecture overview, then our experimental evaluation, finally our contributions. Our cross-molder views-based writing problem statement is the following. Given a cross-molder and language query, expressed over several data sets, which are stored across data stores, and a set of metallized views, which are expressed over these data sets, stored across data stores, we want to find the equivalent to writing of the query, using the views, which minimizes the cost estimation. So we're dealing with the views-based query writing across arbitrary set of data models. The views-based writing problem has been well studied in the literature. However, most of the work had an assumption that the views data and the application data are organized according to the same data model, which is mostly relational, or they allow different data models for storing the views, but they only consider XML as an application data model. So the query and syncing approach in their setting is mainly focused toward XML data model and query language. However, this is different in our setting. We want to have a unified approach, supporting any data model at the application level and at the view level. Our approach and the architecture overview. The key requirement in our setting is to reason about queries and views, involving multiple data models and query languages. However, this comes with several challenges. First, not every data model and query language comes with a views-based rewriting algorithm. And even without such algorithm, none of these algorithms can be extended to across model views-based writing solutions. And any cross-modal views to the writing solution that we propose need to be extendable to additional data model and query language. Our approach to address these challenges is to reduce a variety of query languages and data models into a single one for the purpose of reasoning about it, which is the relational model with integrity constraints. The architecture of our approach is the following. We are giving different data models, cross-modal query and cross-modal views. First, we encode the structure of various data models relationally with the support of integrity constraints, which capture the original feature or the key aspect of these data models. We encode the cross-modal query into relational query, and we encode the cross-modal views into a set of integrity relational constraints, which capture the correspondence between the views input and its output. Now our problem has been purely reduced to a relational setting with integrity constraints. And the rewriting engine of choice is Chase and Backchase writing engine, where we incorporated this engine and novel scale-up techniques to make it scalable in a polystore setting when we have a large number of generated constraints. The output of the rewriting engine is a set of relational reformulation, which will be decoded into an integration plan containing the sources subqueries. Of course, different evaluation plans may lead to different performance. We choose the rewriting of an evaluation plan with the minimum cost based on cost-based model. First, I'll talk about how we encode the structure of various data models relationally and I'll use JSON data model as an example. We encode, we represent the organization of JSON data model using a set of virtual relations. We call them virtual relational encoding of JSONs. For example, the first relation here, collection name relation, attach an ID for every element in the name JSON collection. And the child's relation state that the value identified by the child's ID is immediately listed within the value identified by the parent ID. And the type indicates what is the type of the parent ID. So, the parent ID could be a JSON object or it could be a JSON array. And if the parent ID is a JSON object, then the key holds the field whose associated value is the child ID. If the parent ID is a JSON array, then the key holds the index whose associated value is the child ID. For example, here I have the JSON object in a MIME collection, and here we encode relational MIME collection which attach an ID for every element in the collection. And here in the child's relation, which is state that the result field is immediately listed within the value identified by the parent IDP. And the same will represent the value which is associated with the result field. The JSON data model will not be stored relationally. However, we only use these relations to encode the queries and the views, so we can reason about them. For example, here I'm using the same JSON object, and here we have the JSON query which navigates into this JSON object. And here I'm showing you the corresponding relational encoding of this JSON query using our virtual JSON relations. Also, we need to define a set of entity constraints which capture the original feature of this data model. For example, the first constraint state that there is no JSON object that can have two distinct key value pairs having the same key. And there is no JSON array that can have two distinct elements at the same position. Here are the list of the data models in the query language that we currently supporting. The relational data model with SQL query language, the JSON data model with SQL query language, SQL query language with JSON support in PostgreSQL, and Spark SQL declarative query language, as for key value data model, RIDIS APIs, and for XML, execuity query language. Now, how about encoding the queries and the views? The queries and the views are expressed using a QBT-XM syntax, which is an integration language that we design to support queries over several data stores, each of its own data model, and query language. QBT-XM follows the block-based design introduced in System R, however, the main difference between the query block trees introduced in System R and our QBT-XM syntax is that each block in QBT-XM is expressed in different data model and query language. The QBT-XM consists of four where return clause, four clause introduce several query blocks, single by rotation, for example, PR annotation mean PostgreSQL query language for this block, PGA annotation mean PostgreSQL query language with JSON support for this block, for where clause we are dealing with the scholar quality and return clause we specify how to construct a new data based on the variable bindings introduced in the four clause. The user query will be encoded relationally using the set of virtual relation that it refers to. The views will be encoded into an integrity constraint, for example, which shows how the view input are related to this output. For example, here, I have the view definition in QBT-XM syntax, the right-hand side of the slide, and on the right-hand side of the slide, I have the view encoded into integrity constraints. The first block representing SQL query will be encoded into a conjunction of relational atoms. The second block representing SQL JSON query will be encoded relationally using our JSON virtual relations. In the conclusion of the constraints, we specify how a new JSON object can be constructed from the variable introduced in the four clause, the variable introduced in the body of the query. Now, as I mentioned earlier, the rewriting engine of choice is the chase and backjays writing engine, where we have optimized this engine to make it scalable in the polystore settings. The engine was mainly designed to work with very views and constraints. However, in the case of polystore setting, we can have high number of relevant views, the views that cannot be used to answer the query, and they can anchor an overhead to search for equivalently writing. So we have applied the optimization technique to reduce this overhead, and we mainly refer the audience to the paper for more details about the optimization. Our new optimized version of the engine outperforms the standard one by at least two orders of magnitudes in case of polystore settings. The output of the rewriting engine is a set of relational reformulation, which will be decoded into an integration plan. Different evaluation plan may lead to different performance, which was the rewriting of an evaluation plan with a minimum cost based on cost based model, how we can achieve that. First, the relational rewriting of the query will be partitioned into a view level subqueries, which will be decoded into the native syntax of the respective stores. And the decoded rewriting then will be translated into a logical plan that push the leaves of blocks into the native stores and applying the rest of the logical approaches integration engine. So we chose the rewriting based on a cost based model, which we have adopted from a classical cost based optimization, and through views and mediator systems. Now, what about the aggregation, our virtual function calls an arithmetic operation? We treat them under and we treat them as uninterpreted function samples, but we add integrity constraints to capture their intended meaning. For example, we add, for example, we modeled the add binary, the add operators as a relation with intending meaning that are equal x plus y, which can be captured by constraints stating that add relation is functional, add relation is commutative, and add relation is associative. As for the rewriting, we seek the rewriting under an interpreted function semantics, mainly the rewriting that use the same function call with the same argument as the original query. Our experimental evaluation. So as for the hardware platform, we have used a machine with a CPU with 20 cars, 123 giga gram, and we set the power cache to 60 gigs for all the system that we are using for our whole polystore configurations, Postgres, AsterixDB, MongoDB, and SparkSQL. We have used the Mimic dataset of size 46 gig. And the first experiment, we show the benefit that our approach can bring to a single model queries run in a single systems. We have loaded the Mimic dataset in a native JSON stores, AsterixDB, Postgres JSON, SparkSQL, MongoDB. We've designed and developed a benchmark based on Mimic dataset. We refer the audience to the page for more details about the benchmark. Among the queries that we have to enumerate the queries and the views, among the queries that we have enumerated, we choose a 50 queries which consists of joins selections, at least two level navigation to JSON documents and arrays. 58% of the queries consist of full text search predicates, 60% of them not highly selected, 40% of them highly selected. As for the views storage, we have metalyzed assets to views in Postgres, which can be represented relationally, and they partially compute the query results. And similarly, we have metalyzed assets to views in Postgres with JSON support. We picked Postgres for storing the JSON views as we have experimentally evaluated, shown that the Postgres eventually evaluate the join between the JSON dataset, and it takes the view in solar, which is a dedicated engine for evaluating the full text search predicates. Evaluating the query with the full text search predicates in SparkSQL and AsterixDB, these queries times out. The reason in case of SparkSQL, it lacks supporting any type of indices and evaluating the full text search predicates without the support of index given the size of the text that we have. Also, the JSON array and this operator in case of SparkSQL, the operator is highly efficient. Same observations apply to AsterixDB, which lacks the support of creating an index on an SID collection, and the main overhead came from unisting the JSON array as well. Postgres outperforms MongoDB since MongoDB lacks of supporting the join-reording optimization, and it doesn't natively support inner join. It must be simulated by lift out to join followed by a selection and a scan for non-values. Also, the choice of the join algorithms different than Postgres SQL. It is to be noted that none of these systems is capable to trans-transfer to exploit the existing of the views in a single model setting. Our cross-modal view space writing approach improved the performance of these queries by trans-transfer to exploit the cross-modal views stored in solar to evaluate the full text search predicates in the dedicated engine and Postgres, which eventually evaluated the join between JSON views and relational views. In this experiment, we show the benefit that our approach can bring to an existing polystore systems, BigDug from MIT and Tatooine Engine. We have placed the structure part of the dataset in Postgres relational instance, and the semi-structure part of the dataset in Postgres JSON instance, and the tick part of the data in solar. By evaluating the queries which need to access the backend, we have 60% of the queries containing full text search predicates, which are not highly selective. We observed the overhead of such queries in BigDug is dominated by moving and ingesting the result of the queries during the query runtime in Postgres to perform the join with other sub-queries. However, the tween engine performs better as it computes the join in memory using the bind join mediator, and it doesn't need to pay the intermediate storage cost during the query runtime. So to elevate this overhead in addition to the views that had been materialized, we've materialized a set of additional views which joined the data in solar with the data in Postgres and are materialized in Postgres JSON. Our cross-moder-based writing approach improved the performance of these cross-moder queries by finding the re-writing using the pre-materialized views stored in solar, stored in a Postgres relational instance, and Postgres JSON instance. This figure shows the distribution of re-writing over the set of queries that we have, and the time spent searching for re-writing is a small fraction of the query execution time. Our contributions, our approach improved the performance in natural scenarios for both cross-moder and single-moder queries. We have shown that our cross-moder views-based writing approach is portable across polystore engines, and we designed a reduction from multi-modal views-based re-writing to relational re-writing under constraints. We optimized the state-of-the-art algorithm to scale in a polystore setting. Thank you.
structured, complex structure like graphs or even fully structure like logs and text. Constradating processing task and all of our data models, systems in terms of their capabilities, their systems provide excellent performance for some don't exploit possible data redundancy when the same data can be stored in several data stores, some of which may support the query operations take the advantage of the present centralized views, which can be available in one of several data stores with different data models. Our vision is to allow application to transparently of heterogeneous data store in a PolyStore capability. This is not a classical view-space same or different data models, and they are metallized yet again in distinct data models. And stores by exploiting different strengths of each query into relational query, and we encode the relational constraints, which capture the encode the structure of various data models based on the variable bindings introduced in the constructed from the variable introduced in the be used to answer the query, and they can anchor semantics, mainly the rewriting that use the same and they partially compute the query results. And benefit that our approach can bring to an part of the data in solar. By evaluating the under constraints. We optimized the polystore setting. Thank you.