The rapid development and widespread adoption of open source software, facilitated and accelerated by the web, have fostered a vibrant ecosystem for collaborative development and innovation. GitHub, a leading platform for collaborative software development, currently hosts more than 100 million registered users, creating a substantial ecosystem for examining open source community behaviors. Existing tools for measuring open source communities primarily focus on metrics such as issue response time, pull request response time, or incremental stars to provide insights into community activity. However, these tools are limited in their ability to assess the influence of communities from the perspective of collaboration networks. Moreover, current data collection solutions offer fixed functionalities and lack the flexibility to support multi-source, fine-grained, and customizable data acquisition, which is essential for comprehensive analysis of Open Source Ecosystems (OSEs). In this paper, we present OpenDigger, a framework for multi-dimensional assessment of collaboration activities in OSEs. To enable scalable, modular, and continuous acquisition of OSE data, we developed OpenCrawler, a one-line service providing customizable, fine-grained control over data collection. Using the collected data, OpenDigger computes 20 statistical and 2 network-based metrics, and our empirical analysis further verifies their effectiveness in enabling a comprehensive assessment of trends in OSEs. By continuously collecting logs from GitHub and Gitee, OpenDigger has now accumulated over 9 billion records. Our framework has already been deployed across multiple industrial environments, including Alibaba Group, Ant Group, Apache Foundation, and Mulan Open Source Community.

Isolation Levels (IL) act as correct contracts between applications and database management systems (DBMSs). The complex code logic and concurrent interactions among transactions make it a hard problem to expose violations of various ILs stated by DBMSs. With the recent proliferation of new DBMSs, especially the cloud ones, there is an urgent demand for a general way to detect bugs violating various ILs. The core challenges come from the requirements of: (a) lightweight (verifying without modifying the application logic in workloads and the source code of DBMSs), (b) generality (verifying various ILs), and (c) efficiency (performing efficient verification on a long running workload). To this end, we propose a powerful and practical bug-finding toolLeopard. For lightweight, we propose to infer transaction dependencies based on the time intervals of operations collected from the client-side, without modifying the source code of DBMSs. For generality, based on a thorough analysis of existing concurrency control protocols, we summarize and abstract four mechanisms which can implement ILs in all commercial DBMSs we have investigated. For efficiency, we design atwo-level pipelineto organize and sort massive time intervals in a time and memory conservative way; we propose amechanism-mirrored verificationto simulate the concurrency control protocols implemented in DBMSs for high throughputs; From experimental results,Leopardoutperforms existing methodsCobraandElle. In practice,Leopardhas a superpower to verify various ILs on any workload running on all commercial DBMSs. Moreover, it has successfully discovered 49 bugs that cannot be found by other existing methods.

Cardinality Estimation (CardEst) is crucial for query optimization. Despite the remarkable achievement in DBMS, there is a pressing need to test or tune the work of CardEst. To satisfy the need, we introduce Artemis, a customizable workload generator, which can be used to generate various scenarios with the sensitive features for CardEst, including various data dependencies, complex SQL structures, and diverse cardinalities. It designs a PK-oriented deterministic data generation mechanism to plot various data characteristics; a search-based workload generation is proposed for composing queries with various complexities; it takes a constraint optimization-guided way to achieve a cost-effective cardinality calculation. In this demonstration, users can explore the core features of Artemis in generating workloads.

Various physical design (PD) options within a single database have emerged to optimize diverse workloads, including row-based PDs (e.g., index) and column-based PDs (e.g., column-store replica), each with its own acceleration advantages for different workloads. Determining the optimal combination of these two PDs is a labor-intensive and challenging task, yet it could result in significant performance improvements for the system. Recent automated index advisors (AIAs) have concentrated on identifying the most advantageous combination of row-based PDs. However, the extension of these efforts to the present problem has proven challenging due to 1) the larger search space of hybrid PD selections, 2) the inadequate consideration of the complex interactions between heterogeneous PDs, and 3) the inaccurate evaluation made by the what-if optimizer. To address these issues, we propose a Hybrid physical design advisor (Hyper) with multi-agent reinforcement learning. Hyper excels at recommending the optimal combination of PDs under any specific workload, with an overarching emphasis on both efficiency and quality. Comprehensive evaluations on well-established benchmarks show that our approach outperforms state-of-the-art methods.

The large language model (LLM)-based knob tuning method has attracted considerable attention due to its excellent in-context learning ability and generalizability. However, the existing LLM-based tuning methods do not effectively harmonize multi-source external knowledge, leading to missed opportunities for enhanced knob tuning. In light of this, we propose Rabbit, a novel approach that leverages Retrieval-augmented generation to enhance database knob tuning tools, which seamlessly integrates structured historical tuning experience with graph-encoded static knowledge. First, we introduce an experience-driven knob selection strategy, enhanced by dependency-aware external knowledge integration, to systematically select key knobs. Second, we develop a cutting-edge multi-agent knob domain pruning method, which ensures the reduced search space remains compact yet effective. Finally, we leverage the few-shot capabilities of LLMs to act as surrogate models, enabling rapid exploration of the pruned search space, followed by incremental optimization that expands the search space using historical insights. Moreover, we also design an adaptive strategy to transition between these two search spaces, striking an optimal balance between exploration and exploitation. Extensive experiments on well-established bench-marks demonstrate that Rabbit outperforms the state-of-the-art methods in both effectiveness and efficiency, pointing to a new paradigm for this area.

