| dc.description.abstract | Phase Change Memory (PCM) is a recently developed non volatile memory technology that is expected to provide an attractive combination of the best features of conventional disks (persistence, capacity) and DRAM (access speed). For instance, it is about 2 to 4 times denser than DRAM while providing a DRAM comparable read latency. On the other hand, it consumes much less energy than magnetic hard disks while providing substantially smaller write latency. Due to this suite of desirable features, PCM technology is expected to play a prominent role in the next generation of computing systems, either augmenting or replacing current components in the memory hierarchy. A limitation of PCM, however, is that there is a significant difference between the read and write behaviors in terms of energy, latency, and bandwidth. A PCM write, for example, consumes around 6× more energy than a read. Further, PCM has limited write endurance since a memory cell becomes unusable after the number of writes to the cell exceeds a threshold determined by the underlying chalcogenide glass material.
Database systems, by virtue of dealing with enormous amounts of data, are expected to be prime beneficiaries of this new technology. Accordingly, recent research has investigated how database engines may be redesigned to suit DBMS deployments on PCM, covering areas such as indexing techniques, logging mechanisms, and query processing algorithms. Prior database research has primarily focused on computing architectures wherein either (a) PCM completely replaces DRAM; or (b) PCM and DRAM co exist side by side and are independently controlled by software. However, a third option that is gaining favor in the architecture community is where the PCM is augmented with a small hardware managed DRAM buffer. In this model-referred to as DRAM HARD-the address space of the application maps to PCM, and the DRAM buffer can be visualized as yet another level of the cache hierarchy. With most query processing research preoccupied with the first two models, this third model has remained largely ignored. Moreover, even in the limited literature, the emphasis has been on execution time strategies; the compile time plan selection process itself being left unaltered.
In this thesis, we propose minimalist reworkings of current implementations of database operators, tuned to the DRAM HARD model, to make them PCM conscious. We also propose novel algorithms for compile time query plan selection, thereby taking a holistic approach to introducing PCM compliance in present day database systems. Specifically, our contributions are two fold:
1. PCM conscious operator implementations.
We address the pragmatic goal of minimally altering current implementations of database operators to make them PCM conscious, facilitating an easy transition to the new technology. We target the “workhorse” operators: sort, hash join, and group by. Our customized algorithms and techniques for each operator are designed to significantly reduce the number of writes while simultaneously saving execution time.
Example: For the sort operator, we perform in place partitioning of input data into DRAM sized chunks so that subsequent sorting finishes inside DRAM, thereby avoiding intermediate writes and their latency overheads.
2. PCM aware query optimization.
We redesign the query optimizer to suit the PCM environment. Each new operator implementation is accompanied by simple but effective write estimators, making them suitable for incorporation into the optimizer. Current optimizers typically choose plans using latency based costing with equal costs for reads and writes. PCM’s asymmetric read write nature invalidates these models. We therefore revise the cost models to account for additional write latency and introduce a new write cost metric into plan selection, using the above estimators.
Consequently, the query optimizer needs to select plans that simultaneously minimize writes and response times. We propose two solutions to this dual objective optimization:
• Heuristic propagation algorithm.
Extends the standard dynamic programming plan propagation to drastically reduce the exponential search space. It uses write costs of sub plans at operator nodes to selectively prune dominated candidates.
• Greedy multiple choice knapsack mapping.
Maps the problem to the linear multiple choice knapsack problem and uses its greedy solution to return the final plan. The plan is optimal within the set of non–interesting order plans for a single join order search space and may include a weighted execution of two algorithms at an operator node. While the greedy algorithm offers optimality guarantees in this space, the heuristic approach is attractive due to easier implementation.
Experimental Framework.
Experiments were conducted on Multi2Sim, a state of the art cycle accurate simulator. Since it lacks native PCM support, we extended its memory module to model PCM devices. Specifically:
• Added separate data tracking for DRAM and PCM to implement read before write reduction.
• Modified the timing subsystem to account for asymmetric read write latencies of PCM.
• Introduced the N Chance DRAM replacement policy, shown to work well for PCM based hardware.
Evaluation and Results.
Our techniques were evaluated on end to end TPC H benchmark queries with respect to write counts, response times, and wear distribution. Results indicate that, compared to PCM oblivious counterparts, PCM conscious operators reduce writes by 2–3× while improving response times by ~20–30%. When combined with appropriate plan choices, improvements are even higher.
Example: For Query 19, we observed 64% write savings and response time reduced to two thirds of the original.
Summary.
Our algorithms provide both short term (performance) and long term (endurance) benefits, making them well suited for database engines seeking to leverage the transition to PCM based computing. | |
