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.

Inverted index is a basic tool in many data-intensive applications. Though numerous efforts have been made on efficient inverted index-based query processing, existing schemes do not achieve the expected performance for modern data centers, in which servers are equipped with powerful CPUs and relatively large memory. Through comprehensive measurement studies, we identify the root course is that the data formats for index representation make it unfeasible to design efficient query execution approaches on top of it, which results in poor parallel query support and waste CPU computation. Driven by the findings, we propose to reconcile the in-memory index as columnar structures. To enable this idea, we construct the compact columnar format (i.e., Cocoa) that achieves both desirable space efficiency and maintains the capability for efficient searching support. With Cocoa, we design an efficient query executing scheme that utilizes vectorized batch processing to avoid frequent branch prediction, as well as clause enumeration with pruning to save the overhead of intermediate batch materialization. We build an open-source system VeloSearch to embody our design; experimental results show that VeloSearch achieves ~30× better performance compared with state-of-the-art search libraries such as Lucene and Tantivy.

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.

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.

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.

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.

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.

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.

The rapid development of steel logistics industry still has not effectively address such issues as truck overload and order overdue as well as cargo overstock. One of the reasons lie in limited number of trucks for transporting large scale cargos. More importantly, traditional methods attend to distribute cargos to trucks with the aim of maximizing the loading of each truck. But they ignore the priority level of orders and the expiration date of cargos stored in the warehouses, which have critical influences on profits of steel logistics industry. Hence, it necessitates an appropriate cargo distribution mechanism under the precondition of limited transportation capacity resources, to guarantee the maximization of delivery proportion for high-priority cargos. Recently, tremendous logistics data has been produced and are being in constant increment hourly in steel logistics platform. However, there is no existing solution to transform such data into actionable scheme to improve cargo distributing effectiveness. This paper puts forward a system implementation of smart cargo loading plan decision framework (SCLPD for short) for steel logistics industry. Through analysis on numerous real data cargo loading plan and inventory of warehouse, some important rules related to cargo distribution process are extracted. Additionally, consider that different amounts of trucks arriving in different time periods, based on adaptive time window model, a two- layer searching mechanism consisting of a genetic algorithm and A* algorithm is designed to ensure global optimization of cargo loading plan for the trucks in all time periods. In our demonstration, we illustrate the procedure of matching for cargos and trucks in various time windows, and showcase the comparison experimental results between the traditional method and SCLPD by the measurement of delivery proportion for high- priority cargos. The effectiveness and practicality of SCLPD enables efficient cargo loading plan generation, to meet the real- world requirements from steel logistics platform.

To fully utilize the resources of a main memory database cluster, we additionally take the independent parallelism into account to parallelize multiple pipelines of one query. However, scheduling resources to multiple pipelines is an intractable problem. Traditional static approaches to this problem may lead to a serious waste of resources and suboptimal execution order of pipelines, because it is hard to predict the actual data distribution and fluctuating workloads at compile time. In response, we propose a dynamic scheduling algorithm, List with Filling and Preemption (LFPS), based on two novel techniques. (1) Adaptive filling improves resource utilization by issuing more extra pipelines to adaptively fill idle resource “holes” during execution. (2) Rank-based preemption strictly guarantees scheduling the pipelines on the critical path first at run time. Interestingly, the latter facilitates the former filling idle “holes” with best efforts to finish multiple pipelines as soon as possible. We implement LFPS in our prototype database system. Under the workloads of TPC-H, experiments show our work improves the finish time of parallelizable pipelines from one query up to 2.5X than a static approach and 2.1X than a serialized execution.

Location-aware services have become widely available on a variety of devices. The resulting fusion of spatio-textual data enables the kind of top-k query that takes into account both location proximity and text relevance. Considering both the misspellings in user input and the data quality issues of spatiotextual databases, it is necessary to support error-tolerant spatial keyword search for end-users. Existing studies mainly focused on set-based textual relevance, but they cannot find reasonable results when the input tokens are not exactly matched with those from records in the database. In this paper, we propose a novel framework to solve the problem of top-k location-aware similarity search with fuzzy token matching. We propose a hierarchical index HGR-Tree to capture signatures of both spatial and textual relevance. Based on such an index structure, we devise a best-first search algorithm to preferentially access nodes of HGR-Tree with more similar objects while those with dissimilar ones can be pruned. We further devise an incremental search strategy to reduce the overhead brought by supporting fuzzy token matching. Experimental results on real world POI datasets show that our framework outperforms state-of-the-art methods by one to two orders of magnitude.

