1,720,983 research outputs found
Robust Recursive Query Parallelization in Graph Database Management Systems
No full textRecursive joins such as shortest path and variable length path queries are a core feature set of modern graph database management systems (GDBMS). Since these queries tend to be computationally expensive and may suffer from high execution time, they require efficient parallel processing using multiple cores to achieve good performance. Existing work on parallel query processing includes the morsel driven parallelism approach that distributes a unit of work (denoted as “morsel”) to threads for parallel execution. We revisit this technique in the context of parallelization of recursive joins in GDBMS and discuss how the traditional approach of morsel driven query execution is inadequate to tackle recursive join queries. We show how this approach can be modified to better accommodate scalable parallelization of recursive joins. We further describe how this modified parallel query execution approach has been integrated into Kuzu, an embedded disk based columnar GDBMS. Compared to vanilla morsel driven parallelism, our modified parallel query execution approach can be orders of magnitude faster and scales well on multiple cores
Systems for Graph Extraction from Tabular Data
Get PDFConnections amongst real-world entities provide significant insights for numerous real-life applications in social networks, semantic web, road maps, finance, among others. Graphs are perhaps the most natural way to model such connections in application data. However, in many enterprises, an application data is still primarily stored in an RDBMS in a tabular format and users extract graphs out of an RDBMS and store them in specialized graph processing systems. As a result, many users face two major challenges before conducting any graph analysis. First, extracting graphs from an RDBMS requires building an ETL pipeline, which can require a significant amount of time. Second, keeping the extracted graph in the graph processing system, such as a graph database management system (GDBMS), in sync with the original data in the RDBMS requires developing additional non-trivial synchronization code. In this thesis, we study and address these two challenges and present two software systems, GraphWrangler and R2GSync, that we have developed to solve these challenges. GraphWrangler is an interactive system that streamlines the ETL pipeline. Users connect to an RDBMS using GraphWrangler and with several simple interactions, such as dragging and dropping of rows and columns and drawing edges on the screen, they describe table-to-graph mappings. This way, users can describe the graphs they would like to extract without writing any custom scripts. In addition, GraphWrangler allows user to immediately visualize their tables in the form of a graph. Our second system, R2GSync, uses the mappings of an extracted graph and maintains a consistent, i.e., in sync, copy of this graph in a GDBMS as updates happen to the original RDBMS from which the graph was extracted. Querying the extracted graph inside the GDBMS requires a new querying functionality inside the GDBMS that we call edge views. We describe our implementation of edge views and several optimizations to make queries that contain edge views more efficient
Join Cardinality Estimation Graphs: Analyzing Pessimistic and Optimistic Estimators Through a Common Lens
Get PDFJoin cardinality estimation is a fundamental problem that is solved in the query optimizers of database management systems when generating efficient query plans. This problem arises both in systems that manage relational data as well those that manage graph-structured data where systems need to estimate the cardinalities of subgraphs in their input graphs. We focus on graph-structured data in this thesis.
A popular class of join cardinality estimators uses statistics about sizes of small size queries to make estimates for larger queries. Statistics-based estimators can be broadly divided into two groups: (i) optimistic estimators that use statistics in formulas that make degree regularity and conditional independence assumptions; and (ii) the recent pessimistic estimators that estimate the sizes of queries using a set of upper bounds derived from linear programs, such as the AGM bound, or tighter bounds, such as the MOLP bound that are based on information theoretic bounds.
In this thesis, we introduce a new framework that we call cardinality estimation graph (CEG) that can represent the estimates of both optimistic and pessimistic estimators. We observe that there is generally more than one way to generate optimistic estimates for a query, and the choice has either been ad-hoc or unspecified in previous work. We empirically show that choosing the largest candidate yields much higher accuracy than pessimistic estimators across different datasets and query workloads, and it is an effective heuristic to combat underestimations, which optimistic estimators are known to suffer from.
To further improve the accuracy, we demonstrate how hash partitioning, an optimization technique designed to improve pessimistic estimators' accuracy, can be applied to optimistic estimators, and we evaluate the effectiveness.
CEGs can also be used to obtain insights of pessimistic estimators. We show MOLP estimator is at least as tight as the pessimistic estimator and are identical on acyclic queries over binary relations, and the MOLP CEG offers an intuitive combinatorial proof that the MOLP bound is tighter than the DBPLP bound
Multiple Continuous Subgraph Query Optimization Using Delta Subgraph Queries
Get PDFThis thesis studies the problem of optimizing and evaluating multiple directed structural subgraph queries, i.e., those without highly selective predicates on the edges or vertices, continuously in a changing graph. Existing techniques focus on queries with highly selective predicates or are designed for evaluating a single query. As such, these techniques do not scale when evaluating multiple structural queries either because their computations become prohibitively inefficient or they use prohibitively large auxiliary data structures.
We build upon the delta subgraph query (DSQ) framework that was introduced in prior work. This framework decomposes queries into multiple delta queries, which are then evaluated one query vertex at a time, without requiring any auxiliary data structures. We study the problem of picking good query vertex orderings for a set of DSQs cumulatively to share computation across different DSQs and achieve efficient runtimes in practice. We describe a greedy cost-based optimizer that takes as input a set of DSQs and a subgraph extension catalogue, and generates a single low cost combined plan that cumulatively evaluates all of the DSQs by sharing computation across them. Our combined plans consist of a Scan and multiple Extend/Intersect (E/I) operators. The E/I operator takes a set of partial matches and extends them by one query vertex. We adopt as our cost metric intersection cost (i-cost), which we show is a good estimate of the actual work performed during query evaluation. We further describe an optimization to the base optimizer that expands the DSQs algebraically to even more DSQs to allow more computation sharing between them. On small query sets we demonstrate that our cost-based greedy optimizer is able to find close to optimal combined plans in terms of run time. On larger query sets, we demonstrate that our optimizer and expanded DSQ optimization can yield significant performance improvements against several baselines
GraphflowDB: Scalable Query Processing on Graph-Structured Relations
Get PDFFinding patterns over graph-structured datasets is ubiquitous and integral to a wide range of analytical applications, e.g., recommendation and fraud detection. When expressed in the high-level query languages of database management systems (DBMSs), these patterns correspond to many-to-many join computations, which generate very large intermediate relations during query processing and degrade the performance of existing systems.
This thesis argues that modern query processors need to adopt two novel techniques to be efficient on growing many-to-many joins: (i) worst-case optimal join algorithms; and (ii) factorized representations. Traditional query processors generate join plans that use binary joins, which in iteration take two relations, base or intermediate, to join and produce a new relation. The theory of worst-case optimal joins have shown that this style of join processing can be provably suboptimal and hence generate unnecessarily large intermediate results. This can be avoided on cyclic join queries if the join is performed in a multi-way fashion a join-attribute-at-a-time. As its first contribution, this thesis proposes the design and implementation of a query processor and optimizer that can generate plans that mix worst-case optimal joins, i.e., attribute-at-a-time joins and binary joins, i.e., table-at-a-time joins. In contrast to prior approaches with novel join optimizers that require solving hard computational problems, such as computing low-width hypertree decompositions of queries, our join optimizer is cost-based and uses a traditional dynamic programming approach with a new cost metric.
On acyclic queries, or acyclic parts of queries, sometimes the generation of large intermediate results cannot be avoided. Yet, the theory of factorization has shown that often such intermediate results can be highly compressible if they contain multi-valued dependencies between join attributes. Factorization proposes two relation representation schemes, called f- and d-representations, to represent the large intermediate results generated under many-to-many joins in a compressed format. Existing proposals to adopt factorized representations require designing processing on fully materialized general tries and novel operators that operate on entire tries, which are not easy to adopt in existing systems. As a second contribution, we describe the implementation of a novel query processing approach we call factorized vector execution that adopts f-representations. Factorized vector execution extends the traditional vectorized query processors to use multiple blocks of vectors instead of a single block allowing us to factorize intermediate results and delay or even avoid Cartesian products. Importantly, our design ensures that every core operator in the system still performs computations on vectors. As a third contribution, we further describe how to extend our factorized vector execution model with novel operators to adopt d-representations, which extend f-representations with cached and reused sub-relations. Our design here is based on using nested hash tables that can point to sub-relations instead of copying them and on directed acyclic graph-based query plans.
All of our techniques are implemented in the GraphflowDB system, which was developed throughout the years to facilitate the research in this thesis. We demonstrate that GraphflowDB’s query processor can outperform existing approaches and systems by orders of magnitude on both micro-benchmarks and end-to-end benchmarks. The designs proposed in this thesis adopt common-wisdom query processing techniques of pipelining, vector-based execution, and morsel-driven parallelism to ensure easy adoption in existing systems. We believe the design can serve as a blueprint for how to adopt these techniques in existing DBMSs to make them more efficient on workloads with many-to-many joins
Turning Open Government Data Portals into Interactive Databases
Get PDFThe launch of open governmental data portals (OGDPs), such as data.gov, data.gov.in, and open.canada.ca, have popularized the open data movement of the last decade, which now includes numerous other portals from other public or private institutions. These portals publish large numbers of datasets related to a very wide range of topics. Although the amount of datasets in OGDPs are increasing, the functionalities provided by most of the OGDPs to the end users are limited to finding the datasets based on the title and description, and downloading the actual files. This limitation hinders the end users, especially those without technical skills, to find the open data files and make use of them.
This thesis presents Governor, a web application developed to make open data tables more accessible to the end users in several ways. First, Governor facilitates searching the actual records in the original tables in OGDP. Second, Governor allows users to preview the tables in the web browser directly without downloading them. Third, Governor allows users to integrate multiple tables to form enriched datasets. A key feature here is automatically finding and suggesting joinable and unionable tables to users based on the latest state of their integrated tables. These operations are performed in the web browser interactively through a few clicks without using a programming language or a spreadsheet software. Lastly, Governor provides a set of features to summarize the provenance of integrated tables allowing users and their collaborators to easily trace back the values in integrated tables to the original tables in the OGDP
A+ Indexes: Highly Flexible Adjacency Lists in Graph Database Management Systems
Get PDFAdjacency lists are the most fundamental storage structure in existing graph database management systems (GDBMSs) to index input graphs. Adjacency lists are universally linked-list like per-vertex structures that allow access to a set of edges that are all adjacent to a vertex. In several systems, adjacency lists can also allow efficient access to subsets of a vertex’s adjacent edges that satisfy a fixed set of predicates, such as those that have the same label, and support a fixed set of ordering criteria, such as sorting by the ID of destination vertices of the edges. This thesis describes a highly-flexible indexing subsystem for GDBMSs, which consists of two components. The primary component called A+ indexes store adjacency lists, which compared to existing adjacency lists, provide flexibility to users in three aspects: (1) in addition to per-vertex adjacency lists, users can define per-edge adjacency lists; (2) users can define adjacency lists for sets of edges that satisfy a wide range of predicates; and (3) provide flexible sorting criteria. Indexes in existing GDBMS, such as adjacency list, B+ tree, or hash indexes, index as elements the vertices or edges in the input graph. The second component of our indexing sub-system is secondary B+ tree and bitmap indexes that index aggregate properties of adjacency lists in A+ indexes. Therefore, our secondary indexes effectively index adjacency lists as elements. We have implemented our indexing sub-system on top of the Graphflow GDBMS. We describe our indexes, the modifications we had to do to Graphflow’s optimizer, and our implementation. We provide extensive experiments demonstrating both the flexibility and efficiency of our indexes on a large suite of queries from several application domains
DPQP: A D-representation-based Pipelined Factorized Query Processor for Graph Database Management Systems
Get PDFFactorized databases utilize factorized data representations during query processing to obtain more compact final query results and faster runtimes for queries with many-to-many joins. We revisit this technique in the context of graph database management systems (GDBMSs) whose common workloads are large joins with many-to-many relationships on graph-structured data. We first review the theory of factorized databases and classic flat intermediate tuple structure in traditional pipelined GDBMSs. We then present our tuple representation which mimics factorized representations and can be easily integrated into existing query processors. We further describe how to cache sub-query results with this factorized tuple structure through a static dependency analysis of the query. We have integrated our factorized query processor into GraphflowDB, an in-memory GDBMS. Compared to the original version of GraphflowDB, whose processor is not fully factorized, query plans in our processor can be orders of magnitude faster and produce orders of magnitude smaller result sizes
Systems and Algorithms for Dynamic Graph Processing
Get PDFData generated from human and systems interactions could be naturally represented as graph data. Several emerging applications rely on graph data, such as the semantic web, social networks, bioinformatics, finance, and trading among others. These applications require graph querying capabilities which are often implemented in graph database management systems (GDBMS). Many GDBMSs have capabilities to evaluate one-time versions of recursive or subgraph queries over static graphs – graphs that do not change or a single snapshot of a changing graph. They generally do not support incrementally maintaining queries as graphs change. However, most applications that employ graphs are dynamic in nature resulting in graphs that change over time, also known as dynamic graphs.
This thesis investigates how to build a generic and scalable incremental computation solution that is oblivious to graph workloads. It focuses on two fundamental computations performed by many applications: recursive queries and subgraph queries. Specifically, for
subgraph queries, this thesis presents the first approach that (i) performs joins with worstcase optimal computation and communication costs; and (ii) maintains a total memory footprint almost linear in the number of input edges. For recursive queries, this thesis studies optimizations for using differential computation (DC). DC is a general incremental computation that can maintain the output of a recursive dataflow computation upon changes. However, it requires a prohibitively large amount of memory because it maintains differences that track changes in queries input/output. The thesis proposes a suite of optimizations that are based on reducing the number of these differences and recomputing them when necessary. The techniques and optimizations in this thesis, for subgraph and recursive computations, represent a proposal for how to build a state-of-the-art generic and
scalable GDBMS for dynamic graph data management
Domain Ordering and Box Cover Problems for Beyond Worst-Case Join Processing
Get PDFJoin queries are a fundamental computational task in relational database management systems. For decades, complex joins were most often computed by decomposing the query into a query plan made of a sequence of binary joins. However, for cyclic queries, this type of query plan is sub-optimal. The worst-case run time of any such query plan exceeds the number of output tuples for any query instance.
Recent theoretical developments in join query processing have led to join algorithms which are worst-case optimal, meaning that they run in time proportional to the worst-case output size for any query with the same shape and the same number of input tuples. Building on these results are a class of algorithms providing bounds which go beyond
this worst-case output size by exploiting the structure of the input instance rather than just the query shape.
One such algorithm, Tetris, is worst-case optimal and also provides an upper bound on its run time which depends on the minimum size of a geometric box certificate for the input query. A box certificate is a subset of a box cover whose union covers every tuple which is not present in the query output. A box cover is a set of n-dimensional boxes which cover all of the tuples not contained in the input relations. Many query instances admit different box certificates and box covers when the values in the attributes' domains are ordered differently. If we permute the input query according to a domain ordering which admits a smaller box certificate, use the permuted query as input to Tetris, then transform the result back with the inverse domain ordering,
we can compute the query faster than was possible if the domain ordering was fixed. If we can efficiently compute an optimal domain ordering for a query, then we can state a beyond worst-case bound that is stronger than what is provided by Tetris.
This paper defines several optimization problems over the space of domain orderings where the objective is to minimize the size of either the minimum box certificate or the minimum box cover for the given input query. We show that most of these problems are NP-hard. We also provide approximation algorithms for several of these problems.
The most general version of the box cover minimization problem we will study, BoxMinPDomF, is shown to be NP-hard, but we can compute an approximation only a poly-logarithmic factor larger than K^(a*r), where K is the minimum box cover size under any domain ordering and r is the maximum number of attributes in a relation. This result allows us to compute join queries in time N+K^(a*r*(w+1))+Z, times a poly-logarithmic factor in N, where N is the number of input tuples, w is the treewidth of the query, and Z is the number of output tuples. This is a new beyond worst-case bound. There are queries for which this bound is exponentially smaller than any bound provided by Tetris.
The most general version of the box certificate minimization problem we study, CertMinPDomF, is also shown to be NP-hard. It can be computed exactly if the minimum box certificate size is at most 3, but no approximation algorithm for an arbitrary minimum size is known. Finding such an approximation algorithm is an important direction for future research
- …
