When running OLTP workloads on flash SSDs, relational DBMSs still face the write durability overhead, severely limiting their performance. To address this challenge, we propose NV-PPL, a novel database architecture that leverages NVDIMM as a durable log cache. NV-PPL captures per-page redo logs and retains them on NVDIMM to absorb writes from DRAM to SSD. Our NV-PPL prototype, deployed on an actual NVDIMM device, demonstrates superior transaction throughput, surpassing the same-priced Vanilla MySQL by at least 6.9× and NV-SQL, a page-grained NVDIMM caching scheme, by up to 1.5×. Beyond write reduction, the page-wise logs in NVDIMM enable novel approaches such as redo-less recovery and redo-based multi-versioning. Compared to Vanilla MySQL, redo-less recovery reduces recovery time by one-third, while redo-based multi-versioning enhances the latency of long-lived transactions in HTAP workloads by 3× to 18×.

When running OLTP workloads, relational DBMSs with flash SSDs still suffer from the durability overhead. Heavy writes to SSD not only limit the performance but also shorten the storage lifespan. To mitigate the durability overhead, this paper proposes a new database architecture, NV-SQL. NV-SQL aims at absorbing a large fraction of writes written from DRAM to SSD by introducing NVDIMM into the memory hierarchy as a durable write cache. On the new architecture, NV-SQL makes two technical contributions. First, it proposes the re-update interval-based admission policy that determines which write-hot pages qualify for being cached in NVDIMM. It is novel in that the page hotness is based solely on pages' LSN. Second, this study finds that NVDIMM-resident pages can violate the page action consistency upon crash and proposes how to detect inconsistent pages using per-page in-update flag and how to rectify them using the redo log. NV-SQL demonstrates how the ARIES-like logging and recovery techniques can be elegantly extended to support the caching and recovery for NVDIMM data. Additionally, by placing write-intensive redo buffer and DWB in NVDIMM, NV-SQL eliminates the log-force-at-commit and WAL protocols and further halves the writes to the storage. Our NV-SQL prototype running with a real NVDIMM device outperforms the same-priced vanilla MySQL with larger DRAM by several folds in terms of transaction throughput for write-intensive OLTP benchmarks. This confirms that NV-SQL is a cost-performance efficient solution to the durability problem.

The conventional database buffer managers have two inherent sources of I/O serialization: read stall and mutex conflict. The serialized I/O makes storage and CPU under-utilized, limiting transaction throughput and latency. Such harm stands out on flash SSDs with asymmetric read-write speed and abundant I/O parallelism. To make database I/Os parallel and thus leverage the parallelism in flash SSDs, we propose a novel approach to database buffering, the LRU-C method. It introduces the LRU-C pointer that points to the least-recently-used-clean page in the LRU list. Upon a page miss, LRU-C selects the current LRU-clean page as a victim and adjusts the pointer to the next LRU-clean one in the LRU list. This way, LRU-C can avoid the I/O serialization of read stalls. The LRU-C pointer enables two further optimizations for higher I/O throughput: dynamic-batch-write and parallel LRU-list manipulation. The former allows the background flusher to write more dirty pages at a time, while the latter mitigates mutex-induced I/O serializations. Experiment results from running OLTP workloads using MySQL-based LRU-C prototype on flash SSDs show that it improves transaction throughput compared to the Vanilla MySQL and the state-of-the-art WAR solution by 3x and 1.52x, respectively, and also cuts the tail latency drastically. Though LRU-C might compromise the hit ratio slightly, its increased I/O throughput far offsets the reduced hit ratio.

For a write request, today's flash storage cannot distinguish the logical object it comes from ( e.g. , SSTables in RocksDB). In such object-oblivious flash devices, concurrent writes from different objects are simply packed in their arrival order to flash memory blocks; hence data pages from multiple objects with different lifetimes are multiplexed onto the same flash blocks. This multiplexing incurs write amplification, worsening the performance. Tackling the multiplexing problem, we propose a novel interface for flash storage, FlashAlloc. It is used to pass the logical address ranges of objects to the underlying flash device and thus to enlighten the device to stream writes by objects. The object-aware flash storage can now de-multiplex concurrent writes from multiple objects with distinct deathtimes into per-object dedicated flash blocks. In essence, the interface enables the per-object fine-grained write streaming. Given that popular data stores tend to separate writes by logical objects, we can achieve, compared to the existing solutions, transparent streaming just by calling FlashAlloc upon object creation. Also, FlashAlloc is adaptive to workload changes, and liberates the stream conflicts in the multi-tenant environment. Our experimental results using an open-source SSD prototype demonstrate that FlashAlloc can reduce the device-level write amplification factor (WAF) under RocksDB, F2FS, and MySQL by 1.5, 2.5, and 0.3, respectively and improve their throughput by 2.7x, 1.8x, and 1.2x, respectively. Also, FlashAlloc can mitigate the WAF interference among tenants: when running RocksDB and MySQL together on the same SSD, FlashAlloc reduced WAF from 2.5 to 1.6 and doubled their throughputs.

