Publications

LakeHarbor: Making Structures First-Class Citizens in Data Lakes

Published in ICDE (International Conference on Data Engineering), 2024

This paper introduces LakeHarbor, a new data management paradigm that makes structures (e.g., indexes) first-class citizens in data lakes. The LakeHarbor paradigm enables a data lake system to flexibly construct structures based on registered access method functions and execute data processing jobs efficiently with the potential parallelism that the structures inherently hold by exploiting the functions while not sacrificing flexible data processing such as schema-on-read. This paper also presents ReDe, a prototype data processing engine that implements LakeHarbor, and a motivating evaluation and a case study of ReDe to explore the potential of LakeHarbor.

Recommended citation: H. Yamada, M. Kitsuregawa, and K. Goda. 2024. LakeHarbor: Making Structures First-Class Citizens in Data Lakes. In ICDE, 5583-5592.

The Case for Lazy Byzantine Fault Detection for Transactional Database Systems

Published in ICDCSW - International Conference on Distributed Computing Systems Workshops, 2023

Byzantine fault detection (BFD) techniques are promising approaches for better scalability and practicality, even though they cannot mask Byzantine faults like Byzantine fault tolerance (BFT) techniques. However, the existing BFD protocol for database systems has suffered from long latency since it synchronously makes an agreement on the order of transactions between replicas when executing the transactions. In this paper, we explore an alternative BFD approach for database systems, which defers the expensive agreement and detects Byzantine faults lazily rather than detecting them in real-time. We discuss the challenges and design overview of our approach. We also present preliminary experimental results showing the benefit of our approach.

Recommended citation: J. Nemoto and H. Yamada. 2023. The Case for Lazy Byzantine Fault Detection for Transactional Database Systems. In ICDCSW. 13-18. https://ieeexplore.ieee.org/document/10302986

ScalarDB: Universal Transaction Manager for Polystores

Published in PVLDB (VLDB) - Proceedings of the VLDB Endowment, 2023

This paper presents ScalarDB, a universal transaction manager that achieves distributed transactions across multiple disparate databases. ScalarDB provides a database-agnostic transaction manager on top of its database abstraction; thus, it achieves transactions spanning various databases without depending on the transactional capability of underlying databases. ScalarDB is based on several research works and extended to provide a strong correctness guarantee (i.e., strict serializability), further performance optimizations, and several critical mechanisms for productization. In this paper, we describe the design and implementation of ScalarDB. We also present evaluation results showing that ScalarDB achieves database-spanning transactions with reasonable performance and near-linear scalability without sacrificing correctness. Finally, we share some case studies and lessons learned while building and running ScalarDB.

Recommended citation: H. Yamada, T. Suzuki, Y. Ito, and J. Nemoto. 2023. ScalarDB: Universal Transaction Manager for Polystores. PVLDB 16, 12 (2023), 3768–3780. https://dl.acm.org/doi/10.14778/3611540.3611563

Nested Loops Revisited Again

Published in ICDE (International Conference on Data Engineering), 2023

Hash joins and sort-merge joins have been considered the algorithms of choice for analytical relational queries in most parallel database systems because of their performance robustness and ease of parallelization. On the other hand, nested loop joins have been considered less attractive and are conservatively used. In this paper, we revisit the potential of nested loop joins in a cluster environment. We focus on exploring the parallelism aspect of nested loop joins because there could still be space for improvement by fully exploiting the parallelism of current commodity hardware, which could handle more than thousands of concurrent IOs. We also introduce scalable massively-parallel execution as one of the approaches for achieving massive parallelism in nested loop joins to explore how it widens the potential benefit of nested loop joins. Finally, we discuss future research directions based on our exploration.

Recommended citation: H. Yamada, K. Goda, and M. Kitsuregawa. 2023. Nested Loops Revisited Again. In ICDE, 3708-3717. https://ieeexplore.ieee.org/document/10184629

Scalar DL: Scalable and Practical Byzantine Fault Detection for Transactional Database Systems

Published in PVLDB (VLDB) - Proceedings of the VLDB Endowment, 2022

