Deploying machine learning (ML) inference pipelines in databases become increasingly prevalent in many applications. In order to avoid data transfer between the database and ML runtimes, existing ML2SQL frameworks parse ML pipelines to a graph consisting of ML operators and then translate it into pure SQL. Nevertheless, they typically rewrite the graph without operator fusion or only consider the fusion between certain operators such as StandardScaler and tree inference. However, there are various operators in ML pipelines, which have rich fusion opportunities between each other. To fully exploit operator fusion for graph rewriting, we classify widely used ML operators and design fusion rules driven by their characteristics. Moreover, rewriting the original graph by fusion rules produces candidate graphs that generate SQLs with different execution time. We employ an enumeration-based strategy to search for the graph with the lowest cost. However, this strategy may suffer from the combination explosion on search space for complex ML pipelines. To reduce this space, we propose a greedy-based strategy by exploiting the independence among ML operators. We implement a novel ML2SQL framework as a portable plugin for databases, namely Craftsman. Our experimental evaluations show that, in comparison to the existing approaches, Craftsman generates efficient SQL queries which achieves an average speedup of 2.9x on popular databases such as DuckDB.

Popular LSM-tree based key-value stores suffer from suboptimal and unpredictable performance due to write amplification and write stalls that cause application performance to periodically drop to nearly zero. Our preliminary experimental studies reveal that (1) write stalls mainly stem from the significantly large amount of data involved in each compaction between$L_{0}$-$L_{1}$(i.e., the first two levels of LSM-tree), and (2) write amplification increases with the depth of LSM-trees. Existing work mainly focus on reducing write amplification, while only a couple of them target mitigating write stalls. In this paper, we exploit unique features of non-volatile memory (NVM) to address these two limitations and propose TriangleKV, a new LSM-tree based persistent KV store with multi-tier DRAM-NVM-SSD storage. TriangleKV's design principles include performing smaller and cheaper$L_{0}$-$L_{1}$compaction to reduce write stalls while reducing the depth of LSM-trees to mitigate write amplification. To this end, four novel techniques are proposed. First, we relocate and manage the$L_{0}$level in NVM with our proposedtriangle container. Second, the newright-angle side compactionis devised to compact$L_{0}$to$L_{1}$at fine-grained key ranges, thus substantially reducing the amount of compaction data. Third, TriangleKV increases the width of each level to decrease the depth of LSM-trees thus mitigating write amplification. Finally, thecross-row hint searchis introduced for the triangle container to keep adequate read performance. We implement TriangleKV based on MatrixKV and evaluate it on a hybrid DRAM/NVM/SSD system using Intel's latest 3D Xpoint NVM device Optane DC PMM. Evaluation results show that, with the same amount of NVM, TriangleKV outperforms RocksDB, NoveLSM and MatrixKV in 99th-percentile latencies by$5.5\times$,$2.1\times$and$1.1\times$, and random write throughput by$4.9\times$,$3.5\times$and$1.4\times$respectively.

To leverage the larger-than-DRAM capacity and close-to-DRAM performance of persistent memory (PM) to build future memory systems, more scalable and efficient indexing structures are of paramount importance. However, as we evaluate existing PM indexing structures, we find that (1) both ordered and unordered indexing structures cannot support efficiently all KV operation types, i.e., Put, Get, Delete and Scan, and (2) the majority of indexes scale poorly as the PM capacity and dataset increases, i.e., the decreasing throughput of ordered indexes with the growth of dataset and the blocking of foreground requests by costly hash resizing of unordered indexes. To provide better operational efficiency on both point accesses and range queries for persistent memory in the ever-increasing volume of data, this article proposes ComboTree, a three-tiered indexing structure with a sorted key space. In ComboTree, we break the global B+Tree into multiple low height B+Trees (Tier C) and arrange them with a sorted array (Tier B). Further, we accelerate the lookup of the sorted array by cumulative distribution function (Tier A). Last but not least, a background resizing policy is proposed to avoid performance degradation when the capacity of the ComboTree grows. We implement and evaluate ComboTree on Intel’s Optane DCPMM. Test results show that ComboTree delivers$2.1\times -3.6\times$put throughput and$1.5\times -2.1\times$get throughput of the state-of-art sorted indexes. Furthermore, ComboTree is$1.27\times$faster than the efficient B+Tree variant in various scan granularities, and it is open-sourced1.

Persistent key-value (KV) stores are mainly designed based on the Log-Structured Merge-tree (LSM-tree), which suffer from large read and write amplifications, especially when KV stores grow in size. Existing design optimizations for LSM-tree-based KV stores often make certain trade-offs and fail to simultaneously improve both the read and write performance on large KV stores without sacrificing scan performance. We design UniKV, which unifies the key design ideas of hash indexing and the LSM-tree in a single system. Specifically, UniKV leverages data locality to differentiate the indexing management of KV pairs. It also develops multiple techniques to tackle the issues caused by unifying the indexing techniques, so as to simultaneously improve the performance in reads, writes, and scans. Experiments show that UniKV significantly outperforms several state-of-the-art KV stores (e.g., LevelDB, RocksDB, HyperLevelDB, and PebblesDB) in overall throughput under read-write mixed workloads.

Hybrid Transactional and Analytical Processing (HTAP) databases require processing transactional and analytical queries in isolation to remove the interference between them. To achieve this, it is necessary to maintain different replicas of data specified for the two types of queries. However, it is challenging to provide a consistent view for distributed replicas within a storage system, where analytical requests can efficiently read consistent and fresh data from transactional workloads at scale and with high availability. To meet this challenge, we propose extending replicated state machine-based consensus algorithms to provide consistent replicas for HTAP workloads. Based on this novel idea, we present a Raft-based HTAP database: TiDB. In the database, we design a multi-Raft storage system which consists of a row store and a column store. The row store is built based on the Raft algorithm. It is scalable to materialize updates from transactional requests with high availability. In particular, it asynchronously replicates Raft logs to learners which transform row format to column format for tuples, forming a real-time updatable column store. This column store allows analytical queries to efficiently read fresh and consistent data with strong isolation from transactions on the row store. Based on this storage system, we build an SQL engine to process large-scale distributed transactions and expensive analytical queries. The SQL engine optimally accesses row-format and column-format replicas of data. We also include a powerful analysis engine, TiSpark, to help TiDB connect to the Hadoop ecosystem. Comprehensive experiments show that TiDB achieves isolated high performance under CH-benCHmark, a benchmark focusing on HTAP workloads.

JPEG2000 has been accepted by The Society of Motion Picture and Television Engineers (SMPTE) as the image compression standard for the digital distribution of motion pictures. In JPEG2000, the biggest contribution to the coding performance comes from the Embedded Block Coding with Optimized Truncation (EBCOT), which is also the most time-consuming module by occupying almost 37% of the encoding time. There have been many research activities in the optimization of EBCOT on platforms like FPGA and VLSI, but on Graphics Processing Unit (GPU), a currently popular parallel computing platform in post-production of motion pictures, still few works have been done. This paper proposes a fine-granular parallel EBCOT by re-designing the highly serialized bit-plane coding to a parallel structure where the coding of all bits in a bit-plane could be performed in parallel, then the bit coding tasks can be distributed to the stream processors in GPU by taking advantage of the programming and memory model of CUDA. Experimental results show that our algorithms reveal 3 to 4 times computational speed improvement on an ordinary GPU compared to that on CPU.