While gaining popularity in mobile devices, F2FS, a flash-friendly variation of log-structured file system, reveals three drawbacks: segment cleaning overhead, metadata update overhead, and file fragmentation, which becomes conspicuous under random update workloads. This paper suggests for the first time to leverage the address-remap technique in flash storage to remedy such pitfalls in F2FS. Our approach can, while preserving the benefit of log-structured writes, achieve the eventual effect of in-place update, completely preventing three drawbacks of F2FS. It can thus significantly outperform ext4 as well as vanilla F2FS under random update workloads. Armed with another write mode, F2FS will become competitive for a wider range of applications.

Searching top-k nearest neighbor (kNN) based on the vector similarity is a common problem in many domains. Unlike approximate kNN search, exact kNN needs to check a large portion of the dataset, if not the entire set. When the data volume is large, the dataset cannot fit in the main memory and has to be stored on a storage device such as flash drive. ES4D is a kNN search platform implemented near-data on the solid-state drive (SSD). ES4D accelerates kNN search by using two levels of early termination, using pre-clustering of the dataset vectors and vector sharding. ES4D incorporates several optimization techniques to aid such early terminations. Using near-data processing, ES4D further enhances performance and reduces energy consumption. Performing the kNN search on the SSD side not only improves energy efficiency but also enables ES4D to optimize the physical page placement of dataset vectors on SSD to maximize the search throughput. We evaluated ES4D using various vector datasets. ES4D achieves 1.9× search performance improvement over existing exact kNN search mechanisms. Also, by off-loading the distance calculation to the SSD side, ES4D reduces energy consumption for kNN search by 8.1×.

When a dirty victim page is selected for replacement upon page miss, the buffer manager has to first flush the dirty victim to the storage before reading the missing page. This conventional read-after-write (RAW) protocol, while working well on hard disks, causes the problem of read stall on flash storage with asymmetric read-write speed and parallelism; because of the resource conflict for a buffer frame between write and read operations, a page-missing process has to wait for the slow write to complete to secure a clean frame for the missing page. This strict write-then-read serialization under-utilizes CPU and storage, worsening transaction throughput and latency. To avoid the read stall problem on flash storage, this paper proposes write-after-read (WAR) protocol as a new I/O architecture between buffer manager and flash storage. In WAR, foreground processes make victim frames clean instantly by temporarily copying dirty pages at LRU tail into a separate DRAM space and read their missing pages into the cleaned frames with no stall. The dirty pages will be written to the storage asynchronously. By resolving resource conflict and thus avoiding read stalls, the database engine can issue more I/Os in parallel and better utilize CPU as well as storage, improving throughput and latency. We prototype WAR in two database storage engines, MySQL/InnoDB and Zero. Our comprehensive experimental results show that WAR improves transaction throughput by up to 2.9x compared to RAW.

When replacing a dirty victim page upon page miss, the conventional buffer managers flush the dirty victim first to the storage before reading the missing page. This read-after-write (RAW) protocol, unfortunately, causes the read stall problem on flash storage; because of the asymmetric I/O speed and parallelism in flash storage, the clean frames are quickly consumed, so the read for the missing page often has to wait for the slow write to complete and for the frame to be clean due to the resource conflict for the same buffer frame. RAW will thus make the performance-critical synchronous reads often blocked by writes, severely worsening transaction throughput and latency. In addition, its strict I/O ordering will make flash storage with abundant parallelism under-utilized. To avoid read stalls in the DBMS buffer, we propose RW ( fused read and write ) as a new storage interface. Using RW on read stall, the buffer manager can issue both read and write requests at once to the storage. Then, once the dirty page is copied to the storage buffer, it can immediately serve the read. In addition, to resolve read stalls in the flash storage buffer, we propose R-Buf, where the read buffer is separated from the write buffer so that reads can proceed at no stall. RW and R-Buf, working at different layers, complement each other when used together. We prototype RW and R-Buf on a real Cosmos+ OpenSSD board. Evaluation results show that RW alone improves TPC-C throughput over RAW by 3.2x and, combined with R-Buf, does by 3.9x. In addition, we demonstrate that R-Buf effectively mitigates the I/O interference in multi-tenancy.

Increasing the concurrency level in mobile database systems has not received much attention, mainly because the concurrency requirements of mobile workloads has been regarded to be low. Contrary to popular belief, mobile workloads require higher concurrency. In this work, we propose novel journaling and concurrency mechanisms for mobile DBMSs, both of which build upon one common concept - In-Page Shadowing (IPS). We design and implement a novel In-Page Shadowing recovery method for SQLite to resolve the journaling of journal anomaly, which is known to quadruple the I/O traffic in mobile devices. IPS unions the previous and the next versions of a database page in the same physical page. Using the consolidated two versions of database page, we design Two-Version Timestamp-Ordering (2VTO) protocol that enables non-blocking reads as in multi-version concurrency control, but reduces the garbage collection overhead. Designed with mobile environments in mind, IPS and 2VTO are high-performant and resource-efficient transactional solutions. Our performance study shows that IPS and 2VTO outperform state-of-the-art logging methods and an optimistic concurrency control protocol for real mobile workloads.