Update-intensive workloads are prevalent in contemporary OLTP and AI/ML scenarios. An update operation typically involves deleting the old version of the target record and then inserting a new version. In this work, we demonstrate that an LSM-tree faces two issues when dealing with update-intensive workloads. Firstly, the deleted old versions are not promptly garbage collected until they merge with their new versions during compaction. This may lead to space waste and write amplification. Secondly, it is common for an update operation to modify only a small fraction of a data record, such as one of a hundred attributes. However, state-of-the-art LSM-trees fail to effectively utilize the incremental storage strategy, which involves storing only the updated fraction rather than the entire new version to enhance efficiency. In this paper, we propose two techniques, active and fast garbage collection, and adaptive incremental updating, to address these issues, respectively. Active and fast garbage collection probes the distribution of invalid data versions in an LSM-tree and performs garbage collection in a more promptly manner. Adaptive incremental updating applies different storage modes to the update operation to achieve balanced write and read amplification ratios as much as possible. Based on the techniques, we introduce SylphDB implemented based on the codebase of RocksDB and optimized for update-intensive workloads. Experimental results demonstrated that, compared to traditional LSM-tree based systems, SylphDB can improve the efficiency of garbage collection by 2× and reduce write amplification by 20%.

Abstract Distributed in-memory databases are widely adopted to achieve low latency and high bandwidth for data-intensive applications. They support scale-out by sharding and distributing data across multiple nodes. To efficiently adapt to various workloads, distributed in-memory databases must be capable of migrating shards across nodes. In this paper, we demonstrate that state-of-the-art approaches experience significant performance degradation during migration due to service downtime and redundant data transfer. Furthermore, our findings indicate that the presence of service downtime constrains the scalability of migration strategies, while the transfer of redundant data during the snapshot transfer phase limits their adaptability to dynamic workloads. To this end, this paper proposes Aion, a live migration strategy designed for distributed in-memory databases. Aion eliminates any potential service downtime by immediately switching transaction routing to the destination node. To ensure data consistency between the source and destination nodes, as well as serializable execution during migration, Aion proposes the mutual validation phase. Moreover, Aion introduces an analysis phase before the snapshot transfer phase to identify dynamically changing hotspots in workloads. The analysis phase identifies and transfers tuples and versions accessed less frequently to the destination node, reducing the amount of data transferred. Aion is implemented on a distributed in-memory database and evaluated using various OLTP workloads. The results demonstrate that Aion can fundamentally eliminate service downtime, adapt effectively to various workloads and exhibit robust scalability. Compared to state-of-the-art approaches, Aion achieves up to 2.25x–6.57x higher throughput during migration and shortens the migration duration by 53.7–68.2%.

Previous learning-based parameter query optimization (PQO) methods excel in static workloads by precisely selecting optimal plans in a cache with a fixed set of representative plans. However, these methods struggle in dynamic workloads because they cannot predict over dynamically changed plan caches. These queries that fall outside the previously observed query parameter distribution have the risk of reusing suboptimal plans. Unlike traditional PQO methods that learn mappings from parametric query parameters to a fixed set of execution plans, our adaptive PQO framework ( APQO ) takes both query parameters and the plans themselves as model inputs, thereby handling variable numbers of plans in dynamic workloads. By embedding plan representations through representation learning, we pre-train a foundation model offline, enabling APQO to acquire a generalizable plan performance prediction model. Leveraging the foundation model's predictive capability along with a hybrid data augmentation strategy, we train an online calibration model with minimal training data for distribution-shifted new queries, rapidly adapting knowledge for reusing new plans. APQO is natively designed to handle the characteristics of dynamic workloads. Experimental results show that APQO outperforms existing PQO methods in dynamic workloads, achieving a higher cache hit ratio and significantly reducing query latency.

Distributed databases are widely used in various fields, such as financial services and e-commerce. These businesses generally exhibit characteristics of large-scale and rapid growth. However, these business systems often suffer from deadlocks that prevent them from operating normally for extended periods. Traditional deadlock detection methods face challenges in scalability and efficiency, especially as the number of nodes increases. Therefore, deadlock detection has always been a research area in distributed databases. In this paper, we introduce an efficient deadlock detection algorithm called HAWK, leveraging a H ierarchical A pproach based on W or K load modeling. Our algorithm addresses these issues by constructing a dynamic hierarchical detection tree that adapts to transaction patterns, significantly reducing time complexity and communication overhead. HAWK first models the workload and generates a predicted access graph (PAG), transforming the problem of partitioning detection task in the basic hierarchical detection into partition detection zone (DZ) in the PAG by a graph-cutting algorithm. Then, leveraging the properties of strongly connected components (SCCs) and deadlock cycles, the SCC-cut algorithm naturally partitions the system-wide deadlock detection into multiple non-intersecting detection zones, thereby enhancing detection efficiency. We used the greedy SCC-cut algorithm to perform a more fine-grained partitioning of the complex PAG. Finally, by periodically sampling and updating the hierarchical structure, the algorithm remains responsive to dynamic workload variations, ensuring efficient detection. Our approach outperforms both centralized and distributed methods, offering a more efficient and adaptive solution. Extensive experimental results demonstrate the effectiveness of the HAWK algorithm, showing significant reductions in the duration of the deadlock and improved system throughput.

