检索结果-内蒙古大学图书馆

Exploiting Shared Sub-Expression and Materialized View Reuse for multi-query optimization

INFORMATION SYSTEMS FRONTIERS 2024年 1-16页

作者： Gurumurthy, Bala Bidarkar, Vasudev Raghavendra Broneske, David Pionteck, Thilo Saake, Gunter Otto Von Guericke Univ Magdeburg Germany German Ctr Higher Educ Res & Sci Studies Hannover Germany

querying in isolation lacks the potential of reusing intermediate results, which ends up wasting computational resources. multi-query optimization (MQO) addresses this challenge by devising a shared execution strategy across queries, with two generally used strategies: batched or cached. These strategies are shown to improve performance, but hardly any study explores the combination of both. In this work we explore such a hybrid MQO, combining batching (Shared Sub-Expression) and caching (Materialized View Reuse) techniques. Our hybrid-MQO system merges batched query results as well as caches the intermediate results, thereby any new query is given a path within the previous plan as well as reusing the results. Since caching is a key component for improving performance, we measure the impact of common caching techniques such as FIFO, LRU, MRU and LFU. Our results show LRU to be the optimal for our usecase, which we use in our subsequent evaluations. To study the influence of batching, we vary the factor - derivability - which represents the similarity of the results within a query batch. Similarly, we vary the cache sizes to study the influence of caching. Moreover, we also study the role of different database operators in the performance of our hybrid system. The results suggest that, depending on the individual operators, our hybrid method gains a speed-up between 4x to a slowdown of 2x from using MQO techniques in isolation. Furthermore, our results show that workloads with a generously sized cache that contain similar queries benefit from using our hybrid method, with an observed speed-up of 2x over sequential execution in the best case.

关键词： multi-query optimization Batched query execution Materialized view reuse Caching policies MQO

来源：评论

学校读者我要写书评

暂无评论

Continuous multi-query optimization for subgraph matching over dynamic graphs

引用

SEMANTIC WEB 2022年第4期13卷 601-622页

作者： Wang, Xi Zhang, Qianzhen Guo, Deke Zhao, Xiang Univ Def Technol Sci & Technol Informat Syst Engn Lab Changsha Peoples R China Tianjin Univ Coll Intelligence & Comp Tianjin Key Lab Adv Networking Tank Tianjin Peoples R China

There is a growing need to perform real-time analytics on dynamic graphs in order to deliver the values of big data to users. An important problem from such applications is continuously identifying and monitoring critical patterns when fine-grained updates at a high velocity occur on the graphs. A lot of efforts have been made to develop practical solutions for these problems. Despite the efforts, existing algorithms showed limited running time and scalability in dealing with large and/or many graphs. In this paper, we study the problem of continuous multi-query optimization for subgraph matching over dynamic graph data. (1) We propose annotated query graph, which is obtained by merging the multi-queries into one. (2) Based on the annotated query, we employ a concise auxiliary data structure to represent partial solutions in a compact form. (3) In addition, we propose an efficient maintenance strategy to detect the affected queries for each update and report corresponding matches in one pass. (4) Extensive experiments over real-life and synthetic datasets verify the effectiveness and efficiency of our approach and confirm a two orders of magnitude improvement of the proposed solution.

关键词： multi-query optimization annotated query graph incremental maintenance strategy dynamic graph

来源：评论

学校读者我要写书评

暂无评论

What Happens When Two multi-query optimization Paradigms Combine? A Hybrid Shared Sub-Expression (SSE) and Materialized View Reuse (MVR) Study 27th

What Happens When Two Multi-Query Optimization Paradigms Com...

引用

27th European Conference on Advances in Databases and Information Systems (ADBIS)

ISBN: (纸本)9783031429132;9783031429149

