Implementation of Set Query with UniSQL 이학찬, 류문수 숭실대학교 컴퓨터학과

2Set Query Introduction (1) Set Query Set Query 마케팅 정보 시스템, 의사결정 지원 시스템, 경영 보고, 직 접 마케팅과 같은 전략적 가치 정보 어플리케이션에서 원 하는 결과를 $/QPS (Price per Queries Per Second) 로 얻 을 수 있게 하여 제품에 대한 성능 평가를 할 목적으로 개 발되었다. 마케팅 정보 시스템, 의사결정 지원 시스템, 경영 보고, 직 접 마케팅과 같은 전략적 가치 정보 어플리케이션에서 원 하는 결과를 $/QPS (Price per Queries Per Second) 로 얻 을 수 있게 하여 제품에 대한 성능 평가를 할 목적으로 개 발되었다. 단일 사용자용 성능 평가이며 시험 대상 시스템은 관계형 데이터베이스이다. 단일 사용자용 성능 평가이며 시험 대상 시스템은 관계형 데이터베이스이다. 시험에 사용되는 테이블은 “BENCH” 하나 이고, 이 테이 블에는 13 개의 숫자형 칼럼 (4 byte) 과 8 개의 문자형 칼럼 으로 이루어져 있다. 시험에 사용되는 테이블은 “BENCH” 하나 이고, 이 테이 블에는 13 개의 숫자형 칼럼 (4 byte) 과 8 개의 문자형 칼럼 으로 이루어져 있다.

3Set Query Introduction (2) Performance Metrics Performance Metrics 각 질의에 대해서 elapsed 시간, CPU 시간, I/O 사용에 대 해서 측정한다. 각 질의에 대해서 elapsed 시간, CPU 시간, I/O 사용에 대 해서 측정한다. $/QPS (Dollar Price per Query Per Second) $/QPS (Dollar Price per Query Per Second) P*T / 69 P*T / 69 P: 하드웨어와 소프트웨어 비용 P: 하드웨어와 소프트웨어 비용 T: 전체 질의를 수행하는데 소요된 시간 T: 전체 질의를 수행하는데 소요된 시간 Output Formatting Output Formatting 각 질의의 결과는 사용자가 원하는 파일로 출력 가능한 형태로 출력한다. 각 질의의 결과는 사용자가 원하는 파일로 출력 가능한 형태로 출력한다. Index Index KSEQ, K500K, …, K2 칼럼에 대해서는 모두 인덱스를 생성하도록 한다. KSEQ, K500K, …, K2 칼럼에 대해서는 모두 인덱스를 생성하도록 한다.

4Set Query Bench Table ColumnColumn KSEQ not null sequence[1,N]K4 random[1,4] K500K random[1,N/2]K2 random[1,2] K250K random[1,N/4]S1 “ ” K100K not null random[1,100000]S2 “ ” K40K not null random[1,40000]S3 “ ” K10K not null random[1,10000]S4 “ ” K1K not null random[1,1000]S5 “ ” K100 not null random[1,100]S6 “ ” K25 not null random[1,25]S7 “ ” K10 not null random[1,10]S8 “ ” K5 not null random[1,5] N: 1 백만 행 (defaults size) 에 정수 배 N: 1 백만 행 (defaults size) 에 정수 배 각 튜플의 크기 : 200 bytes 각 튜플의 크기 : 200 bytes

5Set Query Queries (1) Q1: Count, Single Exact Match Q1: Count, Single Exact Match SELECT COUNT(*) FROM BENCH SELECT COUNT(*) FROM BENCH WHERE KN = 2; KN ε {KSEQ, K100K, …, K4, K2} KN ε {KSEQ, K100K, …, K4, K2} 질의 수 : 10 질의 수 : 10 Q2: Count AND ing Two Clauses Q2: Count AND ing Two Clauses Q2A: AND of two exact match conditions Q2A: AND of two exact match conditions SELECT COUNT(*) FROM BENCH SELECT COUNT(*) FROM BENCH WHERE K2 = 2 AND KN = 3; KN ε {KSEQ, K100K, …, K4} KN ε {KSEQ, K100K, …, K4} 질의 수 : 9 질의 수 : 9