Crowdsourced selection asks the crowd to select entities that satisfy a query condition, e.g., selecting the photos of people wearing sunglasses from a given set of photos. Existing studies focus on a single query predicate and in this paper we study the crowdsourced selection problem on multi-attribute data, e.g., selecting the female photos with dark eyes and wearing sunglasses. A straightforward method asks the crowd to answer every entity by checking every predicate in the query. Obviously, this method involves huge monetary cost. Instead, we can select an optimized predicate order and ask the crowd to answer the entities following the order. Since if an entity does not satisfy a predicate, we can prune this entity without needing to ask other predicates and thus this method can reduce the cost. There are two challenges in finding the optimized predicate order. The first is how to detect the predicate order and the second is to capture correlation among different predicates. To address this problem, we propose predicate order based framework to reduce monetary cost. Firstly, we define an expectation tree to store selectivities on predicates and estimate the best predicate order. In each iteration, we estimate the best predicate order from the expectation tree, and then choose a predicate as a question to ask the crowd. After getting the result of the current predicate, we choose next predicate to ask until we get the result. We will update the expectation tree using the answer obtained from the crowd and continue to the next iteration. We also study the problem of answering multiple queries simultaneously, and reduce its cost using the correlation between queries. Finally, we propose a confidence based method to improve the quality. The experiment result shows that our predicate order based algorithm is effective and can reduce cost significantly compared with baseline approaches.

Real-time urban traffic speed estimation provides significant benefits in many real-world applications. However, existing traffic information acquisition systems only obtain coarse-grained traffic information on a small number of roads but cannot acquire fine-grained traffic information on every road. To address this problem, in this paper we study the traffic speed estimation problem, which, given a budget K, identifies K roads (called seeds) where the real traffic speeds on these seeds can be obtained using crowdsourcing, and infers the speeds of other roads (called non-seed roads) based on the speeds of these seeds. This problem includes two sub-problems: (1) Speed Inference - How to accurately infer the speeds of the non-seed roads; (2) Seed Selection - How to effectively select high-quality seeds. It is rather challenging to estimate the traffic speed accurately, because the traffic changes dynamically and the changes are hard to be predicted as many possible factors can affect the traffic. To address these challenges, we propose effective algorithms to judiciously select high-quality seeds and devise inference models to infer the speeds of the non-seed roads. On the one hand, we observe that roads have correlations and correlated roads have similar traffic trend: the speeds of correlated roads rise or fall compared with their historical average speed simultaneously. We utilize this property and propose a two-step model to estimate the traffic speed. The first step adopts a graphical model to infer the traffic trend and the second step devises a hierarchical linear model to estimate the traffic speed based on the traffic trend. On the other hand, we formulate the seed selection problem, prove that it is NP-hard, and propose several greedy algorithms with approximation guarantees. Experimental results on two large real datasets show that our method outperforms baselines by 2 orders of magnitude in efficiency and 40% in estimation accuracy.

With the rapid development of mobile Internet technology, Internet users are shifting from desktop to mobile devices. Modern mobile devices (e.g., smartphones and tablets) are equipped with GPS, which can help users to easily obtain their locations, and location-based services (LBS) have been widely deployed. LBS users are generating more and more spatio-textual data which contains both textual descriptions and geographical locations. In user-generated data, a spatiotextual entity may have different representations, possibly due to GPS deviations or typographical errors [6], [2], and it calls for effective methods to integrate the spatio-textual data from different data sources. A spatio-textual similarity join is an important operation in spatio-textual data integration, which, given two sets of spatio-textual objects, finds all similar pairs from the two sets, where the similarity can be quantified by combining spatial proximity and textual relevancy. There are many applications in spatio-textual similarity joins, e.g., user recommendation in location-based social networks, image duplication detection using spatio-textual tags, spatio-textual advertising, and location-based market analysis [6], [2]. For example, a house rental agency (e.g., rent.com) wants to perform a similarity join on the spatio-textual data of house requirements from renters and the data of house properties from owners. For another example, a startup company, e.g., Factual (factual.com), crawls spatio-textual records to generate points of interest (POIs). As the records are from multiple sources and may contain many duplicates, It needs to run similarity joins to remove the duplicates.

