데이타 스트림에 대한 다중 연속 질의들 사이에는 질의들의 윈도우 중첩 및 주기적 실행 간격으로 인해 재사용이 가능한 중간 결과들이 다수 생길 수 있다. 본 논문은 다중 연속 질의들을 위한 전체 실행 계획을 구성하기 위해, 효율적인 탐욕 기반의 경험적 알고리즘인 GAGPC를 제안한다. 제안한 GAGPC 알고리즘은 질의들의 전체 실행 사이클을 결정하고 관련된 실행 시점들의 최대 집합인 SRP를 찾는다. 다음, 각 SRP에서 실행될 질의들이 가장 높은 이익을 갖는 공통의 조인 부분들을 공유하도록 전체 실행 계획을 구성한다. 본 논문은 공통된 질의 부분의 존재뿐만 아니라 그것과 관련된 중첩된 윈도우 크기에 따라 통일한 연속 질의라 하더라도 최상의 질의 계획아 바뀔 수 있다는 점을 제시한다. 또한 기존 연구와는 달리, 윈도우가 부분 또는 전체적으로 중첩될 수 있으므로 중간 결과의 전체뿐만 아니라 일부도 재 사용할 것을 반영한다. 마지막으로, 본 논문은 GAGPC의 유효성을 위한 시뮬레이션 결과를 제시한다.
데이타 스트림에 대한 다중 연속 질의들 사이에는 질의들의 윈도우 중첩 및 주기적 실행 간격으로 인해 재사용이 가능한 중간 결과들이 다수 생길 수 있다. 본 논문은 다중 연속 질의들을 위한 전체 실행 계획을 구성하기 위해, 효율적인 탐욕 기반의 경험적 알고리즘인 GAGPC를 제안한다. 제안한 GAGPC 알고리즘은 질의들의 전체 실행 사이클을 결정하고 관련된 실행 시점들의 최대 집합인 SRP를 찾는다. 다음, 각 SRP에서 실행될 질의들이 가장 높은 이익을 갖는 공통의 조인 부분들을 공유하도록 전체 실행 계획을 구성한다. 본 논문은 공통된 질의 부분의 존재뿐만 아니라 그것과 관련된 중첩된 윈도우 크기에 따라 통일한 연속 질의라 하더라도 최상의 질의 계획아 바뀔 수 있다는 점을 제시한다. 또한 기존 연구와는 달리, 윈도우가 부분 또는 전체적으로 중첩될 수 있으므로 중간 결과의 전체뿐만 아니라 일부도 재 사용할 것을 반영한다. 마지막으로, 본 논문은 GAGPC의 유효성을 위한 시뮬레이션 결과를 제시한다.
In general, there can be many reusable intermediate results due to the overlapped windows and periodic execution intervals among Multiple Continuous Queries (MCQ) on data streams. In this regard, we propose an efficient greedy algorithm for a global query plan construction, called GAGPC. GAGPC first...
In general, there can be many reusable intermediate results due to the overlapped windows and periodic execution intervals among Multiple Continuous Queries (MCQ) on data streams. In this regard, we propose an efficient greedy algorithm for a global query plan construction, called GAGPC. GAGPC first decides an execution cycle and finds the maximal Set(s) of Related execution Points (SRP). Next, GAGPC constructs a global execution plan to make MCQ share common join-fragments with the highest benefit in each SRP. The algorithm suggests that the best plan of the same continuous queries may be different according to not only the existence of common expressions, but the size of overlapped windows related to them. It also reflects to reuse not only the whole but partial intermediate results unlike previous work. Finally, we show experimental results for the validation of GAGPC.
In general, there can be many reusable intermediate results due to the overlapped windows and periodic execution intervals among Multiple Continuous Queries (MCQ) on data streams. In this regard, we propose an efficient greedy algorithm for a global query plan construction, called GAGPC. GAGPC first decides an execution cycle and finds the maximal Set(s) of Related execution Points (SRP). Next, GAGPC constructs a global execution plan to make MCQ share common join-fragments with the highest benefit in each SRP. The algorithm suggests that the best plan of the same continuous queries may be different according to not only the existence of common expressions, but the size of overlapped windows related to them. It also reflects to reuse not only the whole but partial intermediate results unlike previous work. Finally, we show experimental results for the validation of GAGPC.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
한편, 기존 연구에서 다뤄왔던 다중 질의의 최적화 문제의 복잡도가 NP-Hard임이 증명되었는데 [9], 본 논문에서는 매 실행 시점마다 다중 질의를 최적화하는 문제로 고려될 수 있으므로 기존 문제보다 더 높은 복잡도를 가진다. 그러므로, 탐욕 기반의 경험적 방법을 통해 문제를 해결하고자 한다.
본 논문에서는 데이타 스트림이라는 환경에서 새로이 등장한 윈도우 크기와 실행 간격을 기반으로 다중 연속 질의의 전체 실행 계획을 구성하는 알고리즘을 제안하였다. 본 논문의 알고리즘에서는 크게 두 단계의 과정으로 다중 연속 질의들을 위한 전체 계획을 구성하였다.
한편, G)에서는 4분이 겹쳐서 그림 6(b) 와 같이 3 X C 를 공유하는 계획을 실행하는 것이 더 좋을 수 있다. 본 논문의 목적은 전체의 중간 결과는 물론, 기존 연구와는 달리 일부의 중간 결과까지도 재사용하는 것을 고려하여 최적에 가까운 전체 계획을 세우는 것이다.
가설 설정
센서 네트워크 분야의 연구들은 값비싼 센서들의 전력 소모(power consumption)가 최소화되도록 하는 질의 처리 알고리즘을 중점적으로 다루고 있다. 본 논문에서는 전력이 항상 공급되는 데이타 스트림 서버에서 실행되는 알고리즘을 설계하므로, 전력이라는 요소를 고려하지 않았다. 그러나, 논문의 알고리즘이 전력과는 상관없이 윈도우와 실행 간격을 바탕으로 연 속 질의들의 실행을 최적화하기 때문에, 센서 네트워크에 적용하더라도 크게 영향을 미치지 않을 것으로 기대한다.
제안 방법
6.2.1과 6.2.2에서는 10개의 동일한 연속 질의 집합 (QSET)에 대하여, (「) 본 논문의 GAGPC로 얻는 방법, (匚) 모든 질의의 지역 질의-처리 계획만으로 구성(No Reusing Work)하여 얻는 방법, (匸) 최적 전체 계획을 얻기 위해, 시간제한을 두지 않고 철저한 탐색 (exhaustive search)을 수행하여 얻는 방법, (己) Nia- garaCQ or CACQ 등의 기존 연구의 알고리즘을 본 논문에서 다루고 있는 환경에 적용하여 질의 간에 윈도우 가 완전히 겹치는 경우에만 중간 결과의 재사용이 가능한 것으로 하여 얻는 방법 등으로 전체 계획을 구하였다. 그리고 윈도우 크기, 실행 간격, 연속 질의의 수 둥 을 매개변수로 하여 위의 각 방법으로 얻은 전체 계획의 실행 비용의 변화 추세를 그래프로 나타내었다.
[3] 에서는 'eddy'라는 질의 처리 체제를 기반으로 데이 타 스트림에서 지속적으로 환경에 적응하는 연속 질의 시스템 (Continuously Adaptive Continuous Queries: CACQ)을 제시하고 있다. 구체적으로, 시스템에 도착하는 튜플들이 적용되는 연산자들의 순서를 처리 상황에 따라 효율적으로 질의를 처리할 수 있는 유연한 튜플 라우팅 기법을 제안한다. 또한 비슷한 선택 술어 (selection predicate) 을 갖는 질의들을 그룹 필터 (grouped filter)라는 술어 색인 연산자를 이용하여 그룹 핑하여 처리하는 기법을 제안한다.
끝으로 이익이 가장 큰 중간 결과를 갖는 공유 계획을 SRP 안에서 구성함으로써 실행 사이클 내의 전체 계획을 세움으로써 본 논문의 작업을 완성한다.
그다음, C X 。에 대해, CPs), (R;) 에서 실행될 질의들은 C X D의 일부를 공유하는 조정 질의-처리 계획을 실행 계획으로 결정한다. 다음, B X C에 대해, CP”), (P”)에서 실행될 질의들은 B X C의 일부를 공유하는 조정 질의-처리 계획을 실행 계획으로 결정한다. (R) 에서 A X B의 일부가 실행 계획에 이미 포함되었으므로, (0) 에서 는 그것의 지역 질의-처리 계획이 실행 계획으로 선택된다.
먼저 다중 연속 질의의 실행 사이클을 알아내었다. 다음, 본 논문에서 제안된 재사용 비율과 이익 모델을 바탕으로 각에 있는 시점에서 실행될 연속 질의들의 전체 계획을 구성하였다. 이것은 세부적으로 단계 1~단계 3의 과정을 거쳐서 진행되었다.
구체적으로, 시스템에 도착하는 튜플들이 적용되는 연산자들의 순서를 처리 상황에 따라 효율적으로 질의를 처리할 수 있는 유연한 튜플 라우팅 기법을 제안한다. 또한 비슷한 선택 술어 (selection predicate) 을 갖는 질의들을 그룹 필터 (grouped filter)라는 술어 색인 연산자를 이용하여 그룹 핑하여 처리하는 기법을 제안한다. 그러나, (3) 은 본 논문에서 언급한 실행 간격 기반의 질의를 지원하지 않았다 본 논문이 대상으로 하는 환경에 적용하기 위해, (3)의 질의에 실행 간격 및 조인을 위한 윈도우 연산자를 추가할 필요가 있다.
SRP/게서는 가장 높은 이익을 갖는 순서대로 4X3, C X B X C가 공유될 조인 부분으로 선택되었다. 먼저 A X B에 대해, (R), (P3), (R), (Pg), (凡) 에서 실행될 질의들은 A X 3의 일부를 공유하는 조정 질의 -처리 계획을 실행 계획으로 결정한다. 그다음, C X 。에 대해, CPs), (R;) 에서 실행될 질의들은 C X D의 일부를 공유하는 조정 질의-처리 계획을 실행 계획으로 결정한다.
본 논문의 알고리즘에서는 크게 두 단계의 과정으로 다중 연속 질의들을 위한 전체 계획을 구성하였다. 먼저 다중 연속 질의의 실행 사이클을 알아내었다. 다음, 본 논문에서 제안된 재사용 비율과 이익 모델을 바탕으로 각에 있는 시점에서 실행될 연속 질의들의 전체 계획을 구성하였다.
이때, 가장 높은 이익을 갖는 조인 부분부터 포함시키는 탐욕 기반의 경험적 기법을 적용하여, 하나의 SRP 내에서 공유될 조인 부분을 선택하였다. 본 논문에 제시된 알고리즘은 매우 실용적이며, 최적 전체 계획에 거의 근접하는 전체 계획을 얻는 우수한 성능 결과를 시뮬레이션을 통해 알아보았다.
본 논문에서는 데이타 스트림 환경에서 부가적으로 고려되어야 하는 위의 세 가지 특징들을 기반으로, 다중 연속 질의들에 대한 실행 계획(execution plan)을 세우 는 탐욕 스타일의 경험적 기법(greedy-style heuristic approach)을 제안한다. 본 논문에서 제안하는 기법은 윈도우 크기와 실행 간격을 사용하여 정의되는 재사용 비율(reusable ratio)과 이익(benefit) 모델을 기반으로 한다. 기존 연구와는 달리, 제안하는 방법은 달리 다른 질의가 생성한 중간 결과의 일부를 재사용하는 공유 계획까지 고려함으로써 전체적으로 더 효율적인 실행 계획을 세울 수 있게 된다.
본 논문에서는 데이타 스트림 환경에서 부가적으로 고려되어야 하는 위의 세 가지 특징들을 기반으로, 다중 연속 질의들에 대한 실행 계획(execution plan)을 세우 는 탐욕 스타일의 경험적 기법(greedy-style heuristic approach)을 제안한다. 본 논문에서 제안하는 기법은 윈도우 크기와 실행 간격을 사용하여 정의되는 재사용 비율(reusable ratio)과 이익(benefit) 모델을 기반으로 한다.
본 논문에서는 모든 연속 질의들의 실행 간격의 최소 공배수로 실행 사이클을 설정한다. 즉 세 개의 연속 질의의 실행 간격이 각각 10분, 20분, 30분이라면 이 질의를 시스템이 처리하는 최초의 실행 시점인 '60분'이 시스템의 실행 사이클이 될 것이다.
여기서, 관련 있는 시점'이라 는 의미는 그 시점에서 실행될 질의들은 윈도우가 겹쳐 있고 공통의 부분 조인 표현을 가지고 있어서, 서로 간에 공유 계획을 세울 것을 고려할 필요가 있다는 것이다. 본 논문에서는 한 실행 사이클 내에 있는 모든 시점 들을 '관련 있는 시점' 들만의 집합으로 묶고, 집합 내의 시점에서 실행될 질의들에 대해서만 전체 계획을 고려한 다음, 각 집합 내에서 얻어진 계획을 병합함으로써 실행 사이클 내의 전체 계획을 얻는다.
본 논문에서는 데이타 스트림이라는 환경에서 새로이 등장한 윈도우 크기와 실행 간격을 기반으로 다중 연속 질의의 전체 실행 계획을 구성하는 알고리즘을 제안하였다. 본 논문의 알고리즘에서는 크게 두 단계의 과정으로 다중 연속 질의들을 위한 전체 계획을 구성하였다. 먼저 다중 연속 질의의 실행 사이클을 알아내었다.
표 4는 실험에 사용된 질의들에 대한 상세한 설명이다. 윈도우 크기, 실행 간격, 조인 조건을 동일하게 설정하고 질의 수를 증가 시켜 시뮬레이션하는 것은 무의미하므로, 질의가 추가될 때마다 이들을 임의로 설정하여 질의 수 변화에 따른 각 전체 계획의 생성 시간을 측정하였다.
이것은 세부적으로 단계 1~단계 3의 과정을 거쳐서 진행되었다. 이때, 가장 높은 이익을 갖는 조인 부분부터 포함시키는 탐욕 기반의 경험적 기법을 적용하여, 하나의 SRP 내에서 공유될 조인 부분을 선택하였다. 본 논문에 제시된 알고리즘은 매우 실용적이며, 최적 전체 계획에 거의 근접하는 전체 계획을 얻는 우수한 성능 결과를 시뮬레이션을 통해 알아보았다.
표 3은 실험에 사용된 각 질의 집합에 대한 상세한 설명이다. 집합 내 질의들의 실행 간격은 집합에 설정된 윈도우 크기보다 큰 난수(random value)로 질의마다 다르게 설계하였다.
표 2는 실험에 사용된 각 질의 집합에 대한 상세한 설명이다. 집합 내 질의들의 윈도우 크기는 집합에 설정된 실행 간격 이하의 난수(random value)로 질의마다 다르게 설계하였다.
이론/모형
본 논문의 알고리즘인 GAGPC를 제시한다. 그것은 크게 5.
성능/효과
본 논문에서 제안하는 기법은 윈도우 크기와 실행 간격을 사용하여 정의되는 재사용 비율(reusable ratio)과 이익(benefit) 모델을 기반으로 한다. 기존 연구와는 달리, 제안하는 방법은 달리 다른 질의가 생성한 중간 결과의 일부를 재사용하는 공유 계획까지 고려함으로써 전체적으로 더 효율적인 실행 계획을 세울 수 있게 된다.
첫째, 다중 연속 질의들은 서로 다른 크기의 윈도우 내에 들어온 데이타에 대한 조인을 요구하면서 서로 다른 간격으로 실행되므로, 공통된 질의 부분에 대한 중간 결과 전체에 대해서 보다는 부분적으로 공유가 가능한 경우가 많이 발생하게 된다. 둘째, 연속 질의 간에 공유 가능한 중간 결과의 크기에 따라 중간 결과를 재사용하도록 하는 공유 계획이 효과적일 수도 있고 그렇지 않을 수도 있다. 기존 연구의 알고리즘은 질의 간에 공통이 되는 전체의 중간 결과만을 공유할 것을 고려하므로, 부분적으로 공유 가능한 중간 결과도 고려할 수 있도록 수정되어야 한다.
후속연구
SRP 에 있는 각 시점에서 실행될 연속 질의에 대해 설정된 재사용 비율은 지역 질의-처리 계획에 비해 조정 질의-처리 계획을 선택했을 때의 이익(benefit)을 계산하기 위해 활용될 것이다. 여기서 이익이란 지역 질의 -처리 계획에 비해 재사용이 가능한 중간 결과를 공유하는 조정 질의-처리 계획을 선택했을 때 절약할 수 있는 실행 비용이다.
본 논문에서는 전력이 항상 공급되는 데이타 스트림 서버에서 실행되는 알고리즘을 설계하므로, 전력이라는 요소를 고려하지 않았다. 그러나, 논문의 알고리즘이 전력과는 상관없이 윈도우와 실행 간격을 바탕으로 연 속 질의들의 실행을 최적화하기 때문에, 센서 네트워크에 적용하더라도 크게 영향을 미치지 않을 것으로 기대한다.
마지막으로, 위에서 언급한 고려 사항들을 어느 시점까지 적용하느냐 하는 것에 대한 분석이 필요하다. 그림 4에서 보는 바와 같이 n 개의 질의가 동시에 실행되는 특정 시점 (P花) = R;⑸ = .
그러나 [5]는 XML 문서 스트림에 제한된 다중 연속 질의 최적화 문제를 다루고 있으며, [5] 에서 논의되고 있는 질의는 두 개의 스트림을 조인하기 위한 윈도우 연산자를 지원하지 않는다. 본 논문이 대상으로 하는 환경에 적용하기 위해, 질의가 대상으로 하는 스트림을 XML 문서가 아닌 일반 데이타 스트림으로 확장하고, 스트림에 대한 조인을 지원하기 위해 윈도우 연산자를 추가할 필요가 있다.
향후, 본 논문의 알고리즘은 조인 부분이 삼차(three- way) 이상일 때와 스트림 데이타의 변화율이 빈번하게 바뀌는 것 등을 고려하여 다양한 관점에서 분석될 필요가 있다.
참고문헌 (11)
Lukasz Golab M. Tamer Ozsu, Issues in data stream management, ACM SIGMOD Record, Volume 32, Issue 2, June 2003
※ AI-Helper는 부적절한 답변을 할 수 있습니다.