Search

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.

Time series classification is an important model in data mining. It involves assigning a class label to a test instance based on the training data with known class labels. Most previous studies developed time series classifiers by disregarding the fuzzy nature of events (i.e., events with similar values may belong to different classes) within the data. Consequently, these studies suffered from performance issues, including decreased accuracy and increased memory, runtime, and energy requirements. With this motivation, this paper proposes a novel fuzzy nearest neighbor classifier for time series data. The basic idea of our classifier is to transform the very large training data into a relatively small representative training data and use it to label a test instance by employing a new fuzzy distance measure known as Ravi. Experimental results on real world benchmark datasets demonstrate that the proposed classifier outperforms the current parameter-free time series classifiers and also the popular deep learning techniques.

Periodic-frequent pattern mining (PFPM) is an important data mining model having many real-world applications. However, this model’s prosperous industrial use has been hindered by the problem of combinatorial explosion of patterns, which is the generation of too many redundant patterns, most of which may be useless to the user. We propose a novel model of closed periodic-frequent patterns that may exist in a temporal database to address this problem. Closed periodic-frequent patterns represent a concise lossless subset that uniquely preserves the complete information of all periodic-frequent patterns in a database. An efficient depth-first search algorithm, called Closed Periodic-Frequent Pattern Miner (CPFP-Miner), has been introduced to find all the database’s desired patterns. Experimental results demonstrate that CPFP-Miner is not only memory, runtime, and energy-efficient, but also highly scalable. The usefulness of our model has also been shown with a case study on traffic congestion analytics.

Parallel processing is a flagship approach for answering analytical queries on large-scale database. As the database scale increases, a larger number of processing nodes are likely to be incorporated to increase the degree of parallelism. However, this solution results in an increased probability of node failure. If such a failure happens during query processing, the processing often has to restart from scratch. This temporal cost may not be acceptable for the user. In this paper, we propose PhoeniQ, a fault-tolerant query processing mechanism for analytical parallel database systems. PhoeniQ takes a package-level checkpoint for every operator pipeline and replicates the output of stateful operators among different processing nodes. If a single processing node fails during processing, another node is enabled to resume the execution state of the failed node, so that the query can continue to run. This paper presents our intensive experiments based on our prototype, which demonstrate that PhoeniQ can continue the query processing in the face of node failures with significantly smaller cost than the conventional approach.

Understanding the spread of diseases and the use of medicines is of practical importance for various organizations, such as medical providers, medical payers, and national governments. This study aims to detect the change in the prescription trends and to identify its cause through an analysis of Medical Insurance Claims (MICs), which comprise the specifications of medical fees charged to health insurers. Our approach is two-fold. (1) We propose a latent variable model that simulates the medication behavior of physicians to accurately reproduce monthly prescription time series from the MIC data, where prescription links between the diseases and medicines are missing. (2) We apply a state space model with intervention variables to decompose the monthly prescription time series into different components including seasonality and structural changes. Using a large dataset consisting of 3.5-year MIC records, we conduct experiments to evaluate our approach in terms of accuracy, usefulness, and efficiency. We also demonstrate three applications for our medical analysis.

The relational database has been the fundamental technology for data-driven decision making based on the histories of event occurrences about the analysis target. Thus the performance of analytical workloads in relational databases has been studied intensively. As a common language for performance analysis, decision support benchmarks such as TPC-H have been widely used. These benchmarks focus on summarization of the event occurrence information. Individual event occurrences or inter-occurrence associations are rarely examined in these benchmarks. However, this type of query, called an event sequence query in this paper, is becoming important in various real-world applications. Typically, an event sequence query extracts event sequences starting from a small number of interesting event occurrences. In a relational database, these queries are described by multiple self-joins on the whole sequence of events. Furthermore, each pair of events to be joined tends to have a strong correlation in the timestamp attribute, resulting in heavily skewed join workloads. Despite the usefulness in real-world data analysis, very little work has been done on performance analysis of event sequence queries.

Energy efficiency in analytical database systems is becoming increasingly important because of the rapid growth in energy consumed by data centers driven by the recent big data boom. Previous studies showed that processor speed scaling has the potential to improve energy efficiency of analytical queries. These results, however, were obtained from measurement of specific queries. The power–performance characteristics of processor speed scaling specific to analytical database systems still remains unexplored despite their importance in energy efficient analytical query processing. We tackle this problem by modeling the energy costs of analytical queries with processor speed scaling based on query processing throughput. Our experimental evaluation shows that our energy model can be fitted within an error of 1.65% and can be used to identify power–performance characteristics of analytical queries.

A number of insertions, updates and deletions eventually deteriorate the structural efficiency of database storage, and then cause performance degradation. This phenomenon is called “aging.” In real-world database systems, aging often exhibits strong locality because of the inherent skewness of data access; specifically speaking, the cost of I/O operations is not uniform throughout the storage space. Potentially query execution cost is influenced by the aging. However, conventional query optimizers do not consider the aging locality; thus they cannot accurately estimate the cost of query execution plans at times. In this paper, we propose a novel method of cost estimation that has the key capability of accurately determining aging phenomena, even though such phenomena are non-uniformly incurred. Our experiment on PostgreSQL and TPC-H data sets showed that the proposed method can accurately estimate the query execution cost even if it is influenced by the aging.