Every database engine runs on top of an operating system in the host, strictly separated with the storage. This more-than-half-century-old IHDE (In-Host-Database-Engine) architecture, however, reveals its limitations when run on fast flash memory SSDs. In particular, the IO stacks incur significant run-time overhead and also hinder vertical optimizations between database engines and SSDs. In this paper, we envisage a new database architecture, called SaS (SSD as SQL database engine), where a full-blown SQL database engine runs inside SSD, tightly integrated with SSD architecture without intervening kernel stacks. As IO stacks are removed, SaS is free from their run-time overhead and further can explore numerous vertical optimizations between database engine and SSD. SaS evolves SSD from dummy block device to database server with SQL as its primary interface. The benefit of SaS will be more outstanding in the data centers where the distance between database engine and the storage is ever widening because of virtualization, storage disaggregation, and open software stacks. The advent of computational SSDs with more compute resource will enable SaS to be more viable and attractive database architecture.

Key-value stores such as LevelDB and RocksDB are widely used in various systems due to their high write performance. However, the background compaction operations inherent to the key-value stores are often to blame for write amplification and write stall. In particular, the SSTable size in the existing key-value stores introduces, upon compactions, a tradeoff between the fsync() call frequency and the amount of amplified writes. Small SSTables require a larger number of fsync()/fdatasync() than large SSTables to maintain file consistency. On the contrary, large SSTables result in large overlaps and frequent rewrites of SSTables. In this paper, to reduce file consistency overhead without increasing key ranges of SSTables, we present a variant of LSM-tree, namely, BoLT (Barrier-optimized LSM-Tree), that minimizes the number of calls to fsync()/fdatasync() barriers while taking advantage of fine-grained SSTables. BoLT consists of four key elements: (i) compaction file, (ii) logical SSTables, (iii) group compaction, and (iv) settled compaction. We implement BoLT in LevelDB and HyperLevelDB and compare the performances against LevelDB, HyperLevelDB, RocksDB, and the state-of-the-art PebblesDB. Our experimental study shows that BoLT achieves significantly higher write throughputs than LevelDB and HyperLevelDB.

In this article, we propose a simple but practical and efficient optimization scheme for journaling in ext4, called lightweight data journaling ( LDJ ). By compressing journaled data prior to writing, LDJ can perform comparable to or even faster than the default ordered journaling (OJ) mode in ext4 on top of both HDDs and flash storage devices, while still guaranteeing the version consistency of the data journaling (DJ) mode. This surprising result can be explained with three main reasons. First, on modern storage devices, the sequential write pattern dominating in DJ mode is more and more high-performant than the random one in OJ mode. Second, the compression significantly reduces the amount of journal writes, which will in turn make the write completion faster and prolong the lifespan of storage devices. Third, the compression also enables the atomicity of each journal write without issuing an intervening FLUSH command between journal data blocks and commit block, thus halving the number of costly FLUSH calls in LDJ . We have prototyped our LDJ by slightly modifying the existing ext4 with jbd2 for journaling and also e2fsck for recovery; less than 300 lines of source code were changed. Also, we carried out a comprehensive evaluation using four standard benchmarks and three real applications. Our evaluation results clearly show that LDJ outperforms the OJ mode by up to 9.6× on the real applications.

We present the design, implementation, and evaluation of a new file system, called ACCFS, supporting application-level crash consistency as its first-class citizen functionality. With ACCFS, application data can be correctly recovered in the event of system crashes without any complex update protocol at the application level. With the help of the SHARE interface supporting atomic address remapping at the flash storage layer, ACCFS can easily and efficiently achieve crash consistency as well as single-write journaling. We prototyped ACCFS by slightly modifying the full data journal mode in ext4, implemented the SHARE interface as firmware in a commercial SSD available in the market, and carried out various experiments by running ACCFS on top of the SSD. Our preliminary experimental results are very promising. For instance, the performance of an OLTP benchmark using MySQL/InnoDB engine can be boosted by more than 2-6x by offloading the responsibility of guaranteeing the atomic write of MySQL data pages from the InnoDB engine's own journaling mechanism to ACCFS. This impressive performance gain is in part due to the single-write journaling in ACCFS and in part comes from the fact that the frequent fsync() calls caused by the complex update protocol at the application level can be avoided. ACCFS is a practical solution for the crash consistency problem in that (1) the SHARE interface can be, like the TRIM command, easily supported by commercial SSDs, (2) it can be embodied with a minor modification on the existing ext4 file system, and (3) the existing applications can be made crash consistent simply by opening files in O_ATOMIC mode while the legacy applications can be run without any change.

