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

Performance analysis of "Groupby-After-Join" query processing in parallel database systems

INFORMATION SCIENCES 2004年第1-4期168卷 25-50页

作者： Taniar, D Tan, RBN Leung, CHC Liu, KH Monash Univ Sch Business Syst Clayton Vic 3800 Australia Victoria Univ MCMC Sch Comp Sci & Math Melbourne Vic 8001 Australia Blueridge Syst Ocean NJ 07712 USA

Queries containing aggregate functions often combine multiple tables through join operations. This query is subsequently called "Groupby-Join". There is a special category of this query whereby the group-by operation can only be performed after the join operation. This is known as "Groupby-After-Join" queries-the focus of this paper. In parallel processing of such queries, it must be decided which attribute is used as a partitioning attribute, particularly join attribute or group-by attribute. Based on the partitioning attribute, two parallel processing methods, namely join partition method (JPM) and aggregate partition method (APM) are discussed. The behaviours of these parallelization methods are described in terms of cost models. Experiments are performed based on simulations. The simulation results show that the aggregate partition method performs better than the join partition method. (C) 2004 Elsevier Inc. All rights reserved.

关键词： Groupby queries Groupby-Join queries parallel query processing parallel query optimization parallel databases performance analysis

来源：评论

学校读者我要写书评

暂无评论

DATA-FLOW query EXECUTION IN A parallel MAIN-MEMORY ENVIRONMENT

引用

DISTRIBUTED AND parallel DATABASES 1993年第1期1卷 103-128页

作者： WILSCHUT, AN APERS, PMG 1. University of Twente P.O. Box 217 7500 AE Enschede The Netherlands2. University of Twente P.O. Box 217 7500 AE Enschede The Netherlands

In this paper, the performance and characteristics of the execution of various join-trees on a parallel DBMS are studied. The results of this study are a step into the direction of the design of a query optimization strategy that is fit for parallel execution of complex queries. Among others, synchronization issues are identified to limit the performance gain from parallelism. A new hash-join algorithm is introduced that has fewer synchronization constraints than the known hash-join algorithms. Also, the behavior of individual join operations in a join-tree is studied in a simulation experiment. The results show that the introduced Pipelining hash-join algorithm yields a better performance for multi-join queries. The format of the optimal join-tree appears to depend on the size of the operands of the join: A multi-join between small operands performs best with a bushy schedule;larger operands are better off with a linear schedule. The results from the simulation study are confirmed with an analytic model for dataflow query execution.

关键词： parallel query processing MULTI-JOIN QUERIES SIMULATION ANALYTICAL MODELING

来源：评论

学校读者我要写书评

暂无评论

Performance analysis of parallelization models for path expression queries

引用

INFORMATION SCIENCES 1999年第1-2期117卷 107-142页

作者： Taniar, D Rahayu, JW RMIT Univ Dept Comp Sci Melbourne Vic Australia La Trobe Univ Sch Comp Sci & Comp Engn Bundoora Vic 3083 Australia

In this paper, parallelization models for path expressions queries are studied. Path expression queries involve multiple classes along aggregation/association hierarchies. parallelization models for path expression queries are "inter-object parallelization" and "inter-class parallelization". Inter-object parallelization exploits the associativity within complex objects, whereas inter-class parallelization imposes upon process independence. The behaviours of these parallelization models are described in terms of analytical models. Performance evaluation is also performed to confirm the results from the quantitative analysis. (C) 1999 Elsevier Science Inc. All rights reserved.

关键词： path expression queries parallel query processing inter-object parallelization inter-class parallelization parallel object-oriented databases

来源：评论

学校读者我要写书评

暂无评论

Evaluating top-k queries over web-accessible databases

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2004年第2期29卷 319-362页

作者： Marian, A Bruno, N Gravano, L Columbia Univ Dept Comp Sci 1214 Amsterdam Ave New York NY 10027 USA Microsoft Res Redmond WA USA

