RDB 형식의 데이터구조를 이용한 OLAP Server 설계 및 구현 2000.5.29 데이터베이스 연구실 석사 3학기 강 주 영

목표 RDB형식의 자료구조를 기반으로 OLAP기능을 수행한다.

Sample Data Structure Star Schema Store_Dim Time_Dim Product_Dim TimeKey Store_name Region_name Country_name Store_Key Time_Dim ProductKey Month ... Time_Key Product_Dim EmployeeKey Product name Product_Key Sales_Fact TimeKey EmployeeKey ProductKey Sales Product_Key Time_Key Store_Key Dimensional Keys Multipart Key Measures Star Schema

Sample Data Structure Product dimension ( 5 members, no hierarchy ) Time dimension ( 4 members, no hierarchy ) Product_Key Product_name P1 Juice P2 P3 P4 P5 Coke Beer Soap Milk Time_Key Time_name T1 Spring T2 T3 T4 Summer Fall Winter Store dimension ( 6 members, 3 level hierarchies ) Store_Key Store_name Region_name Country_name S1 K-Mart East USA S2 S3 S4 S5 S6 Target Savons LG-Mart Kim’s-Club E-Mart West Central KOREA

Sample Data Structure Fact Table 사실테이블에 대한 인덱스는 없음 사실테이블에 대한 인덱스는 없음 Dimension Key를 position 정보 ( 정수형)으로 바꾸어서 저장 프로그램 구현 시 용이 Chunking 개념을 이용한 데이터 클러스터링에 이용가능 텍스트 모드의 파일이므로 프로그램 상에서는 바이너리 모드로 변환한 파일로 작업

Sample Queries Exact match 봄에 Target에서 판매된 비누의 판매량은? 여름에 미국 동부지역에서 판매된 맥주의 판매량은? Range Query 봄-가을 사이에 LG-Mart에서 판매된 맥주의 판매량은? Slice 여름에 각 상점에서 판매된 각 상품의 판매량은? Dice 봄과 가을에 각 상점에서 팔린 주스, 맥주, 우유의 판매량은? Pivot Row : 지역, Col : 계절, Page : 상점 형태로 현재 화면에 출력이 되고 있는 상태에서, 이를 Row : 상점, Col : 상품, Page : 계절로 바꾸시오 Drill-down Row : 지역, Col : 상품으로 화면에 출력되고 있는 상태에서, 이를 상점별 상품 판매량으로 한 단계 낮추어서 출력하시오 Roll-up Row : 상점, Col : 상품으로 화면에 출력되고 있는 상태에서, 이를 지역별 상품 판매량으로 한 단계 높여서 출력하시오 1 2 3 4 5 6 7

가정 및 구현환경 가정 구현환경 Language : C 큐브 생성을 위해 집계 테이블을 생성하는 경우 사실 테이블의 정렬이 필요한데 이 경우, 데이터 세트가 작아서 사실 테이블 전체를 메모리에 올려 놓고 in-core정렬이 가능하다고 가정한다. ( None external Sorting ) 구현하고자 하는 프로그램은 주어진 데이터 세트와 질의에 해당하는 OLAP연산만을 수행한다. 질의는 질의를 수행하는 각 함수로 수행되며, 필요한 계층정보 및 차원테이블 멤버 정보는 함수의 파라미터를 통해 주어진다. 차원정보와 차원 키 값의 matching cost무시 구현환경 Language : C input file and hierarchy table: Flat text file summary table : binary file

설계 및 구현 Modules Data Loading Fact table loading Conversion to binary mode file Reading hierarchy information Data Loading Cube Summary Operations (base table, hierarchy table) Generation Table Indexing 1 2 3 4

Data Loading Fact table loading Conversion to binary file Text mode의 사실 테이블을 읽음 Tuple형태의 구조체 배열에 데이터를 load Conversion to binary file Random access 가 가능한 binary mode file로 변환 ( indexing시 필요 ) Reading Hierarchy information store dimension에 대한 hierarchy 정보를 담고 있는 File 생성 Tree 형태의 자료 구조 필요 Table형식의 자료구조 이용 Store USA Korea East West Central K-Mart Target Savons LG-Mart Kim’s E-mart Store Region Country 1 2 3 4 5 6

Data Loading Functions 구조체 배열 void initial_array(void) struct tuple{ int pkey; int skey; int tkey; long sales; }tuples[data_MAX]; Functions void initial_array(void) void read_data(struct tuple ps[], int max ) int text_to_bin(void) int read_hierarchy(void) void sortedarray(struct tuple *ps, int I, int order) 1 1 1 3 1 1 2 2 1 1 3 4 1 2 2 1 1 3 2 5 1 3 3 6 ……. 구조체 배열 P_Key S_key R_key Sales 1 3 2 4 5 6

Cube Generation PST, STP, TPS order sorting of data Aggregation Smallest parent를 따라 aggregation해야 하나 ROLAP의 경우 aggregation 과정에 전체 tuple의 Sorting이 필수적. => 각 Sorted order을 이용하여 aggregation ALL R C P S T PR PC RT CT TP ST TPR TPC PS PST STP TPS

Cube Generation Generate separate summary data file for each group-by Functions int tuple_sort(max) void quicksort(struct tuple *ps[], int left, int right, int member) void swap (struct tuple *salesdata[], int i, int j) void innersort(int max) void cube_gen(int max) SUM15.dat PST PS PR PC P STP ALL ST RT CT S R C TPS TPR TPC TP T SUM1.dat Binary Files