short-paper Share on Freezing Frozen Pages with Multi-Stream SSDs Authors: Hyun-Woo Park View Profile , Soyee Choi View Profile , Mijin An View Profile , Sang-Won Lee View Profile Authors Info & Claims DaMoN'19: Proceedings of the 15th International Workshop on Data Management on New HardwareJuly 2019 Article No.: 16Pages 1–3https://doi.org/10.1145/3329785.3329935Published:01 July 2019Publication History 3citation246DownloadsMetricsTotal Citations3Total Downloads246Last 12 Months31Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The lightweight codebase of SQLite was helpful in making it become the de-facto standard database in most mobile devices, but, at the same time, forced it to take less-complicated transactional schemes, such as physical page logging, journaling, and force commit, which in turn cause excessive write amplification. Thus, the write IO cost in SQLite is not lightweight at all. In this paper, to make SQLite truly lite in terms of IO efficiency for the transactional support, we propose SQLite/SSL , a per-transaction SQL statement logging scheme: when a transaction commits, SQLite/SSL ensures its durability by storing only SQL statements of small size, thus writing less and performing faster at no compromise of transactional solidity. Our main contribution is to show that, based on the observation that mobile transactions tend to be short and exhibit strong update locality , logical logging can, though long discarded, become an elegant and perfect fit for SQLite-based mobile applications. Further, we leverage the WAL journal mode in vanilla SQLite as a transaction-consistent checkpoint mechanism which is indispensable in any logical logging scheme. In addition, we show for the first time that byte-addressable NVM (non-volatile memory) in host-side can realize the full potential of logical logging because it allows to store fine-grained logs quickly. We have prototyped SQLite/SSL by augmenting vanilla SQLite with a transaction-consistent checkpoint mechanism and a redo-only recovery logic, and have evaluated its performance using a set of synthetic and real workloads. When a real NVM board is used as its log device, SQLite/SSL can outperform vanilla SQLite's WAL mode by up to 300x and also outperform the state-of-the-arts SQLite/PPL scheme by several folds in terms of IO time.

Database consistency and recoverability require guaranteeing write atomicity for one or more pages. However, contemporary database systems consider write operations non-atomic. Thus, many database storage engines have traditionally relied on either journaling or copy-on-write approaches for atomic propagation of updated pages to the storage. This reliance achieves write atomicity at the cost of various write amplifications such as redundant writes, tree-wandering, and compaction. This write amplification results in reduced performance and, for flash storage, accelerates device wear-out. In this paper, we propose a flash storage interface, SHARE. Being able to explicitly remap the address mapping inside flash storage using SHARE interface enables host-side database storage engines to achieve write atomicity without causing write amplification. We have implemented SHARE on a real SSD board, OpenSSD, and modified MySQL/InnoDB and Couchbase NoSQL storage engines to make them compatible with the extended SHARE interface. Our experimental results show that this SHARE-based MySQL/InnoDB and Couchbase configurations can significantly boost database performance. In particular, the inevitable and costly Couchbase compaction process can complete without copying any data pages.

Given its pervasive use in smart mobile platforms, there is a compelling need to optimize the performance of sluggish SQLite databases. Popular mobile applications such as messenger, email and social network services rely on SQLite for their data management need. Those mobile applications tend to execute relatively short transactions in the autocommit mode for transactional consistency in databases. This often has adverse effect on the flash memory storage in mobile devices because the small random updates cause high write amplification and high write latency. In order to address this problem, we propose a new optimization strategy, called per-page logging (PPL) , for mobile data management, and have implemented the key functions in SQLite/PPL. The hardware component of SQLite/PPL includes phase change memory (PCM) with a byte-addressable, persistent memory abstraction. By capturing an update in a physiological log record and adding it to the PCM log sector, SQLite/PPL can replace a multitude of successive page writes made to the same logical page with much smaller log writes done to PCM much more efficiently. We have observed that SQLite/PPL would potentially improve the performance of mobile applications by an order of magnitude while supporting transactional atomicity and durability.

This paper presents a novel technique, called Zombie Chasing, for efficient flash management in solid state drives (SSDs). Due to the unique characteristics of NAND flash memory, SSDs need to accurately understand the liveness of the data stored in themselves. Recently, the TRIM command has been introduced to notify SSDs of dead data caused by file deletions, which otherwise could not be tracked by SSDs. This paper goes one step further and proposes a new liveness state, called the zombie state, to denote live data that will be dead shortly due to the corresponding dirty data in the buffer cache. We also devise new zombie-aware garbage collection algorithms which utilize the information about such zombie data inside SSDs. To evaluate Zombie Chasing, we implement zombie-aware garbage collection algorithms in the prototype SSD and modify the Linux kernel and the Oracle DBMS to deliver the information on the zombie data to the prototype SSD. Through comprehensive evaluations using our in-house micro-benchmark and the TPC-C benchmark, we observe that Zombie Chasing improves SSD performance effectively by reducing garbage collection overhead. Especially, our evaluation with the TPC-C benchmark on the Oracle DBMS shows that Zombie Chasing enhances the Transactions Per Second (TPS) value by up to 22% with negligible overhead.

