느린 임의 읽기 성능을 가진 하드디스크에 비해, 플래시메모리는 전자적으로 동작하므로 빠른 임의 접근 속도를 제공하고 순차 읽기와 임의 읽기의 성능 차이가. 따라서 선택도가 높은 경우에도 인덱스 기반 접근 방식이 테이블 스캔 방식에 비해 우수할 수도 있다. 하지만, 기존 인덱스 기반 접근 방식을 사용하는 경우, 일정 이상의 선택도(예: 10%)에서는 테이블 스캔 방식에 비해 여전히 성능이 나쁘다. 본 논문에서는 플래시 메모리 SSD상에서 인덱스 기반 새로운 접근 방법인 pSIDX(partial Sorted Index Scan)을 제안한다. 우선, 인덱스 기반의 테이블 접근 시에 페이지 번호를 기준으로 인덱스 엔트리를 정렬해서 접근하는 방식의 우수성을 보인다. 하지만, 이 방식은 검색 결과의 정렬성을 잃게 된다. 이를 다시 인덱스 키 기준으로 재 정렬하기 위해, 기존 외부합병정렬 대신에 인덱스를 활용하는 기법을 제시한다. 이 기법을 사용함으로써 플래시 메모리 SSD상에서 선택도 50%까지 테이블 스캔에 비해 성능 우위를 얻을 수 있다.
In contrast to harddisks with slow random read latency, electronic flash memory shows fast random access time, and thus the performance gap between sequential and random access to the data pages is very small, though not negligible. Therefore, with flash memory SSDs, the index scan may outperform the full table scan even when the ratio of randomly accessed data pages in a table is very high. With non-clustered indexes, however, the index scan is still inferior to the full table scan even when the predicate selectivity is less than 10%. In this paper, we propose a new approach, pSIDX, to use partial sorted index scan for flash memory SSDs. First, we revisit the sorted index scan. Sorted index scan can outperform the full table scan in a wide range of selectivity. Meanwhile, it can lose the sortedness of index-based scan. Instead of using the naive external merge sort, we propose an efficient re-sorting scheme of the retrieved records, which exploits the index itself. Using this scheme, we show that the sorted index scan can outperform the full table scan in flash memory SSD by up to 50% selectivity.
