Gleb Skobeltsyn · 2009
Efficient and effective search in large-scale data repositories requires complex indexing solutions deployed on a large number of servers. Commercial Web search engines already rely upon complex systems to be able to return relevant query results and keep processing times within the comfortable sub-second limit. Nevertheless, the exponential growth of the amount of content on the Web poses serious challenges with respect to scalability. Coping with these challenges requires novel indexing solutions that not only remain scalable but also preserve the search accuracy. In this work we introduce and explore the concept of query-driven indexing - an index construction strategy that uses caching techniques to adapt to the querying patterns expressed by users. We suggest to abandon the strict difference between indexing and caching, and to build a distributed indexing structure, or a distributed cache, such that it is optimized for the current query load. Our experimental and theoretical analysis shows that employing query-driven indexing is especially beneficial when the content is (geographically) distributed in a Peer-to-Peer network.
Cited by 0
Jos Blakeley Conor, José A. Blakeley, Conor Cunningham et al. · 2005
This paper presents an architecture overview of the distributed, heterogeneous query processor (DHQP) in the Microsoft SQL Server database system to enable queries over a large collection of diverse data sources. The paper highlights three salient aspects of the architecture. First, the system introduces welldefined abstractions such as connections, commands, and rowsets that enable sources to plug into the system. These abstractions are formalized by the OLE DB data access interfaces. The generality of OLE DB and its broad industry adoption enables our system to reach a very large collection of diverse data sources ranging from personal productivity tools, to database management systems, to file system data. Second, the DHQP is built-in to the relational optimizer and execution engine of the system. This enables DH queries and updates to benefit from the cost-based algebraic transformations and execution strategies available in the system. Finally, the architecture is inherently extensible to support new data sources as they emerge as well as serves as a key extensibility point for the relational engine to add new features such as full-text search and distributed partitioned views.
Cited by 0
Maya, Ramanath, Jayant, Haritsa R · NOT FOUND REPOSITORY (Indian Institute of Science Bangalore) · 2000
Cited by 0
Hyunmo Kang, N. Roussopoulos · Digital Repository at the University of Maryland (University of Maryland College Park) · 1987
A new approach to distributed query processing is proposed. In the conventional approach, a query is processed by the reducing phase and the joining phase. In the reducing phase, the relations referenced in the query are reduced using semijoins, and all the relations are joined at the result site in the joining phase. In the proposed approach, an arbitrary interleaving of joins and semijoins is allowed toward the generation of the query result at the result site. The proposed approach considers the local processing cost as well as the data transmission cost while the conventional approach mostly considers the data transmission cost only. The effectiveness of the query processing strategies generated according to the proposed approach is discussed for both the restricted class of join queries and the general join queries.
Cited by 8Open access
Apostolos N. Papadopoulos, Spyros Sioutas, Christos Zaroliagis et al. · 2019
Range queries are important in many diverse applications. In its simplest one-dimensional form, a range query is expressed by an interval [a, b] on the real line, whereas the answer consists of all elements e ∈ [a, b]. In this work, we focus on efficient range query processing techniques in the Apache Spark engine, which is the state-of-the-art solution for big data management and analytics. We aim at developing a Spark-based indexing scheme that supports range queries in such large-scale decentralized environments and scale well w.r.t. the number of nodes and the data items stored. Towards this goal, there have been solutions in the last few years, which however turn out to be inadequate at the envisaged scale, since the classic linear or even the logarithmic complexity (for point queries) is still too expensive, whereas range query processing is even more demanding. In this paper, we go one step further and present a solution with sub-logarithmic complexity. In particular, we present SPIS (SPark-based Interpolation Search), a tree structure that outperforms the existing Spark built-in lookup techniques. We carry out an experimental evaluation by using synthetic data sets. Our experimental results demonstrate the efficiency and scalability of the proposed approach.
Cited by 5
Cyrus Soleimany, Sivarama P. Dandamudi · Lecture notes in computer science · 2000
Cited by 3
Chengwen Liu And, Chengwen Liu, Hao Chen · 2007
. This paper describes a hash partitioning strategy for distributed query processing in a multi-database environment in which relations are unfragmented and replicated. Methods and efficient algorithms are provided to determine the sets of relations that can be hash partitioned, the copies of the relations to be partitioned and the partition sites, how the relations are to be partitioned and where the fragments are to be sent for processing. For a given query, there are usually more than one set of relations that can be hash partitioned. Among the alternatives, our algorithm picks the plan that gives the minimum response time. The paper also presents a simulation study that compares the hash partition strategy to the PRS strategy. The study shows that our strategy outperforms the PRS strategy. 1 Introduction Relation partitioning has been used as a strategy for data allocation [12, 19], or dynamic query processing [4, 13, 15, 21] to achieve a high degree of parallelism amo...
Cited by 0
Wee Siong, Ng Beng, Chin Ooi et al. · 2003
In this paper, we propose a distributed continuous query (CQ) processing system based on Peer to Peer architecture (P2P) technology, where peers collaborate in terms of processing and providing data. In particular, we propose that data streams be reallocated and query sharing be exploited at the peer-to-peer level. Our proposed approach supports a novel class of queries, which we call pervasive CQ. A pervasive CQ issued by peer A is evaluated by peer B and stored there to be retrieved by peer A at a later time. This class of continuous queries is particularly beneficial in the heterogeneous environment in which peers operate. We conduct an extensive performance study to evaluate the proposed strategies, and our results show the effectiveness of the proposed schemes. Contact Author:
Cited by 0
Chengwen Liu Hao, Hao Chen, Warren Krueger · 1996
We present an algorithm to make use of placement dependency information to process distributed queries. Our algorithm first partitions the referenced relations of a given query into a number of non-exclusive subsets such that the fragmented relations within a subset have placement dependency and the join operation(s) associated with the relations in the subset can be locally processed without data transfer. Each subset is associated with a set of sites and can be used to generate an execution plan for the given query by keeping the fragmented relations in the subset fragmented at the sites where they are situated while replicating the other referenced relations at each of the processing sites. Among the alternatives, our algorithm picks the plan that gives the minimum response time. Our experimental results show that our algorithm improves response time significantly. 1 Introduction Query processing in distributed database systems has been an active research area for many years. Many...
Cited by 0
Cyrus Soleimany · 1998
Cited by 3Open access
Peter Bodorik · 1985
This research addresses the problem of query processing by joins in a relational Distributed Data Base (DDB). The problem of finding network locations for execution of joins in a given sequence is shown to be polynomial. A two-phased method, which (i) first finds the sequence of joins and then determines the network location for their executions, is shown through modelling to formulate strategies which are close to the minimal delay strategies.
A heuristic algorithm for formulation of strategies for distributed queries is presented. The algorithm interatively creates a partial space of strategies represented by a graph consisting of a superposition of binary trees such that each tree corresponds to a unique strategy. Through the algorithm's parameter it is possible to alter the depth of the strategy space to be created at each iteration. Consequently, a trade-off between (strategy) execution time and formulation delay can be obtained. It is shown for a test-bed of queries that (i) the search for optimal strategies is undesirable due to the high strategy formulation delay and (ii) the heuristic algorithm incurs a query response time (combined delay due to formulation and execution) which is close to the execution time optimal strategies.
Optimal strategies are employed in evaluating various cost measures which can be used in optimization of distributed queries. In particular, information which is necessary to examine the effect on the various costs associated with optimizing a particular query execution cost is identified and its use is demonstrated on a test-bed of queries. Nine measures of cost are defined and modelling results indicate that those measures which include costs due to both CPU processing and data transfer are more effective than those which include only CPU processor or data transfer cost.
Cited by 6Open access
Maya Ramanath, Jayant R. Haritsa · World Wide Web · 2000
Cited by 7
Hyeong‐Il Kim, Min Yoon, Young-Sung Shin et al. · Lecture notes in electrical engineering · 2015
Cited by 0
B. M. Monjurul Alom, Frans Henskens, Michael Hannaford · 2009
Query processing is an important concern in the field of distributed databases. The main problem is: if a query can be decomposed into subqueries that require operations at geographically separated databases, determine the sequence and the sites for performing this set of operations such that the operating cost (communication cost and processing cost) for processing this query is minimized. The problem is complicated by the fact that query processing not only depends on the operations of the query, but also on the parameter values associated with the query. Distributed query processing is an important factor in the overall performance of a distributed database system. Query optimization is a difficult task in a distributed client/server environment as data location becomes a major factor. In order to optimize queries accurately, sufficient
Cited by 16
Carlo Meghini, Yannis Tzitzikas, Veronica Coltella et al. · arXiv (Cornell University) · 2011
We address the problem of answering queries over a distributed information system, storing objects indexed by terms organized in a taxonomy. The taxonomy consists of subsumption relationships between negation-free DNF formulas on terms and negation-free conjunctions of terms. In the first part of the paper, we consider the centralized case, deriving a hypergraph-based algorithm that is efficient in data complexity. In the second part of the paper, we consider the distributed case, presenting alternative ways implementing the centralized algorithm. These ways descend from two basic criteria: direct vs. query re-writing evaluation, and centralized vs. distributed data or taxonomy allocation. Combinations of these criteria allow to cover a wide spectrum of architectures, ranging from client-server to peer-to-peer. We evaluate the performance of the various architectures by simulation on a network with O(10^4) nodes, and derive final results. An extensive review of the relevant literature is finally included.
Cited by 0Open access
Jonghyeong Han, Joonwoo Lee, Seungyong Park et al. · Lecture notes in computer science · 2007
Cited by 1Open access
SHEN YANYAN · National University of Singapore · 2015
Ph.D
Cited by 0
Yali Zhu, Elke A. Rundensteiner · 2007
Partitioned query processing is an effective method to process continuous queries with large stateful operators in a distributed systems. This method typically partitions input data into non-overlapping portions, with each query plan instance installed on a separate machine processing only one portion of the data. Dynamic redistribution of load among machines is then employed to handle fluctuating stream characteristics. However, existing load redistribution solutions have made the implicit assumption that no local query optimization is conducted at runtime on any of the participating machines, i.e., all local query plan instances are static and thus remain identical. This is restrictive for dynamic stream systems, where data partitions may experience significant fluctuations in selectivities or arrival rates over time - thus warranting local plan reoptimization. This raises the new problem that the heterogeneity of plan shapes among different machines must be tackled when doing load redistribution. To address this, we propose two new load balancing strategies along with corresponding protocols, that can balance the workload across a set of machines while seamlessly handling the complexity caused by local plan changes. The PTLB strategy is plan-agnostic, requiring no detailed knowledge of the underlying query plan. The MSLB strategy is plan-aware, that is. it rebalances the load by comparing the plan shape differences on the participating machines. All proposed techniques have been implemented in the DCAPE continuous query system. Our experiments demonstrate that the application of both query optimization and load balancing results in superior performance compared to applying either of the adaptation techniques alone - as has been the state-of-the-art in the current literature. Our evaluation compares the relative applicability and efficiency of the two proposed techniques PTLB and MSLB.
Cited by 2
T. V. Vijay Kumar, Vikram Singh, Ajay Kumar Verma · 2010
Distributed query processing has become essential in today's scenario to address the changing business needs of users. It aims to arrive at an optimal query processing plan for a given distributed query. This is a complex process as the number of possible query processing plans grows rapidly with increase in the number of sites used, and relations accessed, by the query. Therefore, there is a need to determine optimal query processing plans among all possible plans. The approach presented in this paper attempts to generate such optimal query processing plans using genetic algorithm. As per the approach, the query plans having the required data residing close to each other are considered more efficient and, therefore, are generated. These generated query plans would result in efficient query processing. Further, experimental results show that the approach is able to generate such optimal query processing plans in a fewer number of generations.
Cited by 18
Sabrina De, Capitani Vimercati, Stefano Paraboschi et al. · 2009
We present a simple, yet powerful, approach for the specification and enforcement of authorizations regulating data release among data holders collaborating in a distributed computation, to ensure that query processing discloses only data whose release has been explicitly authorized. Data disclosure is captured by means of profiles, associated with each data computation, that describe the information carried by the result. We also present an algorithm that, given a query plan, determines whether it can be safely executed and produces a safe execution strategy. The main advantage of our approach is its simplicity that, without impacting expressiveness, makes it nicely interoperable with current solutions for collaborative computations in distributed database systems. 1.
Cited by 0