A query to a web search engine usually consists of a list of keywords, to which the search engine responds with the best or "top" k pages for the query. This top-k query model is prevalent over multimedia collections in general, but also over plain relational data for certain applications. For example, consider a relation with information on available restaurants, including their location, price range for one diner, and overall food rating. A user who queries such a relation might simply specify the user's location and target price range, and expect in return the best 10 restaurants in terms of some combination of proximity to the user, closeness of match to the target price range, and overall food rating. processing top-k queries efficiently is challenging for a number of reasons. One critical such reason is that, in many web applications, the relation attributes might not be available other than through external web-accessible form interfaces, which we will have to query repeatedly for a potentially large set of candidate objects. In this article, we study how to process top-k queries efficiently in this setting, where the attributes for which users specify target values might be handled by external, autonomous sources with a variety of access interfaces. We present a sequential algorithm for processing such queries, but observe that any sequential top-k query processing strategy is bound to require unnecessarily long query processing times, since web accesses exhibit high and variable latency. Fortunately, web sources can be probed in parallel, and each source can typically process concurrent requests, although sources may impose some restrictions on the type and number of probes that they are willing to accept. We adapt our sequential query processing technique and introduce an efficient algorithm that maximizes source-access parallelism to minimize query response time, while satisfying source-access constraints. We evaluate our techniques experimentally using b

关键词： algorithms measurement performance parallel query processing query optimization top-k query processing web databases

来源：评论

学校读者我要写书评

暂无评论

The impact of load balancing to object-oriented query execution scheduling in parallel machine environment

引用

INFORMATION SCIENCES 2003年第1-4期157卷 33-71页

作者： Taniar, D Leung, CHC Monash Univ Sch Business Syst Clayton Vic 3800 Australia Victoria Univ Technol Sch Commun & Informat Melbourne Vic 8001 Australia

Skewness has been one of the major problems not only in parallel relational database systems, but also in parallel object-oriented database systems. To improve performance of object-oriented query processing, a careful and intelligent skew handling for load balancing must be established. Depending on the parallel machine environment, whether it is a shared-memory or a shared-nothing architecture, load balancing can be achieved through "physical" or "logical" data re-distribution. It is not the aim of this paper to propose or to investigate skew handling methods, but rather to analyze the impact of load balancing to query execution scheduling strategies. Our analysis shows that when load balancing is achieved, "serial" execution scheduling is preferable to "parallel" execution scheduling strategy. In other words, allocating full resources to a sub-query seems to be better than dividing resources to multiple sub-queries. (C) 2003 Elsevier Inc. All rights reserved.

关键词： query access plans execution scheduling serial and parallel execution scheduling inter/intra-operation parallelization parallel query processing parallel object-oriented databases

来源：评论

学校读者我要写书评

暂无评论

Analyzing imbalance among homogeneous index servers in a web search system

引用

INFORMATION processing & MANAGEMENT 2007年第3期43卷 592-608页

作者： Badue, C. S. Baeza-Yates, R. Ribeiro-Neto, B. Ziviani, A. Ziviani, N. Univ Fed Minas Gerais Dept Comp Sci BR-31270010 Belo Horizonte MG Brazil Google Engn Belo Horizonte Belo Horizonte MG Brazil Natl Lab Sci Comp LNCC Petropolis Brazil

The performance of parallel query processing in a cluster of index servers is crucial for modern web search systems. In such a scenario, the response time basically depends on the execution time of the slowest server to generate a partial ranked answer. Previous approaches investigate performance issues in this context using simulation, analytical modeling, experimentation, or a combination of them. Nevertheless, these approaches simply assume balanced execution times among homogeneous servers (by uniformly distributing the document collection among them, for instance)-a scenario that we did not observe in our experimentation. On the contrary, we found that even with a balanced distribution of the document collection among index servers, correlations between the frequency of a term in the query log and the size of its corresponding inverted list lead to imbalances in query execution times at these same servers, because these correlations affect disk caching behavior. Further, the relative sizes of the main memory at each server (with regard to disk space usage) and the number of servers participating in the parallel query processing also affect imbalance of local query execution times. These are relevant findings that have not been reported before and that, we understand, are of interest to the research community. (c) 2006 Elsevier Ltd. All rights reserved.

关键词： parallel query processing imbalance search engines performance analysis

来源：评论

学校读者我要写书评

暂无评论

APPLYING SEGMENTED RIGHT-DEEP TREES TO PIPELINING MULTIPLE HASH JOINS

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 1995年第4期7卷 656-668页

作者： CHEN, MS LO, ML YU, PS YOUNG, HC UNIV MICHIGAN DEPT EECSANN ARBORMI 48109 IBM CORP ALMADEN RES CTRSAN JOSECA 95120