querying in isolation lacks the potential of reusing results, that ends up wasting computational resources. multi-query optimization (MQO) addresses this challenge by devising a shared execution strategy across queries, with two generally used strategies: batched or cached. These strategies are shown to improve performance, but hardly any study explores the combination of both. In this work we explore such a hybrid MQO, combining batching (Shared Sub-Expression) and caching (Materialized View Reuse) techniques. Our hybrid-MQO system merges batched query results as well as caches the intermediate results, thereby any new query is given a path within the previous plan as well as reusing the results. To study the influence of batching, we vary the factor - derivability which represents the similarity of the results within a query batch. Similarly, we vary the cache sizes to study the influence of caching. Moreover, we also study the role of different database operators in the performance of our hybrid system. The results suggest that, depending on the individual operators, our hybrid method gains a speed-up between 4x to a slowdown of 2x from using MQO techniques in isolation. Furthermore, our results show that workloads with a generously sized cache that contain similar queries benefit from using our hybrid method, with an observed speed-up of 2x over sequential execution in the best case.

关键词： multi-query optimization batched query execution materialized view reuse

来源：评论

学校读者我要写书评

暂无评论

multi-query optimization on RSS Feeds

引用

JOURNAL ON DATA SEMANTICS 2018年第1期7卷 47-64页

作者： Getahun, Fekade Chbeir, Richard Univ Addis Ababa Dept Comp Sci Addis Ababa 1180 Ethiopia Univ Pau & Pays Adour LIUPPA F-64400 Anglet France

RSS feeds are text-content rich, semantically heterogeneous, and contain dynamic XML elements streamed in asynchronous and pull strategies. Hence, for efficient retrieval of RSS feeds, semantic-aware querying operators have been proposed in the literature (Getahun and Chbeir in Inf Sci 237(237):313-342, 2013). However, it is commonly admitted that the use of semantic information would improve, on one hand, the relevance of query result but, on the other hand, at the cost of degrading the efficiency and the performance of the system. To benefit from query execution on semantic information while keeping the efficiency of the system, we propose here a multi-query optimization approach for semantic RSS feed queries. Our approach processes queries by examining the semantic relationship between them and their corresponding windows. It generates a multi-query chain for queries using their window relations for faster execution at runtime. In addition, we propose an operator called quickDrop for semantic load shedding to gracefully decrease irrelevant data load. To validate the proposed approach, we developed a prototype and conducted a set of experiments. The obtained results show that the use of our approach significantly improves the performance of the system.

关键词： Semantic RSS feed query multi-query optimization NAT MQE chain generator Window relationship QuickDrop operator

来源：评论

学校读者我要写书评

暂无评论

RDF multi-query optimization Algorithm for query Rewriting Using Common Subgraphs 19

RDF Multi-query Optimization Algorithm for Query Rewriting U...

引用

3rd International Conference on Computer Science and Application Engineering (CSAE)

作者： Wang, Manzi Fu, Haidong Xu, Fangfang Wuhan Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430065 Peoples R China

ISBN: (纸本)9781450362948

In the current trend of rapid development of big data, there are frequent application scenarios of high concurrent query processing on RDF data sets. The multi-query optimization scheme for solving concurrent queries needs to provide a global approximate optimal solution for the query set composed of a set of queries, so as to minimize the overall time cost of the query set. Under the premise of accelerating statistics by RDF storage index and narrowing the scope of semantic pruning, firstly, simplified multiple queries are converted into connection graphs, and then all queries are clustered and grouped. In each group, all common subgraphs of connection graphs are iteratively searched and mapping tables are established. Then, the common subgraph is arranged in descending order by the number of vertices to construct the query rewriting scheme. Finally, for all the rewritten queries, the dynamic programming algorithm based on selection rate estimation is used for secondary optimization. On the one hand, the common subgraph is used to rewrite the query to reduce the number of queries, so as to reduce the cost through the reusable common result set. On the other hand, because of the establishment of RDF storage index, the selection rate can be estimated quickly, and the rewritten queries can be optimized again to improve the overall query efficiency. The experimental results show that the proposed algorithm has better query performance than the existing query schemes, especially when the RDF dataset is large, the number of queries in the query set is large, and the query statements are complex, the multi-query optimization method in this paper works better.

关键词： Common Subgraph query Rewrite Selection Rate Estimation multi-query optimization

来源：评论

