결과보고서

오픈 소스 데이터베이스 시스템을 이용한 플래시 메모리 SSD 기반의 질의 최적화 기법 연구 A Study on Flash-based Query Optimizing in PostgreSQL 황다솜 1) ㆍ안미진 1) ㆍ이혜지 1) ㆍ김지민 2) ㆍ정세희 2) ㆍ이임경 3) ㆍ차시언 3) 성균관대학교 정보통신대학 1) ㆍ시흥매화고등학교 2) ㆍ용화여자고등학교 3) 멘토: 이상원 1) ㆍ이은미 2) 성균관대학교 정보통신대학 1) ㆍ알티베이스 2) 초록 플래시메모리 Solid-State Device(SSD)의 시장 점유율을 점점 늘어나고 SSD를 적용한 컴퓨팅 환경이 보편화 되었지만 대부분의 데이터베이스 시스템(DBMS)은 여전히 하드디스 크를 위한 정책을 고수하고 있다. 따라서 하드디스크와 차별화된 SSD의 특징을 이해하고 이 특성을 활용할 수 있도록 기존의 스캔 기법의 진화(Evolution)가 필요한 시점이다. 본 논문에서는 기존의 두 개념, 정렬 인덱스 스캔[1]과 병렬 동기I/O(Parallel Synchronous I/O)[2]를 재검토하고 두 개념을 결합한 플래시 메모리를 위한 차세대 스캔기법을 오픈 소 스 DBMS인 PostgreSQL에 구현하였다. 임의 데이터에 대해서 본 논문에서 구현한 스캔기 법과 DBMS 가장 기본 스캔기법인 전체 테이블 스캔(Full table scan)과 성능을 비교하였 을 때, 스토리지가 SSD인 환경에서 동시 사용자가 20명인 경우, 최대 약 3.8배의 성능이 향상되었다. TPC-H의 Q15를 수행하였을 경우, 1.5배 성능이 향상되었다. 키워드: 플래시 메모리(Flash-SSD), 데이터베이스 시스템(DBMS), 인덱스 스캔(Index scan), 병렬 동기 입출력(Parallel Synchronous I/O), TPC-H, PostgreSQL