This paper reviews the history of storage systems. The first section begins with the era of early mechanical calculators and the following four sections review historically major storage devices such as magnetic tapes, magnetic disks, optical devices, and solid-state devices. The final two sections focus on recent system technologies such as storage networking and cloud-based storage.

Flash SSDs are being incorporated in many enterprise storage platforms recently and expected to play a notable role for IO-intensive applications. However, the IO characteristics of flash SSDs are very different from those of hard disks. Since existent storage subsystems are designed on the basis of characteristics of hard disks, the IO performance of flash SSDs may not be obtained as expected. This paper provides an evaluation of flash SSDs in transaction processing systems with TPC-C benchmark. We present performance results with various configurations and describe our observations of the IO behaviors at different levels along the IO path, which helps to understand the performance of flash-based transaction processing systems and provides certain references to build flash-based systems for IO-intensive applications.

Many update queries on a database can eventually degrade the structural efficiency of the database and result in lower performance. This phenomenon is called aging. On aged databases, conventional cost-based query optimizers could choose non-optimal query execution plan because they are not aging-aware and could not accurately estimate query execution cost.As a first step to build an aging-aware query optimizer, we experimentally examined the discrepancy between actual and estimated cost in order to investigate aging influence on the accuracy of cost estimation. The experimental result shows that aging could produce non-negligible cost estimation errors, up to 66.3%. The result indicates that a conventional query optimizer can fail to choose the optimal execution plan even for a simple query.

Data intensive applications such as MapReduce can have large performance degradation from the effects of I/O interference when multiple processes access the same I/O resources simultaneously, particularly in the case of disks. It is necessary to understand this effect in order to improve resource allocation and utilization for these applications. In this paper, we propose a model for predicting the impact of I/O interference on MapReduce application performance. Our model takes basic parameters of the workload and hardware environment, and knowledge of the I/O behavior of the application to predict how I/O interference affects the scalability of an application. We compare the model's predictions for several workloads (TeraSort, WordCount, PFP Growth and PageRank) against the actual behavior of those workloads in a real cluster environment, and confirm that our model can provide highly accurate predictions.

Specialized frameworks for highly scalable data processing continue to gain prominence over traditional databases in many environments including the cloud. Perhaps the most well-known such framework is Google MapReduce, which has gained wide-spread popularity. However, the MapReduce model offers some significant challenges for workload balancing which have not been adequately explored so far. In this paper, we introduce techniques for improving load balancing -- particularly multi-stage jobs and dynamic partition assignment -- by using a modified programming model that offers greater flexibility but maintains the simplicity, scalability and fault tolerance of MapReduce. We then explore the effectiveness of our approach using a parallel frequent itemset mining algorithm.

Power consumption in data centers has been growing remarkably recent years, and power saving of their servers is essential. For power saving of these servers, power saving of an online transaction processing (OLTP) systems, which are major applications in data centers, is important. The OLTP system consumes relatively large amount of power because it is often equipped with a lot of computing and storage resources. Its power saving is difficult because it is required to meet a service level agreement (SLA), and few power saving technologies have been proposed so far. In this paper, we proposed an application-aware power saving for OLTP in a multicore environment. Our proposed methodology aims to save power consumption of OLTP systems by dynamically scaling the operating frequency of processors based on response time observation. Response time is often an important metric of SLA. Application-aware power saving enables power saving in such systems subject to SLAs. In our experimental evaluations using industrial standard benchmark TPC-C and real server workloads, 7.6% of total power consumption was saved. This reduction corresponds to 1000kJ a day in a typical entry level server.

Flash SSDs are being incorporated in many enterprise storage platforms recently. However, the characteristics of the flash SSD are quite different from that of hard disk. The IO strategies in the existing systems should be carefully evaluated. This paper provides an evaluation on the flash-based transaction processing system. Two file systems, traditional in-place update-based file system and log-structured file system, are selected as the representative of two write strategies. Usually, the log-structured file system is believed to play better on flash SSDs. Our experiment shows that the performance results of two database applications are diverse with two file systems on different flash SSDs. We analyze the performance in different configurations. Based on the analysis, we provide our experience on building the flash-based database system to better utilize the performance benefits of flash SSDs.

In recent years, several frameworks have been developed for processing very large quantities of data on large clusters of commodity PCs. These frameworks have focused on fault-tolerance and scalability. However, when using heterogeneous environments these systems do not offer optimal workload balancing. In this paper we present Jumbo, a distributed computation platform designed to explore possible solutions to this issue.