6Set Query Queries (2) Q2B: NOT of an exact match conditions Q2B: NOT of an exact match conditions SELECT COUNT(*) FROM BENCH SELECT COUNT(*) FROM BENCH WHERE K2 = 2 AND NOT KN = 3; KN ε {KSEQ, K100K, …, K4} KN ε {KSEQ, K100K, …, K4} 질의 수 : 9 질의 수 : 9 Q3: Sum, Range and Match Clause Q3: Sum, Range and Match Clause Q3A: the values of an integer binary column Q3A: the values of an integer binary column SELECT SUM(K1K) FROM BENCH SELECT SUM(K1K) FROM BENCH WHERE KSEQ BETWEEN AND AND KN = 3; KN ε {K100K, …, K4} KN ε {K100K, …, K4} 질의 수 : 7 질의 수 : 7

7Set Query Queries (3) Q3B: OR Q3B: OR SELECT SUM(K1K) FROM BENCH SELECT SUM(K1K) FROM BENCH WHERE (KSEQ BETWEEN AND OR KSEQ BETWEEN AND OR KSEQ BETWEEN AND OR KSEQ BETWEEN AND OR KSEQ BETWEEN AND ) AND KN = 3; KN ε {K100K, …, K4} KN ε {K100K, …, K4} 질의 수 : 7 질의 수 : 7

8Set Query Queries (4) Q4: Multiple Condition Selection Q4: Multiple Condition Selection Q4A: ANDing 3 Q4A: ANDing 3 SELECT KSEQ, K500K FROM BENCH SELECT KSEQ, K500K FROM BENCH WHERE constraint with (3 or 5) conditions; Condition Sequence Condition Sequence (1) K2 =1(2) k100 > 80 (3) K10K BETWEEN 2000 AND 3000(4) K5 = 3 (5) K25 IN (11, 19)(6) K4 = 3 (7) K100 < 41 (8) K1K BETWEEN 850 AND 950 (9) K10 = 7(10) K25 IN (3, 4) 질의 수 : 8 질의 수 : 8

9Set Query Queries (5) Q4B: ANDing 5 Q4B: ANDing 5 SELECT KSEQ, K500K FROM BENCH SELECT KSEQ, K500K FROM BENCH WHERE constraint with (3 or 5) conditions; Condition Sequence Condition Sequence (1) K2 =1(2) k100 > 80 (3) K10K BETWEEN 2000 AND 3000(4) K5 = 3 (5) K25 IN (11, 19)(6) K4 = 3 (7) K100 < 41 (8) K1K BETWEEN 850 AND 950 (9) K10 = 7(10) K25 IN (3, 4) 질의 수 : 7 질의 수 : 7

10Set Query Queries (6) Q5: Multiple Column GROUP BY Q5: Multiple Column GROUP BY SELECT KN1, KN2, COUNT(*) FROM BENCH SELECT KN1, KN2, COUNT(*) FROM BENCH GROUP BY KN1, KN2; (KN1, KN2) ε { (K2, K100), (K10, K25), (K10, K25) } (KN1, KN2) ε { (K2, K100), (K10, K25), (K10, K25) } 질의 수 : 3 질의 수 : 3 Q6: Multiple Condition Selection Q6: Multiple Condition Selection Q6A: equality condition limiting the rows of the first table only Q6A: equality condition limiting the rows of the first table only SELECT COUNT(*) FROM BENCH B1, BENCH B2 SELECT COUNT(*) FROM BENCH B1, BENCH B2 WHERE B1.KN = 49 AND B1.K250K = B2.K500K; KN1 ε { K100K, K40K, K10K, K1K, K100 } KN1 ε { K100K, K40K, K10K, K1K, K100 } 질의 수 : 5 질의 수 : 5

11Set Query Queries (7) Q6B: equality conditions limit the rows on both tables Q6B: equality conditions limit the rows on both tables SELECT B1.KSEQ, B2.KSEQ FROM BENCH B1, BENCH B2 SELECT B1.KSEQ, B2.KSEQ FROM BENCH B1, BENCH B2 WHERE B1.KN = 99 AND B1.K250K = B2.K500K AND B2.K25 = 19; KN1 ε { K40K, K10K, K1K, K100 } KN1 ε { K40K, K10K, K1K, K100 } 질의 수 : 4 질의 수 : 4

12Set Query Data Generation pseudo-random number generator PROCEDURE FIELDVGEN()/* Procedure to generate indexed field values */ INTEGER I, J; /* Looping Variables */ DOUBLE SEED INIT (1.); /* Seed For Random Number Generation */ INTEGER ARRAY COLVAL(1:12), /* Array to hold one row of values */ COLCARD(1:12) /* Array holding largest value in each field */ INIT (500000,250000,100000,40000,10000,1000,100,25,10,5,4,2);/* Initialize */ FOR I FROM 1 TO ; /* One Million Rows */ FOR J FROM 1 TO 12; /* Twelve randomly generated column values */ SEED = MOD( D * SEED, D); /* I.E.: Si+1 = (7**5 * Si ) MOD (2**31-1), where Si is SEED, a random # */ COLVAL(J) = MOD(SEED, COLCARD(J) )+1; /* Generate next column value */ END FOR J /* Row complete */ PRINT COLVAL VALUES FOR THIS ROW TO OUTPUT;/*Output row's values*/ END FOR I /* We have generated One Million Rows */ END