Ⅰ. 서론 지난 10여 년 동안, 플래시메모리 Solid-State Device (이하 SSD)의 활용범위 가 점점 넓어져 현재 모바일 기기들은 물론 노트북, 개인용 컴퓨터, 산업용 서버 등에서 하드디스크를 대체하는 스토리지로서 널리 사용되고 있다. SSD는 가볍고 전력효율이 좋으며 견고하여 외부 충격에 강하다. 또한 전자적으로 동작하기 때문에 순차적 I/O (Sequential I/O) 와 랜덤 I/O (Random I/O)간의 성능차이도 비교적 적은 편이다. 이에 반해, 하드디스크는 기계적으로 동작하 기 때문에 데이터를 찾는 시간(seek time and rotation time)이 I/O 요청 패턴에 따 라 성능 차이가 매우 크다. 또한 이 기계적 이 부분은 외부 충격에 매우 약하고 무겁다. 이러한 SSD의 장점과 하드디스크의 가격 경 쟁력 약화로 인해 스토리지 시장에서의 플래 시 메모리의 입지는 점점 더 확장될 것이다. 하지만, Oracle, PostgreSQL, MySQL 등 의 기존의 데이터베이스 시스템(이하 DBMS) 들은 수십 년 간 스토리지 시장을 장악하고 있는 하드디스크의 단점을 극복하기 위해 발 전하였기 때문에 SSD의 높은 보급률에도 불 구하고 기존의 DBMS의 최적화기 (Optimizer)와 쿼리 플래너(Query planner) 는 여전히 하드디스크에 최적화된 정책들을 사용하고 있다. 예를 들어, 인덱스 스캔 (Index Scan, IDX)을 활용할 수 있는 상황 에도 전체 테이블 스캔(Full Table Scan, 이하 FTS)을 선호하는 등 SSD의 빠른 랜덤 읽기나 내부 병렬성(Internal parallelism) 등을 제대로 활용하지 못하고 있다. 하드디 스크와 차별화 된 SSD의 특징을 이해하고 이 특성을 활용할 수 있도록 기존의 스캔기 법에서의 진화가 필요한 시점이다. 따라서, 본 논문에서는 기존의 논문에서 제안하였던 정렬 인덱스 스캔(Sorted index scan)[1]과 병렬 동기 I/O(Parallel Synchronous I/O, 이하 P-sync I/O)[2]를 다시 검토하고 이 두 개념을 결합하여 SSD 를 위한 차세대 scan operator를 오픈 소 스 DBMS인 PostgreSQL에 구현하였다. Synthetic data를 이용한 실험을 통해 새 로이 구현된 scan operator와 기존의 대표 적인 scan operator인 full table scan, index scan을 비롯하여 정렬 인덱스 스캔과 P-sync I/O만 적용된 index scan, 총 4가 지의 scan operator들과의 성능을 비교 하 였다. 스토리지가 SSD인 환경에서, 단일 사 용자의 경우, Full table scan(이하 FTS)보 다 최대 약 3배, 동시 사용자가 20명인 경 우, 최대 약 3.8의 성능이 향상 되었다. 스 토리지가 하드디스크인 환경에서, 단일 사용 자의 경우 최대 약 1.18배 성능이 향상되었 으나 동시 사용자가 20명인 경우, 약 3.4배 성능이 향상되었다. 본 논문에서 구현한 스 캔 기법이 SSD 환경뿐만 아니라 HDD환경 에서도 충분히 가용가치가 있다는 점을 확인 하였다. 또한 TPC-H 벤치마크에 대해서도 실험을 진행하였다. TPC-H의 Q15를 수행해 본 결과, PostgreSQL을 튜닝하지 않고 쿼리 를 수행한 결과보다 약 1.5배 성능이 향상되 었다. 본 논문의 나머지 구성은 다음과 같다. 2 장에서는 앞서 언급한 정렬 인덱스 스캔과 P-sync I/O에 대해 살펴보고 동시에 본 논 문에서 구현한 스캔 기법에 대해 설명한다. 3장에서는 본 논문에서 진행한 실험에 대해 설명하고 4장에서는 결과 분석을 다룬다. 마 지막으로 5장에서는 요약 및 논문의 결론을 맺는다. Ⅱ. 플래시 메모리 SSD 기반의 질의 최적화 기법 2장에서는 정렬 인덱스 스캔[1]과 P-sync I/O[2]에 대해 설명한 후, 두 개념을 결합한 스캔 기법에 대해 소개하고 이 기법이 왜 SSD에 적합한지에 대해 기술한다. 1. 정렬 인덱스 스캔[1]