In order to meet the stringent requirements of low latency as well as high throughput, web service providers with large data centers have been replacing magnetic disk drives with flash memory solid-state drives (SSDs). They commonly use relational and NoSQL database engines to manage OLTP workloads in the warehouse-scale computing environments. These modern database engines rely heavily on redundant writes and frequent cache flushes to guarantee the atomicity and durability of transactional updates. This has become a serious bottleneck of performance in both relational and NoSQL database engines. This paper presents a new SSD prototype called DuraSSD equipped with tantalum capacitors. The tantalum capacitors make the device cache inside DuraSSD durable, and additional firmware features of DuraSSD take advantage of the durable cache to support the atomicity and durability of page writes. It is the first time that a flash memory SSD with durable cache has been used to achieve an order of magnitude improvement in transaction throughput without compromising the atomicity and durability. Considering that the simple capacitors increase the total cost of an SSD no more than one percent, DuraSSD clearly provides a cost-effective means for transactional support. DuraSSD is also expected to alleviate the problem of high tail latency by minimizing write stalls.

Even in modern SSDs, the disparity between random and sequential write bandwidth is more than 10-fold. Moreover, random writes can shorten the limited lifespan of SSDs because they incur more NAND block erases per write. To overcome the problems of random writes, we propose a new file system, SFS, for SSDs. SFS is similar to the traditional log-structured file system (LFS) in that it transforms all random writes at the file system level to sequential ones at the SSD level, as a way to exploit the maximum write bandwidth of the SSD. But, unlike the traditional LFS, which performs hot/cold data separation on segment cleaning, SFS takes a new on writing data grouping strategy. When data blocks are to be written, SFS puts those with similar update likelihood into the same segment for sharper bimodal distribution of segment utilization, and thus aims at minimizing the inevitable segment cleaning overhead that occurs in any log-structured file system. We have implemented a prototype SFS by modifying Linux-based NILFS2 and compared it with three state-of-the-art file systems using several realistic workloads. Our experiments on SSDs show that SFS outperforms LFS by up to 2.5 times in terms of throughput. In comparison to modern file systems, SFS drastically reduces the block erase count inside SSDs by up to 23.3 times. Although SFS was targeted for SSDs, its data grouping on writing would also work well in HDDs. To confirm this, we repeated the same set of experiments over HDDs, and found that SFS is quite promising in HDDs: although the slow random reads in HDDs make SFS slightly less effective, SFS still outperforms LFS by 1.7 times.

In the era of smartphones and mobile computing, many popular applications such as Facebook, twitter, Gmail, and even Angry birds game manage their data using SQLite. This is mainly due to the development productivity and solid transactional support. For transactional atomicity, however, SQLite relies on less sophisticated but costlier page-oriented journaling mechanisms. Hence, this is often cited as the main cause of tardy responses in mobile applications.

Flash memory devices commonly rely on traditional address mapping schemes such as page mapping, block mapping or a hybrid of the two. Page mapping is more flexible than block mapping or hybrid mapping without being restricted by block boundaries. However, its mapping table tends to grow large quickly as the capacity of flash memory devices does. To overcome this limitation, we propose a novel mapping scheme that is fundamentally different from the existing mapping strategies. We call this new scheme Virtual Extent Trie (VET), as it manages mapping information by treating each I/O request as an extent and by using extents as basic mapping units rather than pages or blocks. By storing extents instead of individual addresses, VET consumes much less memory to store mapping information and still remains as flexible as page mapping. We observed in our experiments that VET reduced memory consumption by up to an order of magnitude in comparison with the traditional mapping schemes for several real world workloads. The VET scheme also scaled well with increasing address spaces by synthetic workloads. With a binary search mechanism, VET limits the mapping time to O(log log|U |), where U denotes the set of all possible logical addresses. Though the asymptotic mapping cost of VET is higher than the O(1) time of a page mapping scheme, the amount of increased overhead was almost negligible or low enough to be hidden by an accompanying I/O operation.