13Set Query System environment Hardware Hardware CPU: Pentium III 733MHz CPU: Pentium III 733MHz RAM: 512MB RAM: 512MB HDD: 18GB HDD: 18GB Software Software 운영체제 : Red Hat linux 7.2 (kernel 2.4.7) 운영체제 : Red Hat linux 7.2 (kernel 2.4.7) 컴파일러 : GCC 2.96 컴파일러 : GCC 2.96 UniSQL: UniSQL5.1 Patch1 UniSQL: UniSQL5.1 Patch1

14Set Query UniSQL Parameter page_size = 4,096 bytes page_size = 4,096 bytes num_data_buffers = pages num_data_buffers = pages num_log_buffers = pages num_log_buffers = pages checkpoint_interval_minutes = 180 minutes checkpoint_interval_minutes = 180 minutes

15Set Query Query Optimization UniSQL 은 비용 기반 최적화 방법 (cost based query optimization) 을 제공함. UniSQL 은 비용 기반 최적화 방법 (cost based query optimization) 을 제공함. 인덱스 생성 후 최적화 수행 인덱스 생성 후 최적화 수행 “UPDATE STATISTICS ON ALL CLASSES” “UPDATE STATISTICS ON ALL CLASSES”

16Set Query Statistics gathered Elapsed time Elapsed time 시스템이 질의 처리를 위해서 사용한 모든 경과 시간 시스템이 질의 처리를 위해서 사용한 모든 경과 시간 CPU time CPU time 시스템이 질의 처리를 위해서 사용한 CPU 사용 시간 시스템이 질의 처리를 위해서 사용한 CPU 사용 시간 I/O I/O 시스템이 질의 처리를 위해서 사용한 물리적인 블록 수 시스템이 질의 처리를 위해서 사용한 물리적인 블록 수 Unix/Linux 운영체제의 “iostat” 명령어의 결과 값을 이용 Unix/Linux 운영체제의 “iostat” 명령어의 결과 값을 이용

17Set Query Result (1) ElapsedCPUBlock InBlock Out Q1 Q1 Avg , 회1회 , 회2회 , 회3회 , Q2 Avg , 회1회 , 회2회 , 회3회 , Q3 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,928240

18Set Query Result (2) ElapsedCPUBlock InBlock Out Q1 Q5 Avg , 회1회 , 회2회 , 회3회 , Q6 Avg , 회1회 , 회2회 , 회3회 , Q7 Avg , 회1회 , 회2회 , 회3회 , Q8 Avg , 회1회 , 회2회 , 회3회 ,080192

19Set Query Result (3) ElapsedCPUBlock InBlock Out Q1 Q9 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q2A Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,232344

20Set Query Result (4) ElapsedCPUBlock InBlock Out Q2A Q13 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,176192

21Set Query Result (5) ElapsedCPUBlock InBlock Out Q2A Q17 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q2BQ , 회1회 , 회2회 , 회3회 ,032192

22Set Query Result (6) ElapsedCPUBlock InBlock Out Q2B Q21 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,336192

23Set Query Result (7) ElapsedCPUBlock InBlock Out Q2B Q25 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,248192

24Set Query Result (8) ElapsedCPUBlock InBlock Out Q3A Q29 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,112240

25Set Query Result (9) ElapsedCPUBlock InBlock Out Q3A Q33 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q3BQ , 회1회 , 회2회 , 회3회 ,216344

26Set Query Result (10) ElapsedCPUBlock InBlock Out Q3B Q37 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,392192

27Set Query Result (11) ElapsedCPUBlock InBlock Out Q3B Q41 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q4A Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,056424

28Set Query Result (12) ElapsedCPUBlock InBlock Out Q4A Q45 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,936688

29Set Query Result (13) ElapsedCPUBlock InBlock Out Q4A Q49 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q4B Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,112192

30Set Query Result (14) ElapsedCPUBlock InBlock Out Q4B Q53 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,440192

31Set Query Result (15) ElapsedCPUBlock InBlock Out Q4BQ57 Avg , 회1회 , 회2회 , 회3회 , Q5 Q ,309405,354 1회1회 ,896405,256 2회2회 ,960405,240 3회3회 ,072405,568 Q ,245405,317 1회1회 ,672405,296 2회2회 ,320405,224 3회3회 ,744405,432 Q ,570405,240 1회1회 ,672405,240 2회2회 ,896405,264 3회3회 ,144405,216

