Recent efforts in learned cardinality estimation (CE) have substantially improved estimation accuracy and query plans inside query optimizers. However, achieving decent efficiency, scalability, and the support of a wide range of queries at the same time, has remained questionable. Rather than falling back to traditional approaches to trade off one criterion with another, we present a new learned approach that achieves all these. Our method, called ASM, harmonizes autoregressive models for per-table statistics estimation, sampling for merging these statistics for join queries, and multi-dimensional statistics merging that extends the sampling for estimating thousands of sub-queries, without assuming independence between join keys. Extensive experiments show that ASM significantly improves query plans under a similar or smaller overhead than the previous learned methods and supports a wider range of queries.

The continuous subgraph matching (CSM) problem aims to continuously detect patterns on a dynamic graph, with real-world applications such as fraud detection. Numerous methods have been proposed to address CSM, yet they lack fair comparisons. Furthermore, an existing unified framework for CSM shows misleading experimental results due to its suboptimal implementations. In this paper, we propose a new framework that generates CSM code from the logical and physical plans of delta queries with stacked views. By expressing each CSM method as a delta query plan, our framework enables fair comparisons of CSM methods. Through our comprehensive experiments, we make cause-and-effect arguments for the divergent performance trends from the previous papers and further analyze the individual impacts of various techniques on overall performance. Specifically, our CSM code for an old method significantly outperforms the most recent CSM method, CaLiG, by up to 48.6 times.

GPU-accelerated relational query execution engines have parallelized the execution of a pipeline, a sequence of operators. For the parallelization, the engines evenly partition the tuples in a table that will be scanned by the pipeline's first operator (a scan), and each thread executes the pipeline for the tuples in a partition. However, this approach leads to load imbalances since an operator returns a varying number of output tuples per input tuple, particularly under non-uniform data distributions such as skewed join key values. The load imbalances are classified into intra- and inter-warp load imbalances (intra-WLIs and inter-WLIs) since 1) threads are grouped into warps and 2) every thread in a warp evaluates the same operator for an input tuple concurrently following a single-instruction-multiple-thread manner. In contrast, threads in different warps can evaluate different operators concurrently. Although load balancing techniques have been proposed, however, they fail to solve the load imbalances on various workloads. In this paper, we propose a query execution engine, Themis, named after the deity of fairness, which symbolizes balanced workloads within our context. Themis minimizes intra-WLIs and inter-WLIs across various workloads. First, Themis minimizes intra-WLIs by redistributing tuples between the threads in a warp and making the threads evaluate an operator only when all of them hold inputs. Second, Themis mitigates the inter-WLIs by redistributing the tuples of warps with heavy workloads to idle warps. To check whether a warp's workload is heavy, we propose a method to approximate the sizes of warps' workloads. Based on these approximations, Themis adaptively adjusts the threshold for determining a warp's workload as heavy. In a recent benchmark JCC-H, which introduces skewed join key distributions to TPC-H, Themis significantly alleviates the inter-WLIs and intra-WLIs, outperforming the runner-up by up to 379x.

We propose a new method for estimating the number of answers OUT of a small join query Q in a large database D, and for uniform sampling over joins. Our method is the first to satisfy all the following statements.

Learned cardinality estimation (CE) has recently gained significant attention for replacing long-studied traditional CE with machine learning, especially for deep learning. However, these estimators were developed independently and have not been fairly or comprehensively compared in common settings. Most studies use a subset of IMDB data which is too simple to measure their limits and determine whether they are ready for real, complex data. Furthermore, they are regarded as black boxes, without a deep understanding of why large errors occur.

Graph pattern cardinality estimation is the problem of estimating the number of embeddings of a query graph in a data graph. This fundamental problem arises, for example, during query planning in subgraph matching algorithms. There are two major approaches to solving the problem: sampling and synopsis. Synopsis (or summary)-based methods are fast and accurate if synopses capture information of graphs well. However, these methods suffer from large errors due to loss of information during summarization and inherent assumptions. Sampling-based methods are unbiased but suffer from large estimation variance due to large sample space. To address these limitations, we propose Alley, a hybrid method that combines both sampling and synopses. Alley employs 1) a novel sampling strategy, random walk with intersection, which effectively reduces the sample space, 2) branching to further reduce variance, and 3) a novel mining approach that extracts and indexes tangled patterns as synopses which are inherently difficult to estimate by sampling. By using them in the online estimation phase, we can effectively reduce the sample space while still ensuring unbiasedness. We establish that Alley has worst-case optimal runtime and approximation quality guarantees for any given error bound ε and required confidence μ. In addition to the theoretical aspect of Alley, our extensive experiments show that Alley outperforms the state-of-the-art methods by up to orders of magnitude higher accuracy with similar efficiency.

Despite the crucial role of cardinality estimation in query optimization, there has been no systematic and in-depth study of the existing cardinality estimation techniques for subgraph matching queries. In this paper, for the first time, we present a comprehensive study of the existing cardinality estimation techniques for subgraph matching queries, scaling far beyond the original experiments. We first introduce a novel framework called g-care that enables us to realize all existing techniques on top of it and that provides insights on their performance. By using g-care, we then reimplement representative cardinality estimation techniques for graph databases as well as relational databases. We next evaluate these techniques w.r.t accuracy on rdf and non-rdf graphs from different domains with subgraph matching queries of various topologies so far considered. Surprisingly, our results reveal that all existing techniques have serious problems in accuracy for various scenarios and datasets. Intriguingly, a simple sampling method based on an online aggregation technique designed for relational data, consistently outperforms all existing techniques.

A dynamic graph is defined by an initial graph and a graph update stream consisting of edge insertions and deletions. Identifying and monitoring critical patterns in the dynamic graph is important in various application domains such as fraud detection, cyber security, and emergency response. Given a dynamic data graph and a query graph, a continuous subgraph matching system reports positive matches for an edge insertion and reports negative matches for an edge deletion. Previous systems show significantly low throughput due to either repeated subgraph matching for each edge update or expensive overheads in maintaining enormous intermediate results. We present a fast continuous subgraph matching system called TurboFlux which provides high throughput over a fast graph update stream. TurboFlux employs a concise representation of intermediate results, and its execution model allows fast incremental maintenance. Our empirical evaluation shows that TurboFlux significantly outperforms existing competitors by up to six orders of magnitude.