The pipelined execution of multijoin queries in a multiprocessor-based database system is explored in this paper. Using hash-based joins, multiple joins can be pipelined so that the early results from a join, before the whole join is completed, are sent to the next join for processing. The execution of a query is usually denoted by a query execution tree, To improve the execution of pipelined hash joins, an innovative approach on query execution tree selection is proposed to exploit segmented right deep trees, which are bushy trees of right-deep subtrees. We first derive an analytical model for the execution of a pipeline segment, and then, in light of the model, develop heuristic schemes to determine the query execution plan based on a segmented right-deep tree so that the query can be efficiently executed. As shown by our simulation, the proposed approach, without incurring additional overhead on plan execution, possesses more flexibility in query plan generation, and can lead to query plans of better performance than those achievable by the previous schemes using right-deep trees.

关键词： PIPELINING parallel query processing BUSHY TREES RIGHT-DEEP TREES HASH JOINS

来源：评论

学校读者我要写书评

暂无评论

Integrating open government data with stratosphere for more transparency

引用

JOURNAL OF WEB SEMANTICS 2012年 14卷 45-56页

作者： Heise, Arvid Naumann, Felix Hasso Plattner Inst Potsdam Germany

Governments are increasingly publishing their data to enable organizations and citizens to browse and analyze the data. However, the heterogeneity of this Open Government Data hinders meaningful search, analysis, and integration and thus limits the desired transparency. In this article, we present the newly developed data integration operators of the Stratosphere parallel data analysis framework to overcome the heterogeneity. With declaratively specified queries, we demonstrate the integration of well-known government data sources and other large open data sets at technical, structural, and semantic levels. Furthermore, we publish the integrated data on the Web in a form that enables users to discover relationships between persons, government agencies, funds, and companies. The evaluation shows that linking person entities of different data sets results in a good precision of 98.3% and a recall of 95.2%. Moreover, the integration of large data sets scales well on up to eight machines. (C) 2012 Elsevier B. V. All rights reserved.

关键词： Data integration Data cleansing Record linkage Data fusion parallel query processing Map-reduce

来源：评论

学校读者我要写书评

暂无评论

Performance of a distributed architecture for query processing on workstation clusters

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2003年第4期19卷 463-478页

作者： Soleimany, C Dandamudi, SP Carleton Univ Sch Comp Sci Ctr Networked Comp Ottawa ON K1S 5B6 Canada

A network of workstations (NOWs) is an attractive alternative to parallel database systems due to the cost advantage. In a typical database, client workstations (nodes) submit queries/transactions and receive responses from the database server. With even recent PC-based client nodes providing traditional workstation-class performance, performance improvements can be obtained by offloading some of the processing typically done on the traditional server node to these powerful client nodes. parallel query processing takes advantage of the idle cycles on the client nodes to process the query. In this paper we introduce a distributed architecture for parallel query processing and study the performance of this architecture in various scenarios. We have implemented the distributed architecture using parallel virtual machine (PVM) on a Pentium-based NOW system. Our results show that the distributed architecture successfully achieves good speedups and scaleups. Furthermore, our results show that the distributed architecture handles both light and heavy workloads in the presence of a background (non-query) load. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： parallel query processing parallel database systems networks of workstations load sharing workstation clusters

来源：评论

学校读者我要写书评

暂无评论

A SELF-ADJUSTING DATA DISTRIBUTION MECHANISM FOR MULTIDIMENSIONAL LOAD BALANCING IN MULTIPROCESSOR-BASED DATABASE-SYSTEMS

引用

INFORMATION SYSTEMS 1994年第7期19卷 549-567页

作者： LEE, C HUA, KA NATL CHENG KUNG UNIV INST INFORMAT ENGNTAINANTAIWAN UNIV CENT FLORIDA DEPT COMP SCIORLANDOFL 32816

With the advent of micro-processor, memory, and communication technology, it is economically feasible to develop a parallel database computer system to improve the performance of database systems. Relations in such an environment are usually partitioned and distributed across computing units. To achieve the optimal performance, it is essential for each unit to have a perfectly balanced load (i.e., identical amount of data). However, fragment sizes may vary due to insertions to and deletions from a relation. To retain good performance, the system needs to periodically rebalance the load of the processors by redistributing data among computing units. Traditionally, the redistribution is performed by reshuffling tuples among processors through a relation repartitioning (e.g., rehashing) process. The computation of this process is at the tuple level. In this paper, we present a self-adjusting data distribution scheme which balances computer workload at a cell (coarser grain than tuple) level during query processing to minimize redistribution cost. The entire scheme is built on top of the popular grid file structure. The adaptivity of the scheme and its relevant features are discussed. The cost of load rebalancing is estimated. The result shows that under our assumptions, it is always beneficial to rebalance computer workload before performing a join on skewed data.

关键词： parallel query processing LOAD BALANCING DATA SKEW GRID FILE

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：