This paper presents Scalar DL, a Byzantine fault detection (BFD) middleware for transactional database systems. Scalar DL manages two separately administered database replicas in a database system and can detect Byzantine faults in the database system as long as either replica is honest (not faulty). Unlike previous BFD works, Scalar DL executes non-conflicting transactions in parallel while preserving a correctness guarantee. Moreover, Scalar DL is database-agnostic middleware so that it achieves the detection capability in a database system without either modifying the databases or using database-specific mechanisms. Experimental results with YCSB and TPC-C show that Scalar DL outperforms a state-of-the-art BFD system by 3.5 to 10.6 times in throughput and works effectively on multiple database implementations. We also show that Scalar DL achieves near-linear (91%) scalability when the number of nodes composing each replica increases.

Recommended citation: H. Yamada and J. Nemoto. 2022. Scalar DL: Scalable and Practical Byzantine Fault Detection for Transactional Database Systems. PVLDB 15, 7 (2022), 1324-1336. https://dl.acm.org/doi/10.14778/3523210.3523212

Out-of-order Execution of Database Queries

Published in PVLDB (VLDB) - Proceedings of the VLDB Endowment, 2020

Intra-query parallelism is a key for database software to offer acceptable responsiveness for data-intensive queries. Many researchers have studied how to achieve greater execution parallelism for database queries. Partitioning is a representative approach, which divides a query into multiple sub-tasks and executes them in parallel. However, given a new query, optimal division is not necessarily obvious. Database software utilizes heuristic rules or statistical information to decide how to divide the query before execution. As yet another approach to achieve execution parallelism, this paper presents out-of-order database execution (OoODE), a massively-parallel query execution method to offer significant speedup for database queries consistently. OoODE dynamically decomposes query work by making the best use of the exact knowledge of the potential execution parallelism for each operation ready to be performed during query execution. With OoODE, the database software is allowed to automatically squeeze out the execution parallelism that the query inherently holds. Hence, for a wide spectrum of queries, OoODE performs significantly faster than the serial (non-parallelized) execution, while it performs better than or comparably with alternative parallelizing methods without the need for dividing the query before execution. This paper presents the experiments that we conducted using the prototyped database software and demonstrates that OoODE is two to three orders of magnitude faster than the serial execution, whereas it is substantially (up to 2.07 times) faster than the best achievable case of partitioning. Besides, OoODE performs two to four orders of magnitude faster than major DBMSs.

Recommended citation: K. Goda, Y. Hayamizu, H. Yamada, and M. Kitsuregawa. 2020. Out-of-Order Execution of Database Queries. PVLDB 13, 12 (2020), 3489–3501. https://dl.acm.org/doi/10.14778/3415478.3415571

What’s So Different about Blockchain? — Blockchain is a Probabilistic State Machine

Published in ICDCSW - International Conference on Distributed Computing Systems Workshops, 2016

Blockchain is a distributed timestamp server technology introduced for realization of Bitcoin, a digital cash system. It has been attracting much attention especially in the areas of financial and legal applications. But such applications would fail if they are designed without knowledge of the fundamental differences in blockchain from existing technology. We show that blockchain is a probabilistic state machine in which participants can never commit on decisions, we also show that this probabilistic nature is necessarily deduced from the condition where the number of participants remains unknown. This work provides useful abstractions to think about blockchain, and raises discussion for promoting the better use of the technology.

Recommended citation: K. Saito and H. Yamada. 2016. What’s So Different about Blockchain? — Blockchain is a Probabilistic State Machine. In ICDCSW. 168-175. https://ieeexplore.ieee.org/document/7756226

Scalable Online Index Construction with Multi-Core CPUs

Published in ADC - Australasian Database Conference, 2010

Inverted index is a core element of current text retrieval systems. They can be dynamically constructed using online indexing approaches in the environment which even a small delay in timeliness cannot be tolerated, and the index must always be queryable and up to date. Recently, efficient online index construction schemes have been proposed, however, previous works have not focused on scalability with the modern commodity hardware resources such as multi-core CPUs. In this paper, we propose a scalable online index construction method that better utilizes multi-core CPUs. Using experiments on 30 GB of web data, we demonstrate the efficiency of our method in practice, showing that it dramatically reduces online index construction time without sacrificing query performance.

Recommended citation: H. Yamada and M. Toyama. 2010. Scalable Online Index Construction with Multi-core CPUs. In ADC. 29–36. https://dl.acm.org/doi/10.5555/1862242.1862249

Hiroyuki Yamada

Publications