Exploratory data analysis (EDA), coupled with SQL, is essential for data analysts involved in data exploration and analysis. However, data analysts often encounter two primary challenges: (1) the need to craft SQL queries skillfully and (2) the requirement to generate suitable visualization types that enhance the interpretation of query results. Due to its significance, substantial research efforts have been made to explore different approaches to address these challenges, including leveraging large language models (LLMs). However, existing methods fail to meet real-world data exploration requirements primarily due to (1) complex database schema, (2) unclear user intent, (3) limited cross-domain generalization capability, and (4) insufficient end-to-end text-to-visualization capability. This paper presents TiInsight, an automated SQL-based cross-domain exploratory data analysis system. First, we propose a hierarchical data context (i.e., HDC), which leverages LLMs to summarize the contexts related to the database schema, which is crucial for open-world EDA systems to generalize across data domains. Second, the EDA system is divided into four components (i.e., stages): HDC generation, question clarification and decomposition, text-to-SQL generation (i.e., TiSQL), and data visualization (i.e., TiChart). Finally, we implemented an end-to-end EDA system with a user-friendly GUI in the production environment at PingCAP. We have also open-sourced all APIs of TiInsight to facilitate research within the EDA community. Through extensive evaluations by a real-world user study, we demonstrate that TiInsight offers remarkable performance compared to human experts. Additionally, TiSQL achieves an execution accuracy of 86.3% on the Spider dataset when using GPT-4. It also attains an execution accuracy of 60.98% on the Bird test dataset.

High-reliability distributed coordination services have become an indispensable part of modern large-scale distributed systems. Popular coordination services (e.g., ZooKeeper) adopt a single-writer design to provide a centralized service for managing system metadata, including various configuration information and data catalogs, and to provide distributed synchronization functions. With the continuous increase in metadata size and the scale of distributed systems, these coordination services gradually become performance bottlenecks due to their limitations in capacity, read and write performance, and scalability. To bridge the gaps, we propose FDBKeeper, a novel solution that enables scalable coordination services on distributed ACID key-value database systems. Our motivation is that transactional key-value stores (i.e., FoundationDB) meet the demands of performance and scalability required by large-scale distributed systems over coordination service. To leverage these advantages, coordination services can be implemented as an upper layer on top of distributed ACID key-value databases. Our experimental results demonstrate that FDBKeeper significantly outperforms ZooKeeper across key metrics. Additionally, FDBKeeper reduces hardware resource costs on average by 33% in the production environment, resulting in substantial monetary cost savings. We have successfully replaced ZooKeeper with FDBKeeper in the production-grade ClickHouse cluster deployment.

Cache replacement policies are essential for maximizing application performance. Policies such as LRFU, which incorporate both recency and frequency, have shown efficacy in improving hit rates in many studies. In this paper, we theoretically investigated how parameters impact hit rates in LRFU and discovered two distinct features named unimodality and correlation. Drawing on our understanding, we formulated Hill-Cache. Hill-Cache provides a holistic approach to cache. It incorporates recency and frequency and employs a hill-climbing algorithm for adaptability. Additionally, it improves churn resistance through quick demotion, the approach that the most recent research suggests. By overcoming the limitations of LRFU, including high maintenance overhead and dependency on parameters, Hill-Cache distinguishes itself as a new cache method. Hill-Cache is well-suited for situations where there is an efficiency gap between performance devices and capacity devices, including data caching applications and database systems. Our evaluations, employing 36 real-world traces and various sophisticated policies across diverse cache sizes, demonstrated the superior performance of Hill-Cache. It reduces the average miss rate by 11.97% compared to LRU and outperforms other advanced cache policies such as ARC, LIRS, DLIRS, CACHEUS, and S3FIFO. We incorporated Hill-Cache into Memcached and RocksDB, significantly improving performance metrics such as throughput and latency.

To optimize query parallelism techniques, substantial workloads are required with specific query plans and customized output size for each operator (denoted as cardinality constraint). To this end, a rich body of query-aware database generators (QAG) are proposed. However, the complex data dependencies hidden behind queries make previous QAGs suffer from deficiencies in supporting complex operators and controlling the generation errors. In this paper, we design a new generator Mirage supporting well for complex operators with low error bounds for cardinality constraints. First, Mirage leverages Query Rewriting and Set Transforming Rules to decouple dependencies between key and non-key columns, which could help generate each of them individually. Then, for the non-key columns, Mirage abstracts cardinality constraints of operators as placement requirements within each column's domain, and further models the generation problem as a classic bin packing problem. Finally, for the key columns, Mirage proposes a uniform representation of join cardinality constraints for all types of PK-FK joins and partitions the data according to the matching status between PK and F K columns. Then, it formulates the key population as a Constraint Programming problem, which can be solved by an existing CP Solver. The experiments show that Mirage conquers all previous work in either operator support or generation error.

Non- Volatile Memory (NVM) offers low-latency, non-volatility, and byte-addressability, positioning it as a highly promising device for database performance enhancement. Cur-rent research primarily focuses on utilizing LSM-Tree in con-junction with NVM to reduce write amplification and alleviate write stall issues. However, the comprehensive potential of NVM in simultaneously augmenting both read and write performances remains underexplored. And the previous NVM-enhanced LSM-Tree also ignores the sensitivity of NVM to small-grained random reads and writes, which we believe is the key to further improving read and write performance. To address these issues, we propose BushStore, an innovative LSM-Tree variant specifically optimized for NVM. BushStore is designed with a three-level architecture, where the higher levels of BushStore contain a group of immutable, non-clustered B+Trees, replacing traditional SSTables. By storing the non-leaf nodes in the DRAM and the leaf nodes in NVM, and separating the data pages from the indexes, these B+Trees are able to exhibit high performance for diverse read and write operations. Our approach encompasses four key techniques to significantly boost system efficiency: First, we develop novel data structures that localize read/write operations to confined NVM areas, enhancing access speed. Second, we optimize the key-value data handling during flushing and compaction phases, leveraging the superior scanning and sequantial writing capabilities of B+Trees to ex-pedite write and compaction processes. Third, we dynamically adjust the B+Tree sizes, enabling a balanced and optimized flushing and compaction process, thereby improving overall write performance. Fourth, we implement a lazy-delete Cuckoo filtering and lazy-persistent allocation strategy to accelerate query and compaction processes. Evaluations show that BushStore exhibits high performance and scalability under synthetic and real work-loads, and achieves an average performance improvement of 3.3x in random write throughput and 4.3x in random read throughput compared to the state-of-the-art MioDB system.