Recently, several studies on multi-core cache-aware hash join have been carried out [Kim09VLDB, Blanas11SIGMOD]. In particular, the work of Blanas has shown that rather simple no-partitioning hash join can outperform the work of Kim. Meanwhile, the simple but best performing hash join of Blanas still experiences severe cache misses in probing phase. Because the key values of tuples in outer relation are not sorted or clustered, each outer record has different hashed key value and thus accesses the different hash bucket. Since the size of hash table of inner table is usually much larger than that of the CPU cache, it is highly probable that the reference to hash bucket of inner table by each outer record would encounter cache miss. To reduce the cache misses in hash join probing phase, we propose a new join algorithm, Sorted Probing (in short, SP), which pre-sorts the hashed key values of outer table of hash join so that the access to the hash bucket of inner table has strong temporal locality, thus minimizing the cache misses during the probing phase. As an optimization technique of sorting, we used the cache-aware AlphaSort technique, which extracts the key from each record of data set to be sorted and its pointer, and then sorts the pairs of (key, rec_ptr). For performance evaluation, we used two hash join algorithms from Blanas' work, no partitioning(NP) and independent partitioning(IP) in a standard C++ program, provided by Blanas. Also, we implemented the AlphaSort and added it before each probing phase of NP and IP, and we call each algorithm as NP+SP and IP+SP. For syntactic workload, IP+SP outperforms all other algorithms: IP+SP is faster than other altorithms up to 30%.

RDF is widely used as an ontology language for representing the metadata in Semantic Web, knowledge management system and E-commerce. Since ontologies model the knowledge in a particular domain, they may change over time. Furthermore, ontologies are usually developed and controlled in a distributed and collaborative way. Thus, it is very important to be able to manage multiple versions for RDF data. Earlier studies on RDF versions have focused on providing the accesses to different versions (i.e. snapshots) and computing the differences between those two versions. However, the existing approaches suffer from the space overhead for large scale data, since all snapshots should be redundantly kept in a repository. Moreover, it is very time consuming to compute the delta between two specific versions, which is very common in RDF applications. In this paper, we propose a framework for RDF version management in relational databases. It stores the original version and the deltas between two consecutive versions, thereby reducing the space requirement considerably. The other benefit of our approach is appropriate for change queries. On the flip side, in order to answer a query on a specific logical version, version should be constructed on the fly by applying the deltas between the original version and the logical version. This can slow down query performance. In order to overcome this, we propose a compression technique for deltas, called Aggregated Delta, to create a logical version directly rather than executing the sequence of deltas. An experimental study with real life RDF data sets shows our framework maintains multiple versions efficiently.

Considering the current price gap between disk and flash memory drives, for applications dealing with large scale data, it will be economically more sensible to use flash memory drives to supplement disk drives rather than to replace them. This paper presents FaCE , which is a new low-overhead caching strategy that uses flash memory as an extension to the DRAM buffer. FaCE aims at improving the transaction throughput as well as shortening the recovery time from a system failure. To achieve the goals, we propose two novel algorithms for flash cache management, namely, Multi-Version FIFO replacement and Group Second Chance . One striking result from FaCE is that using a small flash memory drive as a caching device could deliver even higher throughput than using a large flash memory drive to store the entire database tables. This was possible due to flash write optimization as well as disk access reduction obtained by the FaCE caching methods. In addition, FaCE takes advantage of the non-volatility of flash memory to fully support database recovery by extending the scope of a persistent database to include the data pages stored in the flash cache. We have implemented FaCE in the PostgreSQL open source database server and demonstrated its effectiveness for TPC-C benchmarks.

Unlike database tables, B+-tree indexes are hierarchical and their structures change over time by node splitting operations, which may propagate changes from one node to another. The node splitting operation is difficult for the basic In-Page Logging (IPL) scheme to deal with, because it involves more than one node that may be stored separately in different flash blocks. In this paper, we propose Dynamic IPL B+-tree (d-IPL B+-tree in short) as a variant of the IPL scheme tailored for flash-based B+-tree indexes. The d-IPL B+-tree addresses the problem of frequent log overflow by allocating a log area in a flash block dynamically. It also avoids a page evaporation problem, imposed by the contemporary NAND flash chips, by introducing ghost nodes to d-IPL B+-tree. This simple but elegant design of the d-IPL B+-tree provides significant performance improvement over existing approaches. For a random insertion workload, the d-IPL B+-tree outperformed a B+-tree with the plain IPL scheme by more than a factor of two in terms of page write and block erase operations.

Recently, a new buffer and storage management strategy called In-Page Logging (IPL) has been proposed for database systems based on flash memory. Its main objective is to overcome the limitations of flash memory such as erase-before-write and asymmetric read/write speeds by storing changes made to a data page in a form of log records without overwriting the data page itself. Since it maintains a series of changes made to a data page separately from the original data page until they are merged, the IPL scheme provides unique opportunities to design light-weight transactional support for database systems. In this paper, we propose the transactional IPL (TIPL) scheme that takes advantage of the IPL log records to support multiversion read consistency and light-weight database recovery. Due to the dual use of IPL log records, namely, for snapshot isolation and fast recovery as well as flash-aware write optimization, TIPL achieves transactional support for flash memory database systems that minimizes the space and time overhead during normal database processing and shortens the database recovery time.

