Scan and join operators for asymmetric media

Abstract

Solid State Drive (SSD) has become an attractive alternative for storing large databases. SSDs do not present mechanical parts in their assembly. Consequently, SSD has different characteristics and capabilities than that of Hard Disk Drive (HDD). The computer industry is moving towards the construction in large scale of chips with hundreds of cores in order to increase on-chip parallelism. One of the most important features of SSDs is the fact that they implement different levels of internal parallelism for executing read/write operations. Computers with SSD that provides petabytes of storage area is emerging. Nonetheless, database systems were designed based upon two premises. The rst one is the usage of HDD for storing databases. The second premise is that distributed database systems could scale beyond what a single-node Database Management System (DBMS) can support. However, the latter premise only holds for a small number of CPU cores in a node and for a limited number of nodes. Thus, to fully exploit benets provided by the parallelism and high Input/Output Operations Per Second (IOPS) rates supported by many-core machines with SSDs, database systems should be aware of upcoming CPUarchitectures and storage technologies. Thus, this research claims that to take full prot from SSD characteristics, DBMS's components should be aware of read/write asymmetry in SSD devices. It is well-known that the join operation is the query operator which requires the highest amount of accesses (read/write operations) to the secondary memory. This dissertation presents new scan algorithm and a new join algorithm, called respectively Divide and Conquer Scan (DaC Scan) and Divide and Conquer Join (DaC Join). The key goal of these algorithms are take advantage of the SSD's internal parallelism devices, DaC Join also reduces the amount of write operations during the execution of any join operation R S. By making less writes, we intend to extend the lifetime of SSD media by requiring less main memory space. Furthermore, the proposed operators are evaluated by, effectiveness and ef ciency, measured experiments on a database with the TPCH benchmark. The achieved results have shown that the proposed algorithms are quite efcient. For instance, DaC Join can reduce up to 77% of the amount of write operations w.r.t. and the number of write operations presented by Flash join (TSIROGIANNIS et al., 2009; GRAEFE; HARIZOPOULOS, 2010), and, consequently, it can be up to 61% faster than Flash join.