Summary Table Indexing Fact table이 Index를 가지지 않으므로 summary table에 대한 indexing만 수행 Index 구조 P,S,T 차원의 계층 level수가 각각 x,y,z 라면 배 Anchor 배열의 수는 ( x+1 ) * ( y +1 ) * ( z+1) 실제 각 배열에는 group-by 명이 저장되어 있음. 질의의 요구사항에 따라 group-by name을 보고 필요한 배열 cell의 위치를 계산하는 scheme 필요 , scheme이 없는 경우 배열을 모두 scan하며 search하는 과정이 필요 scheme 설정이 어려운 경우 2차 Anchor배열을 둘 수 있음 Functions void indexing_sum(void)

Summary Table Indexing AAA AAT ACA ARA ASA ACT ART AST PAA PAT PCA PRA PSA PCT PRT SUM15.dat SUM1.dat Binary Files AAA 000 AAT 001 ASA 010 AST 011 PAA 100 PAT 101 PSA 110 PST 111 Anchor array 2 Anchor array 1

Operations Exact Match 봄에 Target에서 판매된 비누의 판매량은? ( t1, s2, p4) Function : int exact_match(pkey, skey, slevel, tkey, max ) SKEY 의 level에 따라 ( Store, Region, Country ) Store Fact table을 scanning하면서 각각의 key값을 만족하는 tuple을 선택 => 전체 Fact table을 한번 scan해야 함 Region ( Country ) SUM15.dat SUM1.dat Binary Files P1S3T1 P1S3T3 P2S3T1 P2S3T2 P2S3T3 P3S3T1 P3S3T2 P3S3T3 P1S2T1 P1S2T2 P2S2T1 P1S2T3 P2S2T2 P2S2T3 P3S2T1 P3S2T2 P3S2T3 P1S1T1 P1S1T2 P1S1T3 P2S1T1 P2S1T2 P2S1T3 P3S1T1 P3S1T2 P3S1T3 Base Cube AAA 000 AAT 001 ASA 010 AST 011 PAA 100 PAT 101 PSA 110 PST 111 Anchor array 2 Anchor array 1

Operations Range Query 봄-가을( t1-t3 ) 사이에 LG-mart(s4) 에서 판매된 맥주( p3)의 판매량은? ( Continuous range의 의미는 보통 discrete한 member 값을 가지는 dimension이 아닌 Time과 같은 dimension에서만 가능하다 ) Functions int range_query ( int tsmall, int tlarge, int store, int product ) Logic Parameter를 통해 받은 Product ( key value ), Store ( key value )에 해당하는 data 시작점을 찾는다 ( 1, 2 ) tkey = Tsmall인 tuple을 찾는다. (3) tkey >= Tsmall and tkey <= Tlarge 인동안 sales값 출력 (4) P3S4 의 시작점을 가리키는 index가 존재한다면 쓸데없는 tuple scan을 줄일 수 있다. t1 t2 t3 …. 1 2 3 4

Operations Slice 연산 Functions Logic Fast_dim, Slow_dim 설정 Key = Pkey void slice ( char key, int key_value ) Logic Fast_dim, Slow_dim 설정 Key = Pkey Key = Skey Key = Tkey Fast Dim Slow Dim

Operations Key = Pkey Key = Skey Key = Tkey

Operations Drill-Down Row : 지역, Col : 상품으로 화면에 출력되고 있는 상태에서, 이를 상점별 상품 판매량으로 한 단계 낮추어서 출력하시오 Functions void drill-down( char mode, int key_value, char key, int pole ) Logic mode에 따라 1. ALL -> 모든 region 이 모든 store level로, 이 경우 pole을 기준으로 한 slice와 동일 2. Key 에 따라 ( ‘store’, ‘region’ ) Store : hierarchy table에서 key_value에 해당하는 하위 level key 을 sub_key[]배열에 저장, 이 배열을 통해 fact table data 추출 Region : hierarchy table에서 key_value에 대항하는 하위 level key 들을 sub_key[]배열에 저장, Anchor 배열을 통해 summary table에서 data 추출

Operations ALL Store ( Region ) Fact table에서 Skey = s1, s2인 tuple검색 P1 P2 P3 P4 P5 R1 R2 R3 R4 S1 S2 S3 S4 S5 S6 Key_value에 관계 없이 Tkey ( pole ) 에 따른 Slice와 동일 Rkey = R1, R2 인 Groupby를 Anchor 테이블을 통해 검색 SUM15.dat SUM1.dat Binary Files P1 P2 P3 P4 P5 R1 R2 R3 R4 S1 S2 R2 R3 R4 Store Region Country 1 2 3 4 5 6 Fact table에서 Skey = s1, s2인 tuple검색

Operations Dice Roll-up, Pivot slice방식과 비슷하되 key가 여러 개이므로 key값들을 저장한 배열이 파라미터로 전달. 배열의 값들과 비교하면서 sales data 출력 PST order로 정렬된 데이터를 이용하므로 Product dimension을 page로 놓는다면 Fact table을 한번 scan함으로써 질의 응답 가능 Roll-up, Pivot 화면에 display 된 데이터들의 Summation 화면에 display 된 데이터들의 위치 바꿈

Conclusions & Further research ROLAP의 경우 사전연산과 실시간 연산에 대단히 많은 정렬이 필요하다. RDB에서 제공되는 Index는 OLAP연산에 있어서 꼭 필요한 것은 아니다. Index가 없는 경우 더 나은 성능을 보이는 경우도 있다. Pointer나 Summary index등을 통해 Access할 데이터 셀을 빨리 찾아낸다 할지라도 데이터가 Disk에 멀리 떨어져 있다면 Disk I/O 를 줄이기는 힘들다 => ROLAP 에 MOLAP 형식의 Chunking ( Chunk - ID 추가 ) 필요 Group-by name 을 통해 Summary index의 배열 위치를 계산해 내는 Scheme 필요