Identifying the labels of points of interest (POIs), aka POI labelling, provides significant benefits in location-based services. However, the quality of raw labels manually added by users or generated by artificial algorithms cannot be guaranteed. Such low-quality labels decrease the usability and result in bad user experiences. In this paper, by observing that crowdsourcing is a best-fit for computer-hard tasks, we leverage crowdsourcing to improve the quality of POI labelling. To our best knowledge, this is the first work on crowdsourced POI labelling tasks. In particular, there are two sub-problems: (1) how to infer the correct labels for each POI based on workers' answers, and (2) how to effectively assign proper tasks to workers in order to make more accurate inference for next available workers. To address these two problems, we propose a framework consisting of an inference model and an online task assigner. The inference model measures the quality of a worker on a POI by elaborately exploiting (i) worker's inherent quality, (ii) the spatial distance between the worker and the POI, and (iii) the POI influence, which can provide reliable inference results once a worker submits an answer. As workers are dynamically coming, the online task assigner judiciously assigns proper tasks to them so as to benefit the inference. The inference model and task assigner work alternately to continuously improve the overall quality. We conduct extensive experiments on a real crowdsourcing platform, and the results on two real datasets show that our method significantly outperforms state-of-the-art approaches.

With the development of location-based services (LBS), LBS users are generating more and more spatio-textual data, e.g., checkins and attraction reviews. Since a spatio-textual entity may have different representations, possibly due to GPS deviations or typographical errors, it calls for effective methods to integrate the spatio-textual data from different data sources. In this paper, we study the problem of top-$k$spatio-textual similarity join (Topk-STJoin), which identifies the$k$most similar pairs from two spatio-textual data sets. One big challenge inTopk-STJoinis to efficiently identify the top-$k$similar pairs by considering both textual relevancy and spatial proximity. Traditional join algorithms that consider only one dimension (textual or spatial) are inefficient because they cannot utilize the pruning ability on the other dimension. To address this challenge, we propose a signature-based top-$k$join framework. We first generate a spatio-textual signature set for each object such that if two objects are in the top-$k$similar pairs, their signature sets must overlap. With this property, we can prune large numbers of dissimilar pairs without common signatures. We find that the order of accessing the signatures has a significant effect on the performance. So, we compute an upper bound for each signature and propose a best-first accessing method that preferentially accesses signatures with large upper bounds while those pairs with small upper bounds can be pruned. We prove the optimality of our best-first accessing method. Next, we optimize the spatio-textual signatures and propose progressive signatures to further improve the pruning power. Experimental results on real-world datasets show that our algorithm achieves high performance and good scalability, and significantly outperforms baseline approaches.

With the rapid progress of mobile Internet and the growing popularity of smartphones, location-aware publish/subscribe systems have recently attracted significant attention. Different from traditional content-based publish/subscribe, subscriptions registered by subscribers and messages published by publishers include both spatial information and textual descriptions, and messages should be delivered to relevant subscribers whose subscriptions have high relevancy to the messages. To evaluate the relevancy between spatio-textual messages and subscriptions, we should combine the spatial proximity and textual relevancy. Since subscribers have different preferences - some subscribers prefer messages with high spatial proximity and some subscribers pay more attention to messages with high textual relevancy, it calls for new location-aware publish/subscribe techniques to meet various needs from different subscribers. In this paper, we allow subscribers to parameterize their subscriptions and study the location-aware publish/subscribe problem on parameterized spatio-textual subscriptions. One big challenge is to achieve high performance. To meet this requirement, we propose a filter-verification framework to efficiently deliver messages to relevant subscribers. In the filter step, we devise effective filters to prune large numbers of irreverent results and obtain some candidates. In the verification step, we verify the candidates to generate the answers. We propose three effective filters by integrating prefix filtering and spatial pruning techniques. Experimental results show our method achieves higher performance and better quality than baseline approaches.

Existing route recommendation systems have two main weaknesses. First, they usually recommend the same route for all users and cannot help control traffic jam. Second, they do not take full advantage of real-time traffic to recommend the best routes. To address these two problems, we develop a real-time route recommendation system, called R3, aiming to provide users with the real-time-traffic-aware routes. R3 recommends diverse routes for different users to alleviate the traffic pressure. R3 utilizes historical taxi driving data and real-time traffic data and integrates them together to provide users with real-time route recommendation.