Functionalities of a database system are co-designed and jointly maintain the database performance. Each function-ality usually has its own metrics to evaluate its state. Previous knobs tuning methods regard the database system as a black box and aim to automatically find the optimal configurations by collecting and observing the overall performance data (e.g., transaction throughput per second) under various configuration knobs. However, if a functionality is not running in the tuning phase, its knobs irrelevant to performance changes can also be tuned by existing tools and potential risks would be introduced. To resolve this problem, we design a database knob tuning framework to support functionality-aware knobs tuning. It uses multitask learning to take the database overall performance as the objective of main learning task, and each function module as a separate learning task. This framework enhances the tuning results through learning the relationships between different tasks, and avoids adjusting irrelevant knobs by perceiving the status of functionalities. We validate its generalizability on OceanBase and PostgreSQL. Experimental results show that better performances were achieved on the overall performance and the metrics of various functionalities.

In a geo-distributed database, data shards and their respective replicas are deployed in distinct datacenters across multiple regions, enabling regional-level disaster recovery and the ability to serve global users locally. However, transaction processing in geo-distributed databases requires multiple cross-region communications, especially during the commit phase, which can significantly impact system performance. To optimize the performance of geo-distributed transactions, we propose Decentralized Two-phase Commit (D2PC), a new transaction commit protocol aiming to minimize the negative impact of cross-region communication. In D2PC, we employ multiple co-coordinators that perform commit coordination in parallel. Each co-coordinator is responsible for collecting 2PC votes and making a PreCommit decision in its local region. This approach allows for the concurrent invocation of multiple cross-region network round trips, and each region can end its concurrency control locally before replication is complete, thus significantly reducing the chances of blocking and enhancing system concurrency. Moreover, we propose the bypass leader replication reply method, leveraging decentralized co-coordinators to bypass the leader for message transmission, thereby reducing the commit latency. Experimental results have demonstrated that D2PC can reduce commit latency by 43% and improve throughput by up to 2.43 × compared to the geo-distributed transaction processing methods based on 2PC.

The log-structured merge tree (LSM-tree) has been widely adopted as a backbone of modern key-value stores. However, the multiple exponentially increased levels of LSM-tree makes it suffer from high write amplification. Existing studies often improve the write performance by sacrificing the read performance, which is inefficient to make trade-offs between the update and search efficiency. In this paper, we exploit nonvolatile memory (NVM) to address the write amplification issue for systems with NVM-SSD hybrid storage, and further propose a reinforcement learning method to navigate between update and search efficiency on the varying workloads. Specifically, we first propose a lightweight hot data identification method to efficiently capture access recency as well as frequency in NVM with relative large capacity. On this basis, we can eliminate different versions of frequently updated data in high-performance NVM without pushing them to SSD. To improve the data access locality and facilitate fine-grained index tuning in each level, we devise a virtual-split method to partition the key space gradually without extra write amplification. Finally, we propose a cost based Q-learning algorithm to adaptively tune the data organizations of each partition according to the changing access patterns. Experimental results show that our approach outperforms existing methods by up to 2.67×.

Isolation Levels (IL) act as correct contracts between applications and database management systems (DBMSs). The complex code logic and concurrent interactions among transactions make it a hard problem to expose violations of various ILs stated by DBMSs. With the recent proliferation of new DBMSs, especially the cloud ones, there is an urgent demand for a general way to verify various ILs. The core challenges come from the requirements of: (a) lightweight (verifying without modifying the application logic in workloads and the source code of DBMSs), (b) generality (verifying various ILs), and (c) efficiency (performing efficient verification on a long running workload). For lightweight, we propose to deduce transaction dependencies based on time intervals of operations collected from client-sides without touching the source code of DBMSs. For generality, based on a thorough analysis of existing concurrency control protocols, we summarize and abstract four mechanisms which can implement ILs in all commercial DBMSs we have investigated. For efficiency, we design a two-level pipeline to organize and sort massive time intervals in a time and memory conservative way; we propose a mechanism-mirrored verification to simulate the concurrency control protocols implemented in DBMSs for high throughputs. Leopard outperforms existing methods by up to 114× in verification time with a relative small memory usage. In practice, Leopard has a superpower to verify various ILs on any workload running on all commercial DBMSs. Moreover, it has successfully discovered 23 bugs that cannot be found by other existing methods.

In this paper, we present PM-Blade, an LSM-tree structured storage augmented with persistent memory (or non-volatile memory). PM-Blade utilizes persistent memory to optimize read performance and reduce write amplification, which are essential to Meituan’s online retail applications. Distinguished from existing designs, PM-Blade leverages persistent memory to drastically increase the capacity of the level-0 layer of LSM-tree. An enlarged level-0 layer allows a large amount of hot or warm data to be retained in persistent memory, enabling high read performance. At the same time, it works as a large write buffer that absorbs write amplification. To make the best of the design, we devised an internal compaction method and used a cost-based compaction strategy to maximize the utility of the level-0 layer. We implemented the compaction method using coroutines to improve its efficiency and resource utilization. We evaluated PM-Blade through extensive experiments, in which PM-Blade outperformed several open-source alternatives on standard benchmarks and a real-world workload of Meituan.

