[논문]효율적인 ROLAP 큐브 생성 방법

김명; 송지숙

문제 정의

디스크 I/O는 메모리에 제약이 있는 경우, 사실 테이블이 희박한 경우, 사실 테이블의 차원이 높은 경우를 대상으로 계산하였다. 메모리 크기에 제약이 있는 경우를 살펴보자. 메모리가 충분하지 않으면 New 알고리즘은 2개 이상의 차원으로 사실 테이블을 슬라이스한다.
본 연구에서는 MOLAP 큐브 생성 알고리즘을 사용하여 ROLAP 집계 테이블을 신속하게 생성하는 알고리즘을 제안하였다. 이 알고리즘은 가장 큰 차원들을 기준으로 사실 테이블을 슬라이스하고, 집계 테이블 생성에 필요한 메모리를 체계적으로 재사용함으로써 큐브 생성에 필요한 메모리 사용량을 크게 줄인다.
본 연구에서는 MOLAP 큐브 생성 알고리즘을 사용한 효율적인 ROLAP 큐브 생성 방법을 제시한다. 멤버의 수가 가장 큰 차원을 기준으로 사실테이블을 조각내어 놓으면, 사실테이블을 1번만 스캔하면서 최소의 집계 연산만으로 집계 테이블들을 생성할 수 있고, 이 과정에서 사용되는 메모리는 가장 작은 1차 집계 테이블 1개와 이로부터 생성 가능한 2차 이상의 집계 테이블들의 저장공간 뿐이라는 점에 착안하여 시간/공간적 성능을향상시킨다.
이제 본 연구에서 제안하는 ROLAP 큐브 생성 알고리즘을 소개한다. 이는 분석대상인 사실테이블을 멤버의 수가 가장 큰 차원을 기준으로 슬라이스(slice)해 놓고 집계 연산의 순서를 조정함으로써 큐브를 생성할 때 필요한 메모리 양과 디스크 I/O를 감소시키는 방법이다.

가설 설정

가능한 한 정확한 분석결과를 얻기 위해 ZDN이 사용한 데이타 세트를 사용하였다. 각 실험결과는 10회 실시한 후 평균값으로 나타내었다 사실테이블의 각 열은 4바이트를 차지하는 것으로 가정하고, ZDN과 마찬가지로 데이타는 큐브 내에 균일하게 분포되었다고 가정하였다. 실험에 사용한 데이타 세트는 다음과 같다.
메모리가 85MB인 경우 ZDN 알고리즘은 큐브 생성에 필요한 메모리를 충분히 가지고 있고, New 알고리즘은 사실 테이블을 슬라이스하는데 1 개의 차원만 사용하면 된다. 메모리가 40MB 인 경우는 ZDN 알고리즘의 경우 서브 트리 2개가 발생하고 New 알고리즘은 2개의 차원을 기준으로 사실 테이블을 슬라이스 해야 한다, ZDN 알고리즘의 경우는 큐브 생성 도중에 디스크 I/O를 하는 경우 데이타 희박성을 줄이기 위해 배열을 압축한 채로 디스크 I/O를 한다는 가정을 하였다. 그럼에도 불구하고 그림 5(2)와 같이 New 알고리즘이 디스크 I/O를 작게 한다는 것을 알 수 있다.
사실 테이블의 밀도가 낮은 경우를 살펴보자; 밀도가 0.1%인 4차원 사실 테이블을 가정하자. 각 차원의 크기는 100, 200, 1000, 100000이다.

제안 방법