정렬 인덱스 스캔은 비 군집 인덱스에 대 그림 1 Index scan with P-sync I/O on non-clustered index 예시 한 인덱스 스캔의 성능을 향상시키기 위해 제안된 방법[book]으로 인덱스 엔트리에 저 장된 레코드 식별자(record id, rid)를 디스 크의 데이터 페이지 식별자(page id)의 순서 로 정렬한 후, 정렬된 레코드 식별자를 이용 하여 데이터 레코드에 접근하는 방식이다. 레코드 식별자를 데이터 페이지 식별자 순서 로 정렬하여 접근하기 때문에 한 데이터 페 이지에 대한 접근은 단 한번만 이루어진다. 이는 기존의 인덱스 스캔이 비 군집 인덱스 를 이용하여 데이터 레코드에 접근할 때 발 생하였던 동일한 데이터 페이지에 대한 무작 위 반복 접근의 문제점을 해결한 스캔 기법 이다. SSD를 스토리지로 사용한 환경에서, 비 군집 인덱스에 대하여 정렬 인덱스 스캔 을 활용할 수 있는 선택도의 비율은 기존의 인덱스 스캔의 비율(10%)보다 매우 높다 (50%)[3]. 하지만 정렬 인덱스 스캔을 사용 하면 인덱스 순서로 정렬된 레코드의 순서 잃어버린다는 단점이 있다. [3]에 따르면 레 코드 재정렬 비용이 인덱스 스캔이 유발하는 무작위 반복 접근 비용에 비해 매우 작아 기 존의 인덱스 스캔보다 여전히 뛰어난 성능을 보인다. 따라서 정렬 인덱스 스캔은 기존의 인덱스 스캔보다 SSD에 더욱 적합한 인덱스 스캔 기법이다. 2. 병렬 동기화 입출력 기법 (Parallel Synchronous I/O, P-sync)[2] P-sync I/O는 Roh et al. [2]에서 SSD 의 채널 레벨의 병렬성 (channel level parallelism)을 활용하기 위해 제안한 입출 력 방식으로 동기 입출력(Synchronous I/O)을 확장한 개념이다. F. Chen et al. [4]에 의하면, 단일 SSD를 스토리지로 사용 하는 환경에서 채널 레벨의 병렬성을 활용하 여 SSD의 I/O 성능 향상을 얻기 위해서 I/O 병렬성을 높이는 것이 가장 중요하다. 이에 따라, [2]는 동작 방식은 동기 입출력과 같으나 한번의 I/O오퍼레이션이 다수의 I/O 요청을 담고 있는 배열을 처리하는 P-Sync I/O를 제안하였다. 3. 플래시-최적화 인덱스 스캔 본 논문에서는 2.1과2.2에서 소개했던 정 렬 인덱스 스캔과 P-Sync의 개념을 결합한 스캔 기법을 플래시-최적화 인덱스 스캔기법 으로써 PostgreSQL에 구현하였다. 동작 알 고리즘은 크게 2 단계로 나눌 수 있다. 첫 번째 단계에서는 접근해야 할 레코드 식별자 를 할 인덱스 엔트리 정보를 에서 얻은 후, 데이터 페이지 식별자 순서대로 정렬을 한