Distributed shared buffer (DSB) is a well-known solution to support multi-master database systems. DSB involves controlling access to shared data among different nodes through a distributed shared buffer and lock-based cache coherence protocols. Existing DSB implementations resolve conflicts at the page level and lack the flexibility required by modern cloud database systems. Authors present HyBuffer which mixes rows and pages in the distributed shared buffer. It enables multiple masters to independently modify different rows on the same page, thereby enhancing concurrency and performance. HyBuffer adopts the hybrid design to track the location information of cached data. A centralized node maintains page locations indicating which masters have cached which pages, and the record locations of a cached page are maintained by the master which has cached this page. This design eliminates the need to redistribute metadata when dynamically adding or removing masters. Experimental results demonstrate that HyBuffer achieves better scalability and performance compared to existing approaches.

In this paper, we seek to perform a rigorous experimental study of main-memory hash joins in storage class memory (SCM). In particular, we perform a design space exploration in real SCM for two state-of-the-art join algorithms: partitioned hash join (PHJ) and non-partitioned hash join (NPHJ), and identify the most crucial factors to implement an SCM-friendly join. Moreover, we present a rigorous evaluation with a broad spectrum of workloads for both joins and provide an in-depth analysis for choosing the most suitable algorithm in real SCM environment. With the most extensive experimental analysis up-to-date, we maintain that although there is no one universal winner in all scenarios, PHJ is generally superior to NPHJ in real SCM.

Storage engines for analytic databases are being developed to be setup with different devices for both cost price and performance considerations. Persistent Memory(PMem), as a novel storage device, also provides a new promising option for the hybrid storage. In this demonstration, we introduce Hockey, an efficient columnar storage engine designed for hybrid PMem-SSD storage. We first go through the design of the system and introduce how the data and meta data are structured and accessed on the PMem. The system's data placement strategy on hybrid storage is then presented. To highlight Hockey's design concerns for the hybrid storage as well as its superior performance, we develop a visual interface to demonstrate the system through three scenarios.

Multi-master architecture is desirable for cloud databases in supporting large-scale transaction processing. To enable concurrent transaction execution on multiple computing nodes, we need an efficient transaction commit protocol on the storage layer that ensures ACID as well as consensus among replicas. A leader-based protocol is easy to implement. However, it faces the single-node bottleneck and suffers from high transaction latency in cross-region deployment. While a leaderless protocol can achieve a higher degree of parallelism, it is inefficient in resolving conflicts. This paper proposes the semi-leader protocol, which is a new type of transaction commit protocol for multi-master transaction processing. In a nutshell, the semi-leader protocol is a hybrid protocol that offers separate commit paths for conflicting transactions and non-conflicting transactions. A centralized node, known as the sequencer, is employed to perform precise conflict resolution for conflicting transactions, while non-conflicting transactions can be committed timely in a decentralized manner. Based on the semi-leader protocol, we designed Starry, a multi-master transaction processing mechanism. Experimental results demonstrate that Starry is 1.4× and 4.21× as performant as the leaderless and leader-based protocols respectively in throughput. When dealing with high-contention workloads, Starry can significantly reduce the abort rates.

Distributed shared memory abstraction can coordinate a cluster of machine nodes to empower performance-critical queries with the scalable memory space and abundant parallelism. But to deploy the query under such an abstraction, the general execution model just makes operators expressed as multiple subtasks and sequentially schedule them in parallel, while neglecting those vital dependencies between subtasks and data. In this paper, we conduct the in-depth researches about the issues (i.e., low CPU Utilization and poor data locality) raised by the ignorance of dependencies, and then propose a dependency-aware query execution model called Jasmine, which can (i) help users explicitly declare the dependencies and (ii) take these declared dependencies into the consideration of execution to address the issues. We invite our audience to use the rich graphical interfaces to interact with Jasmine to explore the dependency-aware query execution on distributed shared memory.

Modern distributed database systems scale horizontally by partitioning their data across a large number of nodes. Most such systems build their transactional layers on a replication layer, employing a consensus protocol to ensure data consistency to achieve fault tolerance. Synchronization among replicated state machines thus becomes a significant overhead of transaction processing. Without careful design, synchronization could amplify transactions' lock duration and impair the system's scalability. Speculative techniques, such as Controlled Lock Violation (CLV) and Early Lock Release (ELR), prove useful in shortening lock's critical path and boosting transaction processing performance. To use these techniques to optimize geo-replicated distributed databases(GDDB) is an intuitive idea. This paper shows that a naive application of speculation is often unhelpful in a distributed environment. Instead, we introduce Distributed Lock Violation (DLV), a specialized speculative technique for geo-replicated distributed databases. DLV can achieve good performance without incurring severe side effects.

To support efficiently and continuously loading large scale historical data into a distributed data management system (DDMS), it needs to balance the bulk workload across machines. The fundamental problem is to estimate the time used to merge currently loaded data (defined as incremental data) into previously loaded data (defined as baseline data) for each partition, referred to as partition merge. In this work, we present a learning-based framework, referred to as LeaBalancer, to balance the merge loads across cluster nodes. In the situation where the system is scheduled to have regular bulk loading tasks, LeaBalancer can learn to predict the partition merge time from the merge logs generated by previous bulk loadings. Nevertheless, it is still difficult to balance the bulk workload only using a single plan phase because of inaccurate merge time prediction or other in-progress heavy workloads during the bulk loading. To resolve this problem, we design a multi-round balancing strategy, and at the beginning of each round LeaBalancer carefully chooses partitions for migration according to the remaining merge loads in each node. Experimental results show that LeaBalancer can adaptively perform load balance under various settings.