Previous research addressed the potential problems of the hard-disk oriented design of DBMSs of flashSSDs. In this paper, we focus on exploiting potential benefits of flashSSDs. First, we examine the internal parallelism issues of flashSSDs by conducting benchmarks to various flashSSDs. Then, we suggest algorithm-design principles in order to best benefit from the internal parallelism. We present a new I/O request concept, called psync I/O that can exploit the internal parallelism of flashSSDs in a single process. Based on these ideas, we introduce B+-tree optimization methods in order to utilize internal parallelism. By integrating the results of these methods, we present a B+-tree variant, PIO B-tree. We confirmed that each optimization method substantially enhances the index performance. Consequently, PIO B-tree enhanced B+-tree's insert performance by a factor of up to 16.3, while improving point-search performance by a factor of 1.2. The range search of PIO B-tree was up to 5 times faster than that of the B+-tree. Moreover, PIO B-tree outperformed other flash-aware indexes in various synthetic workloads. We also confirmed that PIO B-tree outperforms B+-tree in index traces collected inside the Postgresql DBMS with TPC-C benchmark.

Flash memory has many advantages such as high performance, low electronic power, non-volatile storage and physical stability, over hard-disks. For this reason, flash memory has been deployed as data storage for mobile devices, including PDAs, MP3 players, laptop-computers and database systems. According to the cell type, flash memory can be divided into SLC(Single Level Chip) and MLC(Multi Level Chip). In general, SLC is known to have high performance and longer lifetime (i.e. more than 100 K wear-leveling) while MLC is to offer larger capacity and with low price but have wear leveling of not longer than 10 K. In this paper, we show that it is possible to design a fast and cost-efficient storage by combining two types of flash memories in a hybrid fashion. Specifically, we propose a hybrid flash memory solid state disk(SSD) scheme using FAST FTL for enterprise applications, where SLC chip is used as the log space for FAST while MLC chips store the normal data blocks. SLC chips allow fast and durable performance for write while MLC chips provide the large capacity. And, this is mainly due to the FAST FTL algorithm's characteristics: it tends to direct the random writes to SLC chips and direct the other most random read to MLC chips. By taking the advantages of both chip types, we can find an economically desirable flash SSD design option. Experimental results show that our hybrid flash SSD scheme outperforms MLC-only flash scheme by far both in terms of performance and price.

This paper presents Dynamic IPL B+-tree (d-IPL in short) as a B+-tree index variant for flash-based storage systems. The d-IPL B+-tree adopts a dynamic In-Page Logging (IPL) scheme in order to address a few new problems that are caused by the unique characteristics of B+-tree indexes The d-IPL B+-tree avoids the frequent log overflow problem by allocating a log area in a flash block dynamically. It also addresses elegantly the problem of page evaporation, imposed by the contemporary NAND flash chips, by introducing ghost nodes within the context of the dynamic IPL scheme. This simple but elegant design of the d-IPL B+-tree improves the performance significantly. For a random insertion workload, the d-IPL B+-tree index outperformed a B+-tree with a plain IPL scheme by more than a factor of two in terms of page write and block erase operations.

The association rule mining, one of the most popular data mining techniques, is to find the frequent itemsets which occur commonly in transaction database. Of the various association algorithms, the Apriori is the most popular one, and its implementation technique to improve the performance has been continuously developed during the past decade. In this paper, we propose a bitmap-based association rule technique, called BAR, in order to drastically improve the performance of the Apriori algorithm. Compared to the latest Apriori implementation, our approach can improve the performance by nearly up to two orders of magnitude. This gain comes mainly from the following characteristics of BAR: 1) bitmap based implementation paradigm, 2) reduction of redundant bitmap-AND operations, and 3) an efficient implementation of bitmap-AND and bit-counting operation by exploiting the advanced CPU technology, including SIMD and SW prefetching. We will describe the basic concept of BAR approach and its optimization techniques, and will show, through experimental results, how each of the above characteristics of BAR can contribute the performance improvement.

The past few decades have witnessed a chronic and widening imbalance among processor bandwidth, disk capacity, and access speed of disk. According to Amdhal's law, the performance enhancement possible with a given improvement is limited by the amount that the improved feature is used. This implies that the performance enhancement of an OLTP system would be seriously limited without a considerable improvement in I/O throughput. Since the market debut of flash memory SSD a few years ago, we have made a continued effort to overcome its poor random write performance and to provide stable and sufficient I/O bandwidth. In this paper, we present three different flash memory SSD models prototyped recently by Samsung Electronics. We then show how the flash memory SSD technology has advanced to reverse the widening trend of performance gap between processors and storage devices. We also demonstrate that even a single flash memory drive can outperform a level-0 RAID with eight enterprise class 15k-RPM disk drives with respect to transaction throughput, cost effectiveness and energy consumption.