다. 두 번째 단계에서는 해당 배열을 미리 P-sync I/O를 통해 I/O 요청을 묶어서 한 꺼번에 이슈한다. 한 번에 요청할 I/O의 개 수는 multiple I/O factor라는 값으로 설정 이 가능하다. 따라서 같은 데이터 페이지에 대한 반복읽기를 피하고 동시에 여러 개의 I/O를 요청하기 때문에 플래시 SSD의 내부 병렬성을 활용할 수 있다. 그림 1은 플래시 최적화 인덱스 스캔의 예시이다. 이 예제에 서는 Multiple I/O factor가 5이기 때문에 한 배열에 5개의 I/O 요청을 저장 할 수 있 다. 우선 인덱스 엔트리에서 접근해야 할 데 이터 페이지 식별자의 정보를 얻어 임시 배 열에 저장 한 다음, 임시 배열을 데이터 페 이지 식별자 순서로 정렬하여 I/O request 배열을 저장한다. 정렬된 I/O 요청 배열의 순서는 {0, 1, 4, 7, 9 }이다. 정렬된 I/O 요 청 배열(하늘색 상자)은 P-sync I/O에 의해 한 번의 I/O operation을 통해 처리된다. Ⅲ. 실험 및 방법 본 논문에서는 임의 데이터(Synthetic data)와 벤치마크 TPC-H를 통해 생성한 실 제 데이터(Real data)에 대하여 여러 가지 스캔 기법의 성능을 측정하는 실험을 진행하 였다. 각 데이터 군에 대한 실험설명은 해당 실험을 설명하는 장에서 자세히 설명한다. 1. 임의 데이터 임의 데이터 군에 대하여 기본 스캔 기법 인 FTS와 IDX 및 정렬 인덱스 스캔(SIDX), P-sync I/O만 적용된 인덱스 스캔(P-sync) 과 본 논문에서 구현한 스캔기법 (SIDX+P-sync)의 성능을 측정하였다. 실험에 사용된 PC는 8G 램, 3.40GHz Intel core i5 CPU이고 리눅스 3.11.0버전 PostgresSQL 9.3 버전에서 실험을 진행하 였다. 실험에 사용된 디스크는 Samsung 840 Pro SSD(256GB)와 Seagate Barracuda 하드디스크(1TB, 32MB cache) 를 사용 하였다.데이터 페이지 크기는 4KB 이고 PostgreSQL DB 버퍼캐시는 128MB(default)이다. 본 논문에서 실험을 위 해 50바이트 사이즈의 튜플 250만 개를 가 진 테이블(총 20개)로 구성된 DB를 생성하 였다. 각 테이블마다 비 군집 인덱스를 생성 하였다. DBMS에 접속한 사용자 수는 단일 사용자부터 20명 사용자 변화를 주며 실험 하였다. 실험에 사용된 쿼리는 주어진 범위 의 레코드를 탐색하는 쿼리 (Range Query) 로 식 1은 실험에서 사용한 쿼리 이다. 예제 쿼리는 talbe_1의 인덱스가 생성된 index_column값이 min과 MAX값 사이에 존재하는 레코드의 column_1의 값을 출력 한다. 본 논문에서의 선택도(Selectivity)는 논리적 선택도로 쿼리의 min과 MAX을 통 해 선택도를 조절하였다. 실험에서의 multiple I/O factor의 값은 128이다. 2. TPC-H Benchmark factory라는 프로그램을 이 용하여 TPC-H 데이터와 쿼리를 생성하였다 (클러스터링 팩터 값은 1이다). 총 22개의 TPC-H 쿼리 중 Q15에 대하여 PostgreSQL 서버가 튜닝을 안 했을 경우와 튜닝을 했을 경우에 대하여 스캔 기법의 성능을 측정하였 다. 실험 PC환경은 임의 데이터에 대한 실 험을 진행한 환경과 동일하고 실험에 사용된 저장장치 또한 동일하다. PostgreSQL는 Oracle과 같이 쿼리를 수행할 때 힌트를 줄 수 없고 서버 환경변수를 이용하여 서버를 튜닝 할 수 있다. 따라서 쿼리를 수행할 때 마다 서버 환경변수를 이용하여 서로 다른 스캔 기법 선택하였다. Q15 및 PostgreSQL 의 환경변수는 Ⅶ. 부록에서 확인 할 수 있 다. Q15를 수행 할 때, h_supplier 테이블 에 생성된 h_supplier_idx1과 h_lineitem에 생성된 h_lineitem_idx3을 이용한다. 각각의 인덱스는 비-군집 인덱스(non-clustered index)이다.

그림 2 성능향상 비율 그래프(동시사용자 20명, SSD) Ⅳ. 결과 및 토론 1. 임의 데이터 그림 2와 3은 동시 사용자가 20명일 때, SSD와 하드디스크 각각에 대한 실험결과에 대한 그래프이다. 그림의 x축은 선택도를, y 축은 FTS를 기준으로 각 스캔 기법들의 성 능 향상비율를 나타낸 값이다. 각각의 스캔 기법들의 쿼리 수행시간을 측정 한 후, FTS 의 실행시간으로 나눠 해당 비율을 구하였 다. 따라서 FTS의 실행시간보다 짧은 경우 1보다 높은 값을 가지고 긴 경우 1보다 작 은 값을 가진다. 1.1. SSD 단일 사용자인 경우, 선택도가 1%와 2% 일 경우는 인덱스 스캔과 정렬 인덱스 스캔 은 같은 수의 I/O를 이슈하기 때문에 성능 차이가 거의 없지만 선택도 4% 이상일 경우 부터 정렬 인덱스 스캔의 성능이 인덱스 스 캔의 성능보다 뛰어난데 이는 인덱스 스캔이 유발하는 동일한 페이지 무작위 반복 접근 때문이다. P-sync를 사용한 인덱스 스캔의 경우 랜덤 I/O를 유발하나 multiple I/O를 이슈하기 때문에 SSD의 내부 병렬성을 활용 하기 때문에 전체 테이블의 80%를 접근하는 선택도 6%까지 FTS보다 최대 2.5배 이상의 성능향상을 보였지만 인덱스 스캔이 유발하 는 동일한 페이지 반복 접근 때문에 선택도 가 높아질수록 점점 성능이 저하된다. 본 논 문에서 구현한 스캔 기법의 경우, 순차적 읽 기에 대한 multiple I/O를 이슈하기 때문에 FTS와 동일한 데이터 페이지를 읽어야하는 선택도 10%인 경우에도 FTS보다 10% 향상 된 성능을 보인다. 동시사용자가 20명일 경 우, 동시 사용자들이 이슈하는 I/O에 의해 SSD의 내부 병렬성을 활용하기 때문에 선택 도가 2%인 경우에도 모든 스캔 기법이 FTS 보다 더 좋은 성능을 보이지만 선택도 4% 경우부터는 인덱스 스캔과 P-sync를 사용하 는 인덱스 스캔 모두 FTS 성능의 약 50%~ 25% 정도의 성능을 보인다. 두 스캔 기법의 성능 저하 원인은 단일 사용자의 경우와 같 SELECT column_1 FROM table_1 WHERE index_column BETWEEN min AND MAX; 식 1. 실험에 사용된 예제 쿼리