学校读者我要写书评

暂无评论

multi-query optimization in Wide-Area Streaming Analytics

Multi-Query Optimization in Wide-Area Streaming Analytics

引用

ACM Symposium on Cloud Computing (SoCC)

作者： Jonathan, Albert Chandra, Abhishek Weissman, Jon Univ Minnesota Twin Cities Minneapolis MN 55455 USA

ISBN: (纸本)9781450360111

Wide-area data analytics has gained much attention in recent years due to the increasing need for analyzing data that are geographically distributed. Many of such queries often require real-time analysis on data streams that are continuously being generated across multiple locations. Yet, analyzing these geo-distributed data streams in a timely manner is very challenging due to the highly heterogeneous and limited bandwidth availability of the wide-area network (WAN). This paper examines the opportunity of applying multi-query optimization in the context of wide-area streaming analytics, with the goal of utilizing WAN bandwidth efficiently while achieving high throughput and low latency execution. Our approach is based on the insight that many streaming analytics queries often exhibit common executions, whether in consuming a common set of input data or performing the same data processing. In this work, we study different types of sharing opportunities and propose a practical online algorithm that allows streaming analytics queries to share their common executions incrementally. We further address the importance of WAN awareness in applying multi-query optimization. Without WAN awareness, sharing executions in a wide-area environment may lead to performance degradation. We have implemented our WAN-aware multi-query optimization in a prototype implementation based on Apache Flink. Experimental evaluation using Twitter traces on a real wide-area system deployment across geo-distributed EC2 data centers shows that our technique is able to achieve 21% higher throughput while saving WAN bandwidth consumption by 33% compared to a WAN-aware, sharing-agnostic system.

关键词： Geo-distributed systems stream processing systems multi-query optimization execution sharing

来源：评论

学校读者我要写书评

暂无评论

Exploiting coarse-grained reused-based opportunities in Big Data multi-query optimization

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2018年 26卷 432-452页

作者： Sahal, Radhya Khafagy, Mohamed H. Omara, Fatma A. Cairo Univ Fac Comp & Informat Dept Comp Sci Giza Egypt Cairo Univ Fac Comp & Informat Giza Egypt Fayoum Univ Fac Comp & Informat Dept Comp Sci Faiyum Egypt

multi-query optimization in Big Data becomes a promising research direction due to the popularity of massive data analytical systems (e.g., MapReduce and Flink). The multi-query is translated into jobs. These jobs are routinely submitted with similar tasks to the underling Big Data analytical systems. These similar tasks are considered complicated and computation overhead. Therefore, there are some existing techniques that have been proposed for exploiting sharing tasks in Big Data multi-query optimization (e.g., MRShare and Relaxed MRShare). These techniques are heavily tailored relaxed optimizing factors of fine-grained reused-based opportunities. In accordance with Big Data multi-query optimization, the existing fine-grained techniques are only concerned with equal tuples size and uniform data distribution. These issues are not applicable to the real-world distributed applications which depend on coarse-grained reused-based opportunities, such as non-equal tuples size and non-uniform data distribution. These two issues receive more-attention in Big Data multi-query optimization, to minimize the data read from or written back to Big Data infrastructures (e.g., Hadoop). In this paper, multi-query optimization using Tuple Size and Histogram (MOTH) system has been proposed to consider the granularity of the reused-based opportunities. The proposed MOTH system exploits the coarse-grained of the fully and partially reused-based opportunities among queries with considering non-equal tuples size and non-uniform data distribution to avoid repeated computations. According to the proposed MOTH system, a combined technique has been introduced for estimating the coarse-grained reused-based opportunities horizontally and vertically. The horizontal estimation of non-equal tuples size has been done by extracting metadata in column-level, while the vertical estimation of non-uniform data distribution is concerned with using pre-computed histogram in row-level. In addition, the MO

关键词： Big Data multi-query optimization Coarse-grained Sharing opportunity Reused-based

来源：评论

学校读者我要写书评

暂无评论

SPARQL multi-query optimization 17

SPARQL Multi-Query Optimization

引用