Due to its superiority such as low access latency, low energy consumption, light weight, and shock resistance, the success of flash memory as a storage alternative for mobile computing devices has been steadily expanded into personal computer and enterprise server markets with ever increasing capacity of its storage. However, since flash memory exhibits poor performance for small-to-moderate sized writes requested in a random order, existing database systems may not be able to take full advantage of flash memory without elaborate flash-aware data structures and algorithms. The objective of this work is to understand the applicability and potential impact that flash memory SSD (Solid State Drive) has for certain type of storage spaces of a database server where sequential writes and random reads are prevalent. We show empirically that up to more than an order of magnitude improvement can be achieved in transaction processing by replacing magnetic disk with flash memory SSD for transaction log, rollback segments, and temporary table spaces.

Recently, flash memory(in particular, NAND) is being rapidly deployed as data storage for mobile platforms such as PDAs, MP3 players, mobile phones and digital cameras, mainly because of its many advantages over its competitor, hard disk, including its low electronic power, non-volatile storage, high performance, physical stability, smaller size, light weight, and portability. Considering its rapid technical improvement both in capacity and speed, it will have a competitive advantage over its rivalry minidrive (i.e. a small size hard disk) under 100 Gbytes within a few years, As the applications in next generation mobile platforms become large, complex, and more data-oriented, they requires the database technology, because the file interface is too complex to manage their complicated data requirements. However, flash memory, compared to hard disk, has a few unique characteristics, and thus the traditional disk-based database technology does not seem to go well with flash memory. Therefore, we need to revisit almost every aspect of DBMS implementation techniques from the perspectives of flash memory. In this paper, we introduce the technical characteristics of flash memory, which we think might have huge impact on database performance to database community that are 1) no-overwrite (erase-before-write paradigm), 2) asymmetric read and write speed, and 3) no seek or rotation time. These small differences necessitate us to revisit all the major DBMS modules which have evolved over the several decades. Based on the characteristics, we identify several key issues in implementing major DBMS modules, and suggest alternative approaches to solve the issues. The topics covered in this article are neither comprehensive nor in-depth, but the main goal of this article is just to issue that a practical and urgent research topic is ahead and it poses us many challenges and opportunities.

The popularity of high-density flash memory as data storage media has increased steadily for a wide spectrum of computing devices such as PDA's, MP3 players, mobile phones and digital cameras. More recently, computer manufacturers started launching new lines of mobile or portable computers that did away with magnetic disk drives altogether, replacing them with tens of gigabytes of NAND flash memory. Like EEPROM and magnetic disk drives, flash memory is non-volatile and retains its contents even when the power is turned off. As its capacity increases and price drops, flash memory will compete more successfully with lower-end, lower-capacity disk drives. It is thus not inconceivable to consider running a full database system on the flash-only computing platforms or running an embedded database system on the lightweight computing devices. In this paper, we present a new design called in-page logging (IPL) for flash memory based database servers. This new design overcomes the limitations of flash memory such as high write latency, and exploits unique characteristics of flash memory to achieve the best attainable performance for flash-based database servers. We show empirically that the IPL approach can yield considerable performance benefit over traditional design for disk-based database servers. We also show that the basic design of IPL can be elegantly extended to support transactional database recovery.

Flash memory is being rapidly deployed as data storage for mobile devices such as PDAs, MP3 players, mobile phones, and digital cameras, mainly because of its low electronic power, nonvolatile storage, high performance, physical stability, and portability. One disadvantage of flash memory is that prewritten data cannot be dynamically overwritten. Before overwriting prewritten data, a time-consuming erase operation on the used blocks must precede, which significantly degrades the overall write performance of flash memory. In order to solve this “erase-before-write” problem, the flash memory controller can be integrated with a software module, called “flash translation layer (FTL).” Among many FTL schemes available, the log block buffer scheme is considered to be optimum. With this scheme, a small number of log blocks, a kind of write buffer, can improve the performance of write operations by reducing the number of erase operations. However, this scheme can suffer from low space utilization of log blocks. In this paper, we show that there is much room for performance improvement in the log buffer block scheme, and propose an enhanced log block buffer scheme, called FAST (full associative sector translation). Our FAST scheme improves the space utilization of log blocks using fully-associative sector translations for the log block sectors. We also show empirically that our FAST scheme outperforms the pure log block buffer scheme.

In this paper, we describe the design and implementation of the SOP Object Version System which is built upon an object database system, called SOP (SNU ODBMS Platform). SOP is fully compliant with ODMG-93, a standard for object databases proposed by the Object Database Management Group (ODMG). To support object versioning in an ODMG C++ OML (Object Manipulation Language) environment, the SOP Object Version System provides a set of APIs (Application Programming Interfaces) as a class library. One important design goal of the SOP Object Version System was to achieve full compliance with ODMG-93 standard. That is, in designing the class library, we tried to utilize the ODMG-93 C++ OML interface as much as possible, while preserving its semantics as defined in ODMG-93. Our object version model follows the basic functionalities of mainstream object version models. Although this approach burdens programmers with the management of the application-specific version policy, it helps users to apply the SOP Object Version System to diverse application areas. Copyright © 1999 John Wiley & Sons, Ltd.