그림 3 성능향상 비율 그래프 (동시사용자 20명, HDD) 은 이유이다. 정렬 인덱스 스캔의 경우는 전 체 테이블보다 접근해야하는 데이터양이 적 을 때까지(선택도 8%) FTS보다 뛰어난 성능 을 보이고 선택도가 10%인 경우는 FTS와 비슷한 성능을 보인다. 정렬 인덱스 스캔에 P-sync를 결합한 기법은 multiple I/O를 처 리하기 때문에 전체 테이블을 접근하는 것과 동일한 양의 데이터를 접근하는 선택도 10% 인 경우에도 FTS 대비 약1.7배의 성능이 향 상되었다. 1.2. 하드디스크 하드디스크 환경에서 실험한 경우에도 본 논문에서 구현한 스캔 기법을 통해 인덱스를 이용한 스캔 기법의 성능향상을 확인하였다. 단일 사용자의 경우, 약 18%정도의 성능이 향상되었고 동시 사용자가 20명인 경우, 최 대 3.4배까지 성능이 향상되었다. P-sync에 의한 성능 이득(gain)보다는 하드디스크인 내부의 prefetch기능으로 순차적 읽기 요청 을 처리하는데 뛰어나고 동시 사용자들에 의해 단일 사용자인 경우보다 더 많은 순차 적 I/O가 이슈 되면서 획득한 성능 향상으 로 분석된다. 2. TPC-H 그림 4는 서버 튜닝을 안 했을 경우 Q15 를 수행한 시간과 서버 튜닝을 통해 직접 스 캔 기법을 선택하여 Q15를 수행한 시간을 나타낸 그래프이다. x축은 쿼리 수행 시간 을, y축은 스캔 기법 나타낸다. 실험결과는 단일 사용자가 해당 쿼리를 수행한 결과이 다. 서버 튜닝을 안 했을 경우, PostgreSQL 은 인덱스 스캔과 비트맵 스캔의 조합으로 쿼리를 수행하였고 수행 시간은 약 9.6초이 다. 비트맵 스캔은 PostgreSQL이 제공하는 기본 스캔 기법 중 하나로 동작방식은 정렬 인덱스 스캔과 비슷하다. 인덱스 스캔으로만 쿼리를 수행할 경우 약 8초로 PostgreSQL 서버의 기본 설정보다 약 1.6초의 성능이 향 상되었다. 비트맵 스캔을 수행할 때 보다 인 덱스 스캔을 수행 할 때, 랜덤 읽기를 유발 함에도 불구하고 SSD의 빠른 랜덤 읽기 덕 분에 성능이 향상되었다. 마지막으로 본 논 문에서 구현한 인덱스 스캔(SIDX+Psync)만 으로 쿼리를 수행한 결과는 약 6.4초이다. 앞서 임의 데이터에 설명하였듯이 정렬 인덱 스 스캔을 통해 랜덤 접근 및 반복 읽기를