32Set Query Result (16) ElapsedCPUBlock InBlock Out Q6A Q61 Avg , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,472416

33Set Query Result (17) ElapsedCPUBlock InBlock Out Q6AQ65 Avg , 회1회 , 회2회 , 회3회 , Q6B Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 , Q , 회1회 , 회2회 , 회3회 ,288384

34Set Query Result (18) ElapsedCPUBlock InBlock Out Q6BQ69 Avg ,8215,450 1회1회 ,6245,344 2회2회 ,4485,384 3회3회 ,3925,624

35Set Query Comparison (1) Page Size 4K Elapsed time - 질의 수행 후 메모리에 대용량 자료 쓰기 수행 Page Size 4K Elapsed time - 질의 수행 후 메모리에 대용량 자료 쓰기 안함 Page Size 8K Elapsed time - 질의 수행 후 메모리에 대용량 자료 쓰기 수행 Block InBlock Out Q ,095, Q ,087, Q ,095, Q ,087, Q ,087, Q ,082, Q ,082, Q ,832,3842,030,160 Q , Q ,496832

36Set Query Comparison (2) Connection Time Query Processing Total Time Q Q Q Q Q Q Q Q Q Q

37Set Query Query plan (1) Query Query plan Q1 Index scan(bench, bench.kseq=2) Q2 Index scan(bench, bench.k100k=2) Q3 Index scan(bench, bench.k10k=2) Q4 Index scan(bench, bench.k1k=2) Q5 Index scan(bench, bench.k100=2) Q6 Index scan(bench, bench.k25=2) Q7 Index scan(bench, bench.k10=2) Q8 Index scan(bench, bench.k5=2) Q9 Index scan(bench, bench.k4=2) Q10 Index scan(bench, bench.k2=2) Q11 Index scan(bench, bench.kseq=3) Q12 Index scan(bench, bench.k100k=3) Q13 Index scan(bench, bench.k10k=3) Q14 Index scan(bench, bench.k2=2)

38Set Query Query plan (2) Query Query plan Q15 Index scan(bench, bench.k2=2) Q16 Q17 Index scan(bench, bench.k10=3) Q18 Index scan(bench, bench.k5=3) Q19 Index scan(bench, bench.k4=3) Q20 Index scan(bench, bench.k2=2) Q21 Q22 Q23 Q24 Q25 Q26 Q27 Q28

39Set Query Query plan (3) Query Query plan Q29 Index scan(bench, bench.k100k=3) Q30 Index scan(bench, bench.k10k=3) Q31 Index scan(bench, bench.k100=3) Q32 Index scan(bench, bench.k25=3) Q33 Index scan(bench, bench.k10=3) Q34 Index scan(bench, bench.k5=3) Q35 Index scan(bench, bench.k4=3) Q36 Index scan(bench, bench.k100k=3) Q37 Index scan(bench, bench.k10k=3) Q38 Index scan(bench, bench.k100=3) Q39 Index scan(bench, bench.k25=3) Q40 Index scan(bench, bench.k10=3) Q41 Index scan(bench, bench.k5=3) Q42 Index scan(bench, bench.k4=3)

40Set Query Query plan (4) Query Query plan Q43 Index scan(bench, bench.k2=1) Q44 Index scan(bench, bench.k5=3) Q45 Q46 Q47 Index scan(bench, bench.k4=3) Q48 Q49 Index scan(bench, bench.k10=7) Q50 Q51 Index scan(bench, bench.k5=3) Q52 Q53 Q54 Q55 Index scan(bench, bench.k10=7) Q56

41Set Query Query plan (5) Query Query plan Q57 Index scan(bench, bench.k10=7) Q58 Sequential scan(bench) Q59 Q60 Q61 Nested loops Index scan(b1, b1.k100k=49) Index scan(b1, b1.k100k=49) Index scan(b2, b1.k250k=b2.k500k) Index scan(b2, b1.k250k=b2.k500k) Q62 Nested loops Index scan(b1, b1.k40k=49) Index scan(b1, b1.k40k=49) Index scan(b2, b1.k250k=b2.k500k) Index scan(b2, b1.k250k=b2.k500k) Q63 Nested loops Index scan(b1, b1.k10k=49) Index scan(b1, b1.k10k=49) Index scan(b2, b1.k250k=b2.k500k) Index scan(b2, b1.k250k=b2.k500k)

