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.

Troubleshooting imperative programs at runtime is very challenging because the final optimized plan is quite different from the original design time model. In this demonstration, we present ProcAnalyzer, an expressive and intuitive tool for troubleshooting issues related to performance, code quality, and security. We propose end-to-end graph (E2EGraph) that provides a holistic view of design time, compile time, and runtime behavior so that end users and engine developers easily find the correlations between design time and runtime. ProcAnalyzer provides suggestions and visualization to find problematic statements through the E2EGraph.

Hybrid transactional and analytical processing (HTAP) systems like SAP HANA make it much simpler to manage both operational load and analytical queries without ETL, separate data warehouses, et al. To represent both transactional and analytical business logic in a single database system, stored procedures are often used to express analytical queries using control flow logic and DMLs. Optimizing these complex procedures requires a fair knowledge of imperative programming languages as well as the declarative query language. Therefore, unified optimization techniques considering both program and query optimization techniques are essential for achieving optimal query performance. In this paper, we propose a novel unified optimization technique for efficient iterative query processing. We present a notion of query motion that allows the movement of SQL queries in and out of a loop. Additionally, we exploit a new cost model that measures the quality of the execution plan with consideration for queries and loop iterations. We describe our experimental evaluation that demonstrates the benefit of our technique using both a standard decision support benchmark and real-world workloads. An extensive evaluation shows that our unified optimization technique enumerates plans that achieve performance improvements of up to an order of magnitude faster than plans generated by the existing loop-invariant code motion technique.

Recently, high utility pattern (HUP) mining is one of the most important research issues in data mining due to its ability to consider the nonbinary frequency values of items in transactions and different profit values for every item. On the other hand, incremental and interactive data mining provide the ability to use previous data structures and mining results in order to reduce unnecessary calculations when a database is updated, or when the minimum threshold is changed. In this paper, we propose three novel tree structures to efficiently perform incremental and interactive HUP mining. The first tree structure, Incremental HUP Lexicographic Tree ({\rm IHUP}_{{\rm {L}}}-Tree), is arranged according to an item's lexicographic order. It can capture the incremental data without any restructuring operation. The second tree structure is the IHUP Transaction Frequency Tree ({\rm IHUP}_{{\rm {TF}}}-Tree), which obtains a compact size by arranging items according to their transaction frequency (descending order). To reduce the mining time, the third tree, IHUP-Transaction-Weighted Utilization Tree ({\rm IHUP}_{{\rm {TWU}}}-Tree) is designed based on the TWU value of items in descending order. Extensive performance analyses show that our tree structures are very efficient and scalable for incremental and interactive HUP mining.

This paper proposes a prefix-tree structure, called CPS-tree (Compact Pattern Stream tree) that efficiently discovers the exact set of recent frequent patterns from high-speed data stream. The CPS-tree introduces the concept of dynamic tree restructuring technique in handling stream data that allows it to achieve highly compact frequency-descending tree structure at runtime and facilitates an efficient FP-growth-based [1] mining technique.

Association rule mining often generates a huge number of rules, but a majority of them either are redundant or do not reflect the true correlation relationship among data objects. We re-examine this problem and show that two interesting measures, all-confidence (denoted as /spl alpha/) and coherence (denoted as /spl gamma/), both disclose genuine correlation relationships and can be computed efficiently. Moreover, we propose two interesting algorithms, CoMine(/spl alpha/) and CoMine(/spl gamma/), based on extensions of a pattern-growth methodology. Our performance study shows that the CoMine algorithms have high performance in comparison with their Apriori-based counterpart algorithms.

In a database management system (DBMS), partial rollback is an important mechanism for canceling only part of the operations executed in a transaction back to a savepoint. Partial rollback complicates buffer management because it should restore the state of the buffers as well as that of the database. Several relational DBMSs (RDBMSs) currently provide this mechanism using page buffers. However, object-oriented or object-relational DBMSs (OO/ORDBMSs) cannot utilize the partial rollback scheme of RDBMSs as is because, unlike RDBMSs, many of them use a dual buffer consisting of an object buffer and a page buffer. In this paper, we propose a thorough study of partial rollback schemes of OO/ORDBMSs with a dual buffer. First, we classify the partial rollback schemes of OO/ORDBMSs into a single buffer-based scheme and a dual buffer-based scheme by the number of buffers used to process rollback. Next, we propose four alternative partial rollback schemes: a page buffer-based scheme, an object buffer-based scheme, a dual buffer-based scheme using a soft log, and a dual buffer-based scheme using shadows. We then evaluate their performance through simulations. The results show that the dual buffer-based partial rollback scheme using shadows provides the best performance. Partial rollback in OO/ORDBMS has not been addressed in the literature; yet, it is a useful mechanism that must be implemented. The proposed schemes are practical ones that can be implemented in such DBMSs.

Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database systems. A number of spatial join algorithms have recently been proposed in the literature. Most of them, however, perform the join in the original space. Joining in the original space has a drawback of dealing with sizes of objects and thus has difficulty in developing a formal algorithm that does not rely on heuristics. In this paper, we propose a spatial join algorithm based on the transformation technique. An object having a size in the two-dimensional original space is transformed into a point in the four-dimensional transform space, and the join is performed on these point objects. This can be easily extended to n-dimensional cases. We show the excellence of the proposed approach through analysis and extensive experiments. The results show that the proposed algorithm has a performance generally better than that of the R*-based algorithm proposed by Brinkhoff et al. This is a strong indicating that corner transformation preserves clustering among objects and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely affect clustering. We believe that our result will provide a new insight towards transformation-based spatial query processing.

Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database systems. Since spatial join is a fairly expensive operation, we need an efficient algorithm taking advantage of the characteristics of available spatial access methods. In this paper, we propose a spatial join algorithm using corner transformation and show its excellence through experiments. To the extent of authors' knowledge, the spatial join processing using corner transformation is new. In corner transformation, two regions in one file joined with two adjacent regions in the other file share a large common area. The proposed algorithm utilizes this property in order to reduce the number of disk accesses for spatial join. Experimental results show that the performance of the algorithm is generally better than that of the R*-tree based algorithm proposed by Brinkhoff et al. (1993. 1994). This is a strong indication that corner transformation is a promising category of spatial access methods and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely effect the clustering. We also briefly mention that the join algorithm based on corner transformation has a nice property of being amenable to parallel processing. We believe that our result will provide a new insight towards transformation-based processing of spatial operations.