7 버전의 운영체제가 장착된 Sun UltraSparc 10 워크스테이션을 사용하였다. 가능한 한 정확한 분석결과를 얻기 위해 ZDN이 사용한 데이타 세트를 사용하였다. 각 실험결과는 10회 실시한 후 평균값으로 나타내었다 사실테이블의 각 열은 4바이트를 차지하는 것으로 가정하고, ZDN과 마찬가지로 데이타는 큐브 내에 균일하게 분포되었다고 가정하였다.
1%인 6차원 사실 테이블을 선택하였다. 각 차원의 크기는 10, 10, 100, 100, 200, 10000으로 하였다. 테이블의 크기는 28GB이다.
큐■브 래티스로부터 정렬 비용을 최소화시키는 큐브 트리를 생성한다. 그 다음에 파이프라인 방식으로 집계 테이블들이 계산될 수 있도록 큐브 트리를 몇 개의 패스(path)로 분해하고, 각 패스를 따라 가면서 집계 테이블을 파이프라인 방식으로 계산한다. PipeSort 알고리즘의 단점은 미리 추정된 정렬 비용을 사용하여 큐브 트리를 결정한다는 것이다.
이 작업을 위해 필요한 총 메모리는 AB, A, B, q〃(상수 개) 이다 집계 테이블 AB, AC, BC, C는 슬라이스된 사실 테이블을 읽는 동안에 계산이 완료된다. 그 후에는 계산이 완료되어 현재 메모리에 있는 AB로부터 디스크 엑세스 없이 를 루트로 하는 트리에 속한 모든 집계 테이블을 계산한다. 즉, 그림 1(3)의 점선 타원형 안에 있는 집계 테이블 A, B, a〃이 파이프라인 방식으로 계산된다.
ZDN 알고리즘은 배열을 이용하여 집계 테이블을 계산하기 때문에 정렬 기반 ROLAP 큐브 생성 알고리즘들에 비해 성능이 뛰어나다. 따라서 본 논문에서는 새로운 ROALP 큐브 생성 알고리즘을 제안하고 이 알고리즘의 성능을 ZDN 알고리즘과 비교, 분석하였다.
이 알고리즘은 가장 큰 차원들을 기준으로 사실 테이블을 슬라이스하고, 집계 테이블 생성에 필요한 메모리를 체계적으로 재사용함으로써 큐브 생성에 필요한 메모리 사용량을 크게 줄인다. 메모리 사용량을 감소시켜서 모든 집계 테이블이 메보리 상에서 최소 부모 집계 테이블로부터 생성될 수 있도록 하여 집계 연산의 시간을 감소시켰다. 또한 2차 이상의 집계 테이블들을 생성할 때는 셀을 순서대로 스캔하기 때문에 셀의 인덱스를 계산하는 시간을 줄였다.
본 연구에서 제안한 알고리즘과 ZDN 알고리즘의 속도를 비교해 보기로 한다. 제안한 알고리즘의 성능을 ZDN 알고리즘과 비교하는 이유는 이미 [1] 에서 ZDN 알고리즘이 기존의 ROLAP 큐브 생성 알고리즘들보다 훨씬 효율적이라는 것을 증명해 놓았기 때문이다.
본 연구에서 제안한 알고리즘이 큐브를 생성하는데 사용하는 메모리의 양은 최소 크기 1차 집계 테이블 1개 와이 테이블을 최소 부모로 하는 모든 상위 집계 테이블을 계산하는데 드는 메모리 공간이다. 만약 이만큼의 메모리 공간이 확보될 수 없다면 사살 테이블을 2개 이상의 차원을 기준으로 슬라이스하여 필요한 메모리 공간을 줄일 수 있다.
이를 ZDN 알고리즘이라고 부르기로 한다. 이 알고리즘에서는 ROLAP 사실 테이블을 배열로 변환 한 후에 MOLAP 큐브 생성기를 사용하여 큐브를 생성하고 이를 다시 ROLAP 집계 테이블 저장 방식으로 변환한다. 알고리즘의 첫 단계에서 사실테이블을 메모리에 한꺼번에 로드될 수 있는 크기로 조각(partition)내어 디스크에 저장한다.
즉 한 슬라이스에 속한 튜플들은 동일한 C와 力값을 갖는다. 이제 슬라이스 CiDj (1MCW飾, 를 순서대로 1 개씩 읽으면서 1차 집계 테이블 ABD, ACD, BCD를 계산해 간다. 슬라이스들은 C를 행으로 보고, D를 열로 보았을 때 열우선순서 (column major order)로 읽힌다 예를 들면, C心, C₂Dh G以, .

대상 데이터

디스크 I/O는 메모리에 제약이 있는 경우, 사실 테이블이 희박한 경우, 사실 테이블의 차원이 높은 경우를 대상으로 계산하였다. 메모리 크기에 제약이 있는 경우를 살펴보자.
보자. 말도가 0.1%인 6차원 사실 테이블을 선택하였다. 각 차원의 크기는 10, 10, 100, 100, 200, 10000으로 하였다.
변경한다. 모든 데이타 집합은 4차원이며, 크기는 40X 40x40 X1000이匸데이타의 밀도는 각각 1%, 10%, 25%, 40%이며, 대응되는 사실테이블의 크기는 각각 12.8MB, 128MB, 321MB, 512MB이다.
실험에는 512MB 메모리와 20GB 하드 디스크가 장착되고 SunOS 5.7 버전의 운영체제가 장착된 Sun UltraSparc 10 워크스테이션을 사용하였다. 가능한 한 정확한 분석결과를 얻기 위해 ZDN이 사용한 데이타 세트를 사용하였다.
이 알고리즘은 큐브 트리를 여러 개의 서브 트리로 나누어 서브 트리 한 개씩 처리하는 방법이다. 실험에는 [1]에서 사용한 데이타 세트인 4차원 사실 테이블을 사용하였다 사실 테이블의 각 차원 크기는 40, 40, 40, 1000으로 하였다. 데이타 밀도는 10%으로 하여 사실 테이블에는 6, 400, 000개의 튜플이 있고 사살 테이블이 차지하는 공간은 128MB 이다.
각 차원의 크기는 10, 10, 100, 100, 200, 10000으로 하였다. 테이블의 크기는 28GB이다. 메모리의 크기는 10MB, 500MB인 경우로 정하였다.

이론/모형

메모리가 충분하지 않으면 New 알고리즘은 2개 이상의 차원으로 사실 테이블을 슬라이스한다. ZDN 방법 역시 이를 해결하기 위해 [1]에 제안되어 있는 Multi-Pass 알고리즘을 사용한다. 이 알고리즘은 큐브 트리를 여러 개의 서브 트리로 나누어 서브 트리 한 개씩 처리하는 방법이다.

성능/효과

[1]은 저밀도 큐브의 데이타 압축 방법을 제시하였고, 사용자 질의처리 시에 디스크 블록 읽는 회수를 줄이기 위해 [12]가 제안한 청크단위 배열 저장방식을 기반으로 한 큐브 생성 알고리즘을 제안하였다. [U 에서는 이 알고리즘을 ROLAP 집계 테이블의 생성에 적용하는 방안을 제시하였고, 그 방안이 테이블 상에서 ROLAP 집계 테이블들을 직접 생성하는 것보다 훨씬 효율적이라는 것을 실험적으로 보였다.
또한 알고리즘이 간단하여 구현하여 사용하기 수월하다는 장점을 갖는다. 기존의 ROLAP 큐브 생성 알고리즘들보다 성능이 월등하게 나은 [1]의 큐브 생성 알고리즘과 비교한 결과 본연구에서 제안한 알고리즘이 사실 테이블의 밀도, 차원의 개수에 얀정적이고 효율적이라는 것을 보였다.
실험에는 [1]에서 사용한 데이타 세트인 4차원 사실 테이블을 사용하였다 사실 테이블의 각 차원 크기는 40, 40, 40, 1000으로 하였다. 데이타 밀도는 10%으로 하여 사실 테이블에는 6, 400, 000개의 튜플이 있고 사살 테이블이 차지하는 공간은 128MB 이다. 메모리 크기를 100紬에서 1MB까지 변화시켜 가면서 두 알고리즘의 디스크 I/O 분량을 계산한 것이 그림 5(1)에 있다.
데이타의 밀도가 40% 정도가 되면 ZDN 알고리즘의 경우 데이타 압축단계가 없어진다. 두 알고리즘 모두 베이스 큐브의 밀도가 높아짐에 따라 실행시간이 안정적으로 증가한다는 것을 알 수 있다. 밀도가 10%에서 25%, 40%로 증가할 때 실행 시간이 2.
둘째, [단계 2] 와 [단계 3] 에서는 연산 결과를 디스크에 쓰는 것 이외에 부수적인 디스크 I/O가 전혀 없고, 각 집계 테이블은 집계 연산시간을 최소화하는 부모 집계 테이블(smallest parent)로부터 계산된다. 또한 각 튜플은 집계 연산과정에서 단 한 번만 읽혀진다.
여기서 c의 값이 차원마다 다르게 설정된 이유는 청크 1개가 디스크 블록 크기인 4K 바이트에 근접하도록 하였기 때문이다 그림 2(1)과 같이 모든 차원 멤버의 수가 같은 경우 메모리 사용량이 최대가 되고, 그림 2(2)와 같이 차원 간의 멤버 수가 차이를 보이면 두 방법 모두 메모리를 효율적으로 사용한다는 것을 알 수 있다. 또한 본 연구에서 제안한 알고리즘이 메모리를 더 효율적으로 사용한다는 것을 알 수 있다.
셋째, 사실테이블이 희박한 경우라고 해도 집계 테이블들의 밀도가 높아지므로 배열형태의 집계 테이블을 취급하는 것이 밀도가 지나치게 낮지 않는 한 테이블 형태의 집계 테이블들을 취급하는 것보다 효율적이다. 또한 제안한 알고리즘은 2차 이상의 상위 집계 테이블들을 계산할 때 메모리를 동적으로 할당하여 사용하고 셀들을 항상 정해진 순서대로 스캔하고 생성하기 때문에 셀의 배열 인덱스를 계산하는데 시간이 거의 들지 않는다.
표 3은 1개의 차원을 기준으로 사실 테이블을 슬라이스한 경우를 나타내고, 표 4는 2개의 차원을 기준으로 사실 테이블을 슬라이스한 경우를 나타낸다. 알고리즘은 특히 실제 데이타의 모양에 가까운 차원의 멤버의 개수가 다른 경우에 메모리 사용량이 크게 줄어들어 있는 것을 알 수 있다.
4차원 데이타로, 3개의 차원은 크기가 40이고, 남은 차원은 크기가 각각 400, 1, 000, 10, 000이다. 유효 셀 개수는 모두 6, 400, 000개이며, 데이타의 밀도는 각각 25%, 10%, 1%이다. 따라서 사실 테이블의 크기는 128.
제안하였다. 이 알고리즘은 가장 큰 차원들을 기준으로 사실 테이블을 슬라이스하고, 집계 테이블 생성에 필요한 메모리를 체계적으로 재사용함으로써 큐브 생성에 필요한 메모리 사용량을 크게 줄인다. 메모리 사용량을 감소시켜서 모든 집계 테이블이 메보리 상에서 최소 부모 집계 테이블로부터 생성될 수 있도록 하여 집계 연산의 시간을 감소시켰다.
멤버의 수가 가장 큰 차원을 기준으로 사실테이블을 조각내어 놓으면, 사실테이블을 1번만 스캔하면서 최소의 집계 연산만으로 집계 테이블들을 생성할 수 있고, 이 과정에서 사용되는 메모리는 가장 작은 1차 집계 테이블 1개와 이로부터 생성 가능한 2차 이상의 집계 테이블들의 저장공간 뿐이라는 점에 착안하여 시간/공간적 성능을향상시킨다. 제안한 방법의 효율성은 기존의 ROLAP 큐브 생성 알고리즘들보다 월등하게 속도가 빠른 [1] 의방법과의 비교를 통해 보였다. 논문은 다음과 같이 구성된다: 2절에서 OLAP 큐브 생성과 기존의 연구 결과를 설명하고, 3절에서 새로운 ROLAP 큐브 생성 방법을 제시한다.
비교해 보기로 한다. 제안한 알고리즘의 성능을 ZDN 알고리즘과 비교하는 이유는 이미 [1] 에서 ZDN 알고리즘이 기존의 ROLAP 큐브 생성 알고리즘들보다 훨씬 효율적이라는 것을 증명해 놓았기 때문이다. 또한 ZDN 알고리즘 역시 메모리의 여유가 있는 경우에는 사실 테이블을 한 번만 스캔하면서 MOLAP 큐브 생성알고리즘을 통해 큐브 전체를 생성하므로 본 연구에서 제안한 방법과 유사하면서 효율적인 알고리즘이기 때문이다.
6M 개이다. 차원이 증가할수록 New 알고리즘이 ZDN 알고리즘에 비해 우수한 성능을 보인다는 것을 알 수 있다. 종합적으로, New 알고리즘은 데이타의 밀도, 차원의 증가에 안정적이고 효율적인 알고리즘이다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

효율적인 ROLAP 큐브 생성 방법
An Efficient ROLAP Cube Generation Scheme 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

참고문헌 (13)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

효율적인 ROLAP 큐브 생성 방법 An Efficient ROLAP Cube Generation Scheme 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

참고문헌 (13)

이 논문을 인용한 문헌

저자의 다른 논문 :

김명 (56)

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

효율적인 ROLAP 큐브 생성 방법
An Efficient ROLAP Cube Generation Scheme 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper