Optimizing index scan on flash SSDs

다국어 초록 (Multilingual Abstract)

Because the random IO latency is far lagging behind the bandwidth in mechanical hard disk, hard disk has very low access performance. Meanwhile, electro-mechanical flash memory SSDs show very fast latency in random reads and performance gap between sequential and random read to data page is relatively small. For this reason, index-based scan is considered to become more outperform than full table scan in flash memory storage devices. Recent results indicate, however, the existing index scan can outperform the full table scan only in very low selectivity.
In this paper, we research how to optimize the index scan on flash memory SSDs. First, we empirically demonstrate that compared to full table scan, the index scan has much more poorly performance even when the selectivity of selection predicate is less than 10%. It is mainly because of repetitive IOs of same data pages during the index scan due to limited size of buffer cache. Second, we revisit the idea of sorted index scan. It first sorts the index entries in the order of record identifier before fetching data pages. So it can avoid the unnecessary repetitive IOs of the same pages. Our experimental result shows that it can outperform the full table scan when the selectivity is larger than 30%. By the way, one serious drawback of the sorted index scan is that lose the sortness in index key order and it is not sorted any more in the index key order. Third, in order to efficiently re-sort the result from the sorted index scan, we propose a new external index-based sort algorithm, partitioned sort, which exploits the information of key value distribution in the index leaf nodes while partitioning the data to be sorted. The traditional external merge sort might use multiple passes depending on the data size and the sort memory size. On the other hand, partition sort can sort data in one pass regardless of the available sort memory size.

목차 (Table of Contents)

• 1. ABSTRACT
• 2. INTRODUCTION
• 3. BACKGROUND
• 4. SORTED INDEX SCAN
• 5. INDEX-BASED PARTITIONED SORT
• 6. CONCLUSION
• 7. REFERENCES