그림 4 스캔 기법 별 Q15 수행 결과 제거하고 병렬 동기화 입출력을 통해 SSD 내부 병렬성을 활용함으로써 PostgreSQL의 성능을 향상시켰다. Ⅴ. 결론 및 향후연구 본 논문에서는 기존의 연구들에서 발표된 Sorted index scan과 P-sync I/O를 오픈 소스 데이터베이스 시스템인 PostgreSQL에 구현하여 두 개념을 동시에 활용하는 스캔 기법에 대해 소개하였다. 임의 데이터 군에 대한 실험을 통해 본 논문에서 구현한 스캔 기법은 Flash SSD의 내부 병렬성의 특성과 빠른 순차적 읽기를 이용하기 때문에 Index scan은 물론 Full table scan에 비해 SSD 환경의 경우 최대 약 3.8배의 성능 향상을 확인하였다. HDD환경의 경우에도 HDD의 pre-fetch기능으로 최대 약 3.4의 성능향상 을 확인하였다. 또한 SSD 환경뿐만 아니라 HDD환경에서도 충분히 활용가치가 있다는 점을 확인 하였다. 또한, TPC-H 벤치마크 실험을 통해 본 논문에서 구현한 플래시-최 적화 인덱스 스캔기법이 PostgreSQL의 서 버를 튜닝하지 않았을 경우보다 약 1.5배 정 도 성능이 향상 되었다. 이는 임의 데이터에 서 수행한 쿼리보다 복잡한 쿼리를 수행하였 고 단일 사용자 환경에서만 수행하여 SSD의 내부 병렬성을 충분히 활용하지 못하였기 때 문이다. 향후연구를 통해 본 논문에서 구현한 인덱 스 스캔과 기존의 여러 조인 기법을 함께 연 구하여 복잡한 쿼리에 대해서 최적화된 조합 에 대해 연구할 예정이다. Ⅵ. Acknowledge 이 연구는 2015년 한국연구재단과 한국여 성과학기술인지원센터의 지원을 받아 연구되 었습니다. Ⅶ. 참고문헌 [1] R. Ramakrishnan and J. Gehrke. Database Management Systems(3rd ed),mcgraw Hill. [2] Hongchan Roh et al,"b+-tree Index Optimization by Exploiting Internal Parallelism of Flash-based Solid State Drives, Proceeding of the VLDB Endowment, Vol. 5,No.4

[3] Jae-Hyo Lee et al., Revisiting Sorted Index Scan with Flash SSDs, EDB 2010, 2010. [4] F. Chen et al, Essential roles of exploiting internal parallelism of flash memory based solid state drives in high-speed data processing, HPCA, pages 266-277, 2011.

Ⅷ. 부록 A. Q15 (Q15-1) DROP VIEW REVENUE0 (Q15-2) CREATE VIEW REVENUE0 (supplier_no,total_revenue) AS SELECT l_suppkey, sum(l_extendedprice * (1-l_discount)) FROM H_Lineitem WHERE l_shipdate >= '1993-09-01' and l_shipdate < '1993-12-01' group by l_suppkey; (Q15-3) SELECT s_suppkey, s_name, s_address, s_phone, TOTAL_REVENUE FROM H_Supplier, REVENUE0 WHERE s_suppkey = supplier_no AND TOTAL_REVENUE = (SELECT MAX(TOTAL_REVENUE) FROM REVENUE0) ORDER BY s_suppkey; (Q15-4) DROP VIEW REVENUE0 B. PostgreSQL sever 환경변수(postgres.conf) 해당 변수들의 기본 값은 모두 on 이며 쿼리 플래너가 쿼리 실행 계획을 짤 때, 모든 스캔 기법을 고려한다. 값이 Off일 경우, 해당 스캔 기법은 고려대상에서 제외된다. enable_bitmapscan enable_indexscan enable_seqscan enable_hashjoin enable_mergejoin enable_nestloop Bitmap scan 선택가능 여부 결정 Index scan 선택가능 여부 결정 Full table scan 선택가능 여부 결정 Hash join 선택가능 여부 결정 Merge join 선택가능 여부 결정 Nested loop join 선택가능 여부 결정 표 1. PostgreSQL 환경변수