Recently, flash memory is emerging as the storage device. With price sliding fast, the cost per capacity is approaching to that of SATA disk drives. So far flash memory has been widely deployed in consumer electronics even partly in mobile computing environments. For enterprise systems, the deployment has been studied by many researchers and developers. In terms of the access performance characteristics, flash memory is quite different from disk drives. Without the mechanical components, flash memory has very high random read performance, whereas it has a limited random write performance because of the erase-before-write design. The random write performance of flash memory is comparable with or even worse than that of disk drives. Due to such a performance asymmetry, naive deployment to enterprise systems may not exploit the potential performance of flash memory at full blast. This paper studies the effectiveness of using non-in-place-update (NIPU) techniques through the IO path of flash-based transaction processing systems. Our deliberate experiments using both open-source DBMS and commercial DBMS validated the potential benefits; x3.0 to x6.6 performance improvement was confirmed by incorporating non-in-place-update techniques into file system without any modification of applications or storage devices.

Together with the information explosion era comes the problem of high energy consumption in data centers. Among the various components of a data center, storage is one of the biggest energy consumers. Many efforts have been put on reducing energy consumptions of data centers/storage systems, from server workflow management to storage data allocation. However, most works focus on local storage systems and pay no attention to other structures of storage systems. With the exponential expanding on both the depth and width of the Internet, wide-area storage systems attract more and more attention as they are reliable, load-balancing, and easy to collaborate. In this paper, we study the energy consumption in wide-area storage systems by using multimedia objects as our special application area. We develop a multimedia object distributing algorithm based on the access pattern to multimedia objects and the topology of storage systems. We also present an in-depth analysis that provides valuable insight into the characteristics of multimedia object distribution strategies and leads to precision guarantees.

So far, the core component of the IT system was absolutely a server, and the storage was recognized as its peripheral. The recent evolution of device and network technologies has enabled storage consolidation, by which all the data and its related simple software codes can be placed in one place. Storage centric designs are being deployed into many enterprise systems. The role of the storage should be reconsidered. This paper presents activities of the Storage Fusion Project, a five-year research and development project. Storage Fusion is an idea of elegant deep collaboration between storage and database servers. Two substantial works are presented in this paper. First, the exploitation of query execution plans enables dynamically informed prefetching, accordingly boosting ad-hoc queries significantly. Second, the idea of putting autonomic database reorganization into the storage has the potential benefit of relieving the management burdens of database structural deterioration.

The paper proposes a structural deterioration monitor of database, which is an essential building block to realize an autonomic database reorganizer. Experimental results with our prototype show that the monitor can keep track of structural deterioration with high resolution, high accuracy, and low overhead.

Our research focuses on autonomic database reorganization for DBMS. Reorganization counteracts structural deterioration in tablespaces to recover performance. Structural deterioration through data updates is inevitable, therefore reorganization is an essential task in database administration. At present, there are only vague metrics of disorganization for judging whether administrator should perform reorganization or not. In this paper, we consider IO behavior inside storage and clarify causal relationship between level of structural deterioration and that of performance deterioration. We propose a method to quantitatively detect performance deterioration for reorganization trigger, and evaluate it with empirical test studies.

The unprecedented growth of available spatial data at geographically distributed locations coupled with the emergence of grid computing provides a strong motivation for designing a spatial grid which supports fast data retrieval and allows its users to transparently access data of any location from anywhere. This calls for efficient search and load-balancing mechanisms. This paper focusses on dynamic load-balancing in spatial grids via data migration/replication to prevent degradation in system performance owing to severe load imbalance among the nodes. The main contributions of our proposal are as follows. First, we view a spatial grid as comprising several clusters where each cluster is a local area network (LAN) and propose a novel inter-cluster load-balancing algorithm which uses migration/replication of data. Second, we present a novel scalable technique for dynamic data placement that not only improves data availability but also minimizes disruptions and downtime to the system. Our performance study demonstrates the effectiveness of our proposed approach in correcting workload skews, thereby facilitating improvement in system performance. To our knowledge, this work is one of the earliest attempts at addressing load-balancing via both online data migration and replication in grid environments.

PC cluster system is an attractive platform for data-intensive applications. But the conventional shared-nothing system has a limit on load balancing performance and it is difficult to change the number of nodes and disks dynamically during execution. In this paper, we develop dynamic resource injection, where the system can inject CPU power and expand I/O bandwidth by adding nodes and disks dynamically in the SAN(Storage Area Network)-connected PC cluster. Our experiments with data mining application confirm its effectiveness. We show the advantages of combining PC cluster with SAN.

We present performance measurement results for a parallel SQL based information retrieval system implemented on a PC cluster system. We used the Web-TREC dataset under a left-deep query execution plan. We achieved satisfactory speed up.

Structural deterioration of database is caused by updates of the database and can degrade performance seriously. Database reorganisation, which removes structural deterioration by relocating data in the secondary storage, is an administrator's headache; it is difficult to schedule reorganisation efficiently to keep acceptable performance because conventional database systems lack crucial monitoring facility of structural deterioration, with high resolution, high accuracy and low overhead. In order to make database reorganisation be easy for administrators and be autonomic in the future, the paper proposes an online database structure deterioration monitor, which can visualise structural deterioration distribution, with a novel structural deterioration model, a storage performance model and an incremental update technique. The experimental results with our prototype show that our scheme can monitor structural deterioration with an error of within 12% and with an overhead of 3% at most.