面向非易失性存储器的多表连接写操作的优化研究

Multi-table join operation is one of the most important operations in lots of systems, such as embedded databases and data warehouses. Hence improving the performance of Multi-table join operation can accelerate the speed of data processing and analysis. The overall performance of the systems can be also enhanced. Emerging non-volatile memories (NVMs) have been widely discussed to complement or substitute DRAM in memory hierarchy in recent years. When the NVM is incorporated into memory hierarchy, it has fast read/write speed, high storage density, byte addressability, low power consumption and persistency. However, employing existing multi-table join algorithms directly on NVM incurs two big problems: (1) existing algorithms cannot fully exploit the benefits of NVM which may stand in the way of improving the performance of systems. (2) Existing algorithms produce large intermediate table size and a large number of copies of data, which causes a lot of NVM writes to the storage device. Since NVM suffers from the limitation of write endurance (i.e., once the number of writes of a memory cell exceeds the endurance limit, the NVM chip is considered worn-out), existing multi-table join algorithms can easily make NVM device breakdown. In this paper, we consider the limited write endurance of NVM and aim to reduce the number of NVM writes caused by multi-table join algorithms. First, we propose an algorithm, NVjoin, to select an optimal order for joining multiple tables. NVjoin algorithm analyzes the relation between tables according to the joining statements entered by user. And then estimate the size of the intermediate tables using sampling techniques. In this way, we can obtain an optimal order so as to reduce the number of NVM writes. Second, a new data structure, LWTab, is designed to keep the intermediate results of multi-table join algorithms. The new structure makes full use of the byte-addressability of NVM. Specifically, instead of storing data, we store the address of data in LWTab, which can significantly reduce the number of copies of data and the size of intermediate tables. In this way, the number of NVM writes can be also significantly reduced. This paper employs DRAM to simulate NVM and a lot of experiments (including timing performance, number of NVM writes) have been carried out with three different join algorithms. Experimental results show that the algorithms proposed in this paper achieve better results not only in timing performance but also in number of NVM writes. Specifically, compared with multi-table join algorithms in MySQL, a widely used database, NVjoin algorithm can reduce the number of NVM writes by 104.21 times and achieve 65.01% improvements in timing performance. Moreover, when LWTab structure is employed, the NVjoin algorithm can further reduce the number of NVM writes by 16.74 times and achieve 71.86% improvements in timing performance.