Cloud backup is becoming the preferred way for users to support disaster recovery. In addition to its convenience, users are deeply concerned about reducing storage costs in the face of large-scale backup data. Data deduplication is an effective method for backup storage. However, current deduplicate methods lack the utilization of cloud resources to provide scalable backup service for cloud backup users, and cannot meet the biased preference for different backup versions. For new backup versions, users want higher deduplicate and restore speed to reduce the waiting time. Conversely, reducing storage costs is more necessary for old backup versions.In this paper, we present SLIMSTORE, with a cloud-based deduplication architecture that disassembles the system into a storage layer and a computing layer to support elastic utilization of cloud resources. We propose two types of processing nodes with different design focuses to meet the needs of cloud-based backup. The L-node exploits locality and similarity, and adopts a history-aware strategy to provide fast online deduplication service. L-node also optimizes online restoration to realize high restore efficiency. Meanwhile, the G-node provides exact deduplication offline for the old versions, and helps the restore performance of the new versions by optimizing their physical storage. We compare SLIMSTORE with some state-of-art deduplicate and restore methods. Experimental results show that SLIMSTORE can achieve fast deduplication, efficient restoration, and effective space reduction. Furthermore, SLIMSTORE attains scalable deduplication and restoration.

Abstract Evaluation of interactive search systems and study of users’ struggling search behaviors require a significant number of search tasks. However, generation of such tasks is inherently difficult, as each task is supposed to trigger struggling search behavior rather than simple search behavior. To the best of our knowledge, there has not been a commonly used task set for research in struggling search. Moreover, the everchanging landscape of information needs would render old task sets less ideal if not unusable for evaluation. To deal with this problem, we propose a crowd-powered task generation method and develop a platform to efficiently generate struggling search tasks on basis of online wikis such as Wikipedia. Our experiments and analysis show that the generated tasks are qualified to emulate struggling search behaviors consisting of “repeated similar queries” and “quick-back clicks”; tasks of diverse topics, high quality and difficulty can be created using this method. For benefit of the community, we publicly released a task generation platform TaskGenie, a task set of 80 topically diverse struggling search tasks with “baselines,” and the corresponding anonymized user behavior logs.

Abstract Intra-query fault tolerance has increasingly been a concern for online analytical processing, as more and more enterprises migrate data analytical systems from mainframes to commodity computers. Most massive parallel processing (MPP) databases do not support intra-query fault tolerance. They may suffer from prolonged query latency when running on unreliable commodity clusters. While SQL-on-Hadoop systems can utilize the fault tolerance support of low-level frameworks, such as MapReduce and Spark, their cost-effectiveness is not always acceptable. In this paper, we propose a smart intra-query fault tolerance (SIFT) mechanism for MPP databases. SIFT achieves fault tolerance by performing checkpointing, i.e., materializing intermediate results of selected operators. Different from existing approaches, SIFT aims at promoting query success rate within a given time. To achieve its goal, it needs to: (1) minimize query rerunning time after encountering failures and (2) introduce as less checkpointing overhead as possible. To evaluate SIFT in real-world MPP database systems, we implemented it in Greenplum. The experimental results indicate that it can improve success rate of query processing effectively, especially when working with unreliable hardware.

Interactive information-seeking systems are designed to help users with their struggling during the searching for complex fact checking tasks, where a searcher may have clear information needs but experience difficulty in collecting required information. However, evaluation and comparison of such systems requires a large number of such tasks, which are difficult to collect or make up. To the best of our knowledge, there has not been a commonly used task set for evaluating struggling search of this kind. This paper proposes a convenient method to generate complex fact checking tasks. Each of the generated task has a clearly defined goal, which however takes an average searcher a significant amount of effort to reach. We conducted lab user studies to verify the feasibility of this method. The results confirmed its feasibility and efficiency.

User-centered approaches have been extensively studied and used in the area of struggling search. Related research has targeted key aspects of users such as user satisfaction or frustration, and search success or failure, using a variety of experimental methods including laboratory user studies, in-situ explicit feedback from searchers and by using crowdsourcing. Such studies are valuable in advancing the understanding of search difficulty from a user's perspective, and yield insights that can directly improve search systems and their evaluation. However, little is known about how user moods influence their interactions with a search system or their perception of struggling. In this work, we show that a user's own mood. can systematically bias the user's perception, and experience while interacting with a search system and trying to satisfy an information need. People who are in activated-(un)pleasant moods tend to issue more queries than people in deactivated or neutral moods. Those in an unpleasant mood perceive a higher level of difficulty. Our insights extend the current understanding of struggling search tasks and have important implications on the design and evaluation of search systems supporting such tasks.

In this demo paper, we introduce LogCanvas, a platform for user search history visualization.Different from the existing visualization tools, LogCanvas focuses on helping users re-construct the semantic relationship among their search activities. LogCanvas segments a user's search history into different sessions and generates a knowledge graph to represent the information exploration process in each session.A knowledge graph is composed of the most important concepts or entities discovered by each search query as well as their relationships. It thus captures the semantic relationship among the queries.LogCanvas offers a session timeline viewer and a snippets viewer to enable users to re-find their previous search results efficiently. LogCanvas also provides a collaborative perspective to support a group of users in sharing search results and experience.