42Set Query Query plan (6) Query Query plan Q64 Nested loops Index scan(b1, b1.k1k=49) Index scan(b1, b1.k1k=49) Index scan(b2, b1.k250k=b2.k500k) Index scan(b2, b1.k250k=b2.k500k) Q65 Nested loops Index scan(b1, b1.k100=49) Index scan(b1, b1.k100=49) Index scan(b2, b1.k250k=b2.k500k) Index scan(b2, b1.k250k=b2.k500k) Q66 Nested loops Index scan(b1, b1.k40k=99) Index scan(b1, b1.k40k=99) Index scan(b2, b1.k250k=b2.k500k) Index scan(b2, b1.k250k=b2.k500k) Q67 Nested loops Index scan(b1, b1.k10k=99) Index scan(b1, b1.k10k=99) Index scan(b2, b1.k250k=b2.k500k) Index scan(b2, b1.k250k=b2.k500k)

43Set Query Query plan (7) Query Query plan Q68 Nested loops Index scan(b1, b1.k1k=99) Index scan(b1, b1.k1k=99) Index scan(b2, b1.k250k=b2.k500k) Index scan(b2, b1.k250k=b2.k500k) Q69 Merge join(b1.k250k=b2.k500k) Index scan(b1, b1.k100=99) Index scan(b1, b1.k100=99) Index scan(b2, b2.k25=19) Index scan(b2, b2.k25=19)

44Set Query Conclusion & Analysis (1) 데이터 생성기에 대한 검증 데이터 생성기에 대한 검증 “Set Query” 논문에서 제시하는 알고리즘으로 구현하여 논문에서 제시하는 칼럼 값과 일치함으로써 검증 “Set Query” 논문에서 제시하는 알고리즘으로 구현하여 논문에서 제시하는 칼럼 값과 일치함으로써 검증 결과에 대한 검증 결과에 대한 검증 “Set Query” 논문의 Appendix A 에 나오는 결과값과 구현 결과값을 비교하여 검증 “Set Query” 논문의 Appendix A 에 나오는 결과값과 구현 결과값을 비교하여 검증 모든 결과값 동일하며 각 질의들은 정확히 수행 모든 결과값 동일하며 각 질의들은 정확히 수행 시스템 통계에 대한 고려 시스템 통계에 대한 고려 “Set Query” 논문에서는 통계 수집을 시험 대상 시스템에 서 제공하는 툴을 사용해서 통계 수집 “Set Query” 논문에서는 통계 수집을 시험 대상 시스템에 서 제공하는 툴을 사용해서 통계 수집 “UniSQL” 에는 제공하지 않으므로 운영체제 관점에서 통 계 수집을 수행 “UniSQL” 에는 제공하지 않으므로 운영체제 관점에서 통 계 수집을 수행

45Set Query Conclusion & Analysis (2) $/QPS $/QPS H/W 와 S/W 에 대한 비용이 없음으로 제시하지 않음 H/W 와 S/W 에 대한 비용이 없음으로 제시하지 않음 각 질의 수행 결과의 출력 각 질의 수행 결과의 출력 사용자에게 결과 파일 (outputFile.txt) 로 제공함 사용자에게 결과 파일 (outputFile.txt) 로 제공함 outputFile.txt outputFile.txt Query --- select count(*) from bench where kseq = 2 1………… Query --- select count(*) from bench where k4 = …………

46Set Query Conclusion & Analysis (3) 페이지 크기에 대한 고려 페이지 크기에 대한 고려 페이지 크기의 변화에 따라서 수행 시간이 변함 페이지 크기의 변화에 따라서 수행 시간이 변함 페이지 크기가 8K 인 경우의 I/O 발생이 4K 보다 많음 페이지 크기가 8K 인 경우의 I/O 발생이 4K 보다 많음 4K 크기가 8K 크기 보다 좋은 이유는 OS 의 파일 시스템 의 기본 페이지 크기가 4K 로 같은 크기 값으로써 좋은 것 으로 생각됨 4K 크기가 8K 크기 보다 좋은 이유는 OS 의 파일 시스템 의 기본 페이지 크기가 4K 로 같은 크기 값으로써 좋은 것 으로 생각됨 Connection Time 대한 고려 Connection Time 대한 고려 평균 4 초 정도는 데이터베이스의 연결을 하고 있음 평균 4 초 정도는 데이터베이스의 연결을 하고 있음 간단한 질의는 질의 처리 시간에 비해 많은 시간을 연결 에 사용하고 있음 간단한 질의는 질의 처리 시간에 비해 많은 시간을 연결 에 사용하고 있음