17th IEEE International Conference on Trust, Security and Privacy in Computing and Communications (IEEE TrustCom) / 12th IEEE International Conference on Big Data Science and Engineering (IEEE BigDataSE)

作者： Chen, Jiaqi Zhang, Fan Zou, Lei Peking Univ Inst Comp Sci & Technol Beijing Peoples R China

ISBN: (纸本)9781538643877

With RDF knowledge base and SPARQL have been widely used, the performance of query engine gets more attention. In the actual complicated application scenarios, query engine may receive intensive query requests with similar structure in a short time, as usual these queries will be evaluated independently. multi-query optimization evaluation approach can mine feasible common query patterns deeply, choose preferable combination of common query patterns according to the cost model, and reduce the total time consumption by taking advantage of the common query pattern evaluation results. The experiments on LUBM dataset indicate that the total evaluation time of multi-query optimization evaluation approach is shorter than sequential evaluation approach and making the throughput of query engine improve.

关键词： rdf sparql multi-query optimization common query pattern mining and selecting

来源：评论

学校读者我要写书评

暂无评论

query grouping-based multi-query optimization framework for interactive SQL query engines on Hadoop

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2018年第19期30卷

作者： Chen, Ling Lin, Yan Wang, Jingchang Huang, Heqing Chen, Donghui Wu, Yong Zhejiang Univ Coll Comp Sci & Technol Hangzhou 310027 Zhejiang Peoples R China Alibaba Zhejiang Univ Joint Inst Frontier Technol Hangzhou 310027 Zhejiang Peoples R China Zhejiang Hongcheng Comp Syst Co Ltd Hangzhou 310053 Zhejiang Peoples R China

In the past few years, executing high-concurrency queries with interactive SQL query engines on Hadoop has become an important activity for many organizations. However, these systems do not adopt multi-query optimization (MQO) to accelerate the process. There are two major concerns. Firstly, traditional MQO researches assume that multiple queries have high similarity. However, these systems usually serve a variety of applications. Although queries from the same application have high similarity, queries from different applications may have low similarity, so using traditional MQO will be inefficient and time consuming. Secondly, integrating MQO may lead to lots of system modifications. To integrate MQO into interactive SQL query engines on Hadoop efficiently, a query grouping-based MQO framework is proposed. A lightweight mechanism is used to represent SQL queries, on which a grouping method is exploited to speed up the optimization process. A cost model is integrated to estimate the execution cost of interactive SQL query engines on Hadoop. By using the proposed framework, we modify Impala system to support MQO, and the experimental results on TPC-DS show significant performance improvements.

关键词： grouping method Impala system multi-query optimization

来源：评论

学校读者我要写书评

暂无评论

Efficient and Provable multi-query optimization 17

Efficient and Provable Multi-Query Optimization

引用

36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Kathuria, Tarun Sudarshan, S. Microsoft Res Bengaluru Karnataka India Indian Inst Technol Bombay Maharashtra India

ISBN: (纸本)9781450341981

Complex queries for massive data analysis jobs have become increasingly commonplace. Many such queries contain common subexpressions, either within a single query or among multiple queries submitted as a batch. Conventional query optimizers do not exploit these subexpressions and produce sub-optimal plans. The problem of multi-query optimization (MQO) is to generate an optimal combined evaluation plan by computing common subexpressions once and reusing them. Exhaustive algorithms for MQO explore an O(n(n)) search space. Thus, this problem has primarily been tackled using various heuristic algorithms, without providing any theoretical guarantees on the quality of their solution. In this paper, instead of the conventional cost minimization problem, we treat the problem as maximizing a linear transformation of the cost function. We propose a greedy algorithm for this transformed formulation of the problem, which under weak, intuitive assumptions, provides an approximation factor guarantee for this formulation. We go on to show that this factor is optimal, unless P = NP. Another noteworthy point about our algorithm is that it can be easily incorporated into existing transformation-based optimizers. We finally propose optimizations which can be used to improve the efficiency of our algorithm.

关键词： Approximation algorithms hardness of approximation multi-query optimization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：