Snapshot Isolation (SI) is a widely adopted concurrency control mechanism in database systems, which utilizes timestamps to resolve conflicts between transactions. However, centralized allocation of timestamps is a potential bottleneck for parallel transaction management. This bottleneck is becoming increasingly visible with the rapidly growing degree of parallelism of today's computing platforms. This paper introduces Posterior Snapshot Isolation (PostSI), an SI mechanism that allows transactions to determine their timestamps autonomously, without relying on centralized coordination. As such, PostSI can scale well, rendering it suitable for various multi-core and MPP platforms. Extensive experiments are conducted to demonstrate its advantage over existing approaches.

High-frequency trading (HFT) has always been welcomed because it benefits not only personal benefits but also the whole social welfare. While the recent advance of portfolio selection in HFT market enables to bring about more profit, it yields much contended OLTP workloads. Featuring exploiting the abundant parallelism, transaction pipeline, the state-of-the-art concurrency control (CC) mechanism, however, suffers from limited concurrency confronted with HFT workloads. Its variants that enable more parallel execution by leveraging fine-grained contention information also take little effect. To solve this problem, we for the first time observe and formulate the source of restricted concurrency as harmful ordering of transaction statements. To resolve harmful ordering, we propose PARE, a pipeline-aware reordered execution, to improve application performance by rearranging statements in order of their degrees of contention. In concrete, two mechanisms are devised to ensure the correctness of statement rearrangement and identify the degrees of contention of statements, respectively. We also study the off-line reordering problem. We prove that this problem is NP-hard and present an off-line reordering approach to approximate the optimal reordering strategy. Experiment results show that PARE can improve transaction throughput and reduce transaction latency on HFT applications by up to an order of magnitude than the state-of-the-art CC mechanism.

Large-scale knowledge graphs (KGs) contain massive entities and abundant relations among the entities. Data exploration over KGs allows users to browse the attributes of entities as well as the relations among entities. It therefore provides a good way of learning the structure and coverage of KGs. In this paper, we introduce a system called SEED that is designed to support entity-oriented exploration in large-scale KGs, based on retrieving similar entities of some seed entities as well as their semantic relations that show how entities are similar to each other. A by-product of entity exploration in SEED is to facilitate discovering the deficiency of KGs, so that the detected bugs can be easily fixed by users as they explore the KGs.

Denormalization is a common tactic for enhancing performance of data warehouses. However, it is rarely used in main memory databases, which regards storage space as scarce resource. In this paper, we demonstrate that MMDB can actually benefit from the strategy of denormalization. We have created A-Store, a prototypical main-memory database system customized for star and snowflake schemas, which applies the strategy of denormalization to achieve highly efficient OLAP. Instead of resorting to fully materialized denormalization, A-Store applies a method called virtual denomalization, which allows query processing to be performed in a denormalized way, while without incurring additional space consumption.

With the proliferation of graph-based applications, such as social network management and Web structure mining, update-intensive graph databases have become an important component of today’s data management platforms. Several techniques have been recently proposed to exploit locality on both data organization and computational model in graph databases. However, little investigation has been conducted on buffer management of graph databases. To the best of our knowledge, current buffer managers of graph databases suffer performance loss caused by unnecessary random I/O access. To solve this problem, we develop a novel batch replacement policy for buffer management. This policy enables us to maximally exploit sequential I/O to improve the performance of graph database. However, trivial solution produces impractical maintenance for replacement plan with maximal sequential I/O. To enable the policy, we first devise a segment tree-based buffer manager to efficiently maintain a optimal replacement plan. Unfortunately, segment tree-based solution becomes bottleneck in multi-core environment. To remedy this weakness, a B-tree-based buffer manager is further proposed. Extensive experiments on real-world and synthetic datasets demonstrate the superiority of our method.

Denormalization is a common tactic for enhancing performance of data warehouses, though its side-effect is quite obvious. Besides being confronted with update abnormality, denormalization has to consume additional storage space. As a result, this tactic is rarely used in main memory databases, which regards storage space, i.e., RAM, as scarce resource. Nevertheless, our research reveals that main memory database can benefit enormously from denormalization, as it is able to remarkably simplify the query processing plans and reduce the computation cost. In this paper, we present A-Store, a main memory OLAP engine customized for star/snowflake schemas. Instead of generating fully materialized denormalization, A-Store resorts to virtual denormalization by treating array indexes as primary keys. This design allows us to harvest the benefit of denormalization without sacrificing additional RAM space. A-Store uses a generic query processing model for all SPJGA queries. It applies a number of state-of-the-art optimization methods, such as vectorized scan and aggregation, to achieve superior performance. Our experiments show that A-Store outperforms the most prestigious MMDB systems significantly in star/snowflake schema based query processing.

In recent years, a number of open databases have emerged on the Web, providing Web users with platforms to collaboratively create structured information. As these databases are intended to accommodate heterogeneous information and knowledge, they usually comprise a very large schema and billions of instances. Browsing and searching data on such a scale is not an easy task for a Web user. In this context, interactive query construction offers an intuitive interface for novice users to retrieve information from databases neither requiring any knowledge of structured query languages, nor any prior knowledge of the database schema. However, the existing mechanisms do not scale well on large scale datasets. This paper presents a set of techniques to boost the scalability of interactive query construction, from the perspective of both, user interaction cost and performance. We connect an abstract ontology layer to the database schema to shorten the process of user-computer interaction. We also introduce a search mechanism to enable efficient exploration of query interpretation spaces over large scale data. Extensive experiments show that our approach scales well on Freebase - an open database containing more than 7,000 relational tables in more than 100 domains.

This paper considers top-k retrieval using Conditional Preference Network (CP-Net). As a model for expressing user preferences on multiple mutually correlated attributes, CP-Net is of great interest for decision support systems. However, little work has addressed how to conduct efficient data retrieval using CP-Nets. This paper presents an approach to efficiently retrieve the most preferred data items based on a user's CP-Net. The proposed approach consists of a top-k algorithm and an indexing scheme. We conducted extensive experiments to compare our approach against a baseline top-k method - sequential scan. The results show that our approach outperform sequential scan in several circumstances.

This paper presents an approach based on casual graph to optimize the task hierarchies for Hierarchical Reinforcement Learning (HRL). We conducted experiments to show that the resulting task hierarchies can improve effectiveness of reinforcement leaning.

Databases enable users to precisely express their informational needs using structured queries. However, database query construction is a laborious and error-prone process, which cannot be performed well by most end users. Keyword search alleviates the usability problem at the price of query expressiveness. As keyword search algorithms do not differentiate between the possible informational needs represented by a keyword query, users may not receive adequate results. This paper presents IQP- a novel approach to bridge the gap between usability of keyword search and expressiveness of database queries. IQPenables a user to start with an arbitrary keyword query and incrementally refine it into a structured query through an interactive interface. The enabling techniques of IQPinclude: 1) a probabilistic framework for incremental query construction; 2) a probabilistic model to assess the possible informational needs represented by a keyword query; 3) an algorithm to obtain the optimal query construction process. This paper presents the detailed design of IQP, and demonstrates its effectiveness and scalability through experiments over real-world data and a user study.

This paper presents IQP - a novel approach to bridge the gap between usability of keyword search and expressiveness of database queries. IQP enables a user to start with an arbitrary keyword query and incrementally refine it into a structured query through an interactive interface. The enabling techniques of IQP include: (1) a conceptual framework for incremental query construction; (2) a probabilistic model to assess the possible informational needs represented by a keyword query; (3) an algorithm to perform an optimal query construction.

Keyword queries over structured databases are notoriously ambiguous. No single interpretation of a keyword query can satisfy all users, and multiple interpretations may yield overlapping results. This paper proposes a scheme to balance the relevance and novelty of keyword search results over structured databases. Firstly, we present a probabilistic model which effectively ranks the possible interpretations of a keyword query over structured data. Then, we introduce a scheme to diversify the search results by re-ranking query interpretations, taking into account redundancy of query results. Finally, we propose α-nDCG-W and WS-recall, an adaptation of α-nDCG and S-recall metrics, taking into account graded relevance of subtopics. Our evaluation on two real-world datasets demonstrates that search results obtained using the proposed diversification algorithms better characterize possible answers available in the database than the results of the initial relevance ranking.

In contrast to classical databases and IR systems, real-world information systems have to deal increasingly with very vague and diverse structures for information management and storage that cannot be adequately handled yet. While current object-relational database systems require clear and unified data schemas, IR systems usually ignore the structured information completely. Malleable schemas, as recently introduced, provide a novel way to deal with vagueness, ambiguity and diversity by incorporating imprecise and overlapping definitions of data structures. In this paper, we propose a novel query relaxation scheme that enables users to find best matching information by exploiting malleable schemas to effectively query vaguely structured information. Our scheme utilizes duplicates in differently described data sets to discover the correlations within a malleable schema, and then uses these correlations to appropriately relax the users’ queries. In addition, it ranks results of the relaxed query according to their respective probability of satisfying the original query’s intent. We have implemented the scheme and conducted extensive experiments with real-world data to confirm its performance and practicality.

To support ubiquitous computing, the underlying data have to be persistent and available anywhere-anytime. The data thus have to migrate from devices local to individual computers, to shared storage volumes that are accessible over open network. This potentially exposes the data to heightened security risks. We propose two mechanisms, in the context of a steganographic file system, to mitigate the risk of attacks initiated through analyzing data accesses from user applications. The first mechanism is intended to counter attempts to locate data through updates in between snapshots - in short, update analysis. The second mechanism prevents traffic analysis - identifying data from I/O traffic patterns. We have implemented the first mechanism on Linux and conducted experiments to demonstrate its effectiveness and practicality. Simulation results on the second mechanism also show its potential for real world applications.

While user access control and encryption can protect valuable data from passive observers, these techniques leave visible ciphertexts that are likely to alert an active adversary to the existence of the data. We introduce StegFD, a steganographic file driver that securely hides user-selected files in a file system so that, without the corresponding access keys, an attacker would not be able to deduce their existence. Unlike other steganographic schemes proposed previously, our construction satisfies the prerequisites of a practical file system in ensuring the integrity of the files and maintaining efficient space utilization. We also propose two schemes for implementing steganographic B-trees within a StegFD volume. We have completed an implementation on Linux, and results of the experiment confirm that StegFD achieves an order of magnitude improvements in performance and/or space utilization over the existing schemes.

While user access control and encryption can protect valuable data from passive observers, those techniques leave visible ciphertexts that are likely to alert an active adversary to the existence of the data, who can then compel an authorized user to disclose it. We introduce StegFS, a steganographic file system that aims to overcome that weakness by offering plausible deniability to owners of protected files. StegFS securely hides user-selected files in a file system so that, without the corresponding access keys, an attacker would not be able to deduce their existence, even if the attacker is thoroughly familiar with the implementation of the file system and has gained full access to it. Unlike previous steganographic schemes, our construction satisfies the prerequisites of a practical file system in ensuring integrity of the files and maintaining efficient space utilization. We have completed an implementation on Linux, and experiment results confirm that StegFS achieves an order of magnitude improvements in performance and/or space utilization over the existing schemes.