컴퓨팅 장치에 의해 수행되는 쿼리 처리 방법에 있어서,데이터베이스의 입력 쿼리를 획득하는 단계;상기 데이터베이스의 테이블에 대응되는 정점 및 테이블간 조인 정보에 대응되는 간선으로 구성된 조인 그래프(join graph)를 생성하는 단계;상기 조인 그래프를 복수의 서브 그래프로 분할하는 단계;상기 입력 쿼리를 기초로 상기 복수의 서브 그래프를 이용하여 다항 조인 연산자를 포함하는 타겟 쿼리의 실행 계획을 생성하는 단계;비용 모델을 기초로 상기 타겟 쿼리의 실행 계획을 최적화하는 단계;GPU 또는 CPU 메모리의 가용 크기를 기초로, 상기 타겟 쿼리에 포함된 다항 조인 연산자의 테이블 정렬 알고리즘을 획득하는 단계;상기 획득된 정렬 알고리즘에 따라 정렬된 다항 조인 연산자의 테이블에 포함된 하나 이상의 조인 컬럼의 정렬 순서를 결정하는 단계; 및상기 하나 이상의 조인 컬럼의 정렬 순서를 기초로, 상기 복수의 서브 그래프에 대한 연산을 수행하는 단계를 포함하는,쿼리 실행 방법.

제 1항에 있어서,상기 조인 그래프를 생성하는 단계는상기 입력 쿼리에 포함된 조인 술어 정보(join predicate)를 이용하여 상기 조인 그래프를 생성하는 단계를 포함하고,상기 조인 그래프는,상기 정점에 대한 테이블 타입 정보를 포함하고, 상기 간선에 대한 술어 정보 및 조인 타입 정보를 더 포함하는,쿼리 실행 방법.

제 1항에 있어서,상기 복수의 서브 그래프는,참조키-참조키 조인 타입과 대응되는 간선으로만 구성된 제1 서브 그래프 및 고유키-참조키 조인 타입과 대응되는 간선을 포함하는 제2 서브 그래프를 포함하는쿼리 실행 방법.

제 3항에 있어서,상기 제2 서브 그래프는,고유키-참조키 조인 타입과 대응되는 복수의 간선으로 구성되고, 상기 복수의 간선과 연결된 공통 정점은 사실 테이블(fact table) 타입의 테이블과 대응되는,쿼리 실행 방법.

제 4항에 있어서,상기 타겟 쿼리의 실행 계획을 생성하는 단계는,상기 제2 서브 그래프의 개수를 기초로 다항 조인 연산자를 포함하는 타겟 쿼리의 실행 계획을 생성하는 단계를 포함하는,쿼리 실행 방법.

제 3항에 있어서,상기 타겟 쿼리의 실행 계획을 생성하는 단계는상기 복수의 서브 그래프 중 상기 제1 서브 그래프가 하나인 경우, 복수의 제2 서브 그래프 각각을 이용하여 서브 쿼리를 생성하는 단계; 및상기 서브 쿼리가 제1 서브 그래프에 대응되는 다항 조인 연산자의 자식(child)으로 구성된 타겟 쿼리의 실행 계획을 생성하는 단계를 포함하는, 쿼리 실행 방법.

제 6항에 있어서,상기 서브 쿼리는,상기 복수의 서브 그래프 중 상기 제1 서브 그래프가 복수인 경우 상기 제1 서브 그래프에 포함된 고유키-참조키 조인 타입에 대응되는 간선들의 집합을 기초로 생성된,쿼리 실행 방법.

제 7항에 있어서,상기 타겟 쿼리의 실행 계획을 생성하는 단계는,복수의 제1 서브 그래프에 대하여, i 번째 제1 서브 그래프내의 정점을 포함하는 j 번째 제1 서브 그래프에 대한 서브쿼리가 존재하는 경우, i 번째 제1 서브 그래프와 그 자식들에 대해 생성된 서브쿼리가 j 번째 제1 서브 그래프에 대한 서브쿼리의 자식으로 구성된 타겟 쿼리의 실행 계획을 생성하는 단계를 포함하는,쿼리 실행 방법.

제 6항에 있어서,상기 타겟 쿼리의 실행 계획을 생성하는 단계는,상기 입력 쿼리 중 상기 복수의 서브 그래프에 대응되는 서브 쿼리를 제외한 나머지 쿼리가 존재하는 경우, 상기 나머지 쿼리에 대응되는 추가 서브 쿼리를 생성하는 단계; 및제1 서브 그래프에 대한 서브 쿼리가 상기 추가 서브 쿼리의 자식으로 구성된 타겟 쿼리의 실행 계획을 생성하는 단계를 포함하는,쿼리 실행 방법.

제 1항에 있어서, 상기 타겟 쿼리의 실행 계획을 최적화하는 단계는상기 타겟 쿼리에 대한 복수의 후보 쿼리 실행 계획을 생성하는 단계;지정된 비용 모델에 기초하여 상기 복수의 후보 쿼리 실행 계획 각각의 처리 비용을 연산하고, 최소 처리 비용의 후보 쿼리 실행 계획을 획득하는 단계를 포함하는,쿼리 실행 방법.

제 1항에 있어서,상기 정렬 알고리즘을 획득하는 단계는상기 다항 조인 연산자의 각 자식 테이블에 대해 테이블의 카디널리티(Cardinality), 조인 컬럼의 개수, GPU 장치 사용 가능 유무를 기초로 GPU 사용 가능 여부를 판단하는 단계;GPU 사용이 가능한 경우, 테이블의 카디널리티와 상기 테이블의 정렬 대상 컬럼 크기를 이용하여 테이블 정렬 시 필요한 최소 메모리 공간의 크기를 계산하는 단계; 및상기 최소 메모리 공간의 크기와 GPU 가용 크기를 비교하여 상기 정렬 알고리즘을 획득하는 단계를 포함하는,쿼리 실행 방법.

제 11항에 있어서,상기 정렬 알고리즘을 획득하는 단계는,GPU 가용 크기보다 상기 최소 메모리 공간의 크기가 크고 정렬 대상 컬럼이 하나인 경우, 이기종(Heterogeneous) 정렬 알고리즘을 획득하는 단계를 포함하는,쿼리 실행 방법.

제 11항에 있어서,상기 정렬 알고리즘을 획득하는 단계는,GPU 가용 크기보다 상기 최소 메모리 공간이 크고 정렬 대상 컬럼이 복수개인 경우 CPU 장치 기반의 비교(comparison) 기반 정렬 알고리즘을 획득하는 단계를 포함하는,쿼리 실행 방법.

제 11항에 있어서,상기 정렬 알고리즘을 획득하는 단계는,GPU 사용이 가능하고 모든 자식 테이블에 대해 GPU 가용 크기보다 상기 최소 메모리 공간이 작으며, 각 자식 테이블에 대해 필요한 정렬 대상 컬럼이 하나인 경우 GPU 장치 기반의 비-비교(non-comparison) 기반의 정렬 알고리즘을 획득하는 단계를 포함하는, 쿼리 실행 방법.

제 11항에 있어서,상기 정렬 알고리즘을 획득하는 단계는,GPU 사용이 가능하고 모든 자식 테이블에 대해 GPU 가용 크기보다 상기 최소 메모리 공간이 작으며, 상기 정렬 대상 컬럼이 복수개인 경우 GPU 장치 기반의 비교 기반 정렬 알고리즘을 획득하는 단계를 포함하는,쿼리 실행 방법.

제 11항에 있어서,상기 정렬 알고리즘을 획득하는 단계는,GPU 사용이 불가능하고 각 자식 테이블에 대해 필요한 정렬 대상 컬럼이 하나인 경우 CPU 장치 기반의 비-비교(non-comparison) 기반의 정렬 알고리즘을 획득하는 단계를 포함하는,쿼리 실행 방법.

제 11항에 있어서,상기 정렬 알고리즘을 획득하는 단계는,GPU 사용이 불가능하고 각 자식 테이블에 대해 필요한 정렬 대상 컬럼이 복수개인 경우 CPU 장치 기반의 비교 기반 정렬 알고리즘을 획득하는 단계를 포함하는,쿼리 실행 방법.

제 1항에 있어서,상기 복수의 서브 그래프는,참조키-참조키 조인 타입과 대응되는 간선으로만 구성된 제1 서브 그래프 및 고유키-참조키 조인 타입과 대응되는 간선을 포함하는 제2 서브 그래프를 포함하고,상기 하나 이상의 조인 컬럼의 정렬 순서를 결정하는 단계는,상기 제1 서브 그래프에 대해 하나 이상의 전역 조인 변수를 추출 하는 단계;상기 추출된 하나 이상의 전역 조인 변수() 각각에 대하여, 상기 조인 그래프 에서 해당 전역 조인 변수를 조인 컬럼으로 포함하는 간선의 집합(), 상기 전역 조인 변수를 포함하는 정점의 집합() 및 정점에 해당하는 데이터베이스 테이블들의 카디널리티의 합() 계산하는 단계;상기 하나 이상의 전역 조인 변수() 각각에 대응되는 튜플 을 획득하고, 값을 기준으로 상기 획득된 하나 이상의 튜플을 정렬 하는 단계; 및 상기 정렬된 튜플을 기초로, 각각의 튜플에 대응되는 전역 조인 변수간 정렬 순서를 결정하고, 상기 각각의 전역 조인 변수를 포함하는 하나 이상의 조인 컬럼의 정렬 순서를 결정하는 단계를 포함하는, 쿼리 실행 방법.

제 18항에 있어서,상기 복수의 서브 그래프에 대한 연산을 수행하는 단계는,하나 이상의 제2 서브 그래프에 포함된 복수의 서브 쿼리 간 처리 순서를 결정하는 단계; 및상기 복수의 서브 쿼리 간 결정된 처리 순서에 따라, 상기 복수의 서브 쿼리의 실행 및 상기 복수의 서브 쿼리의 실행 결과의 정렬을 병렬적으로 수행하는 단계를 포함하는, 쿼리 실행 방법.

제 19항에 있어서,상기 복수의 서브 쿼리 간 결정된 처리 순서에 따라, 상기 복수의 서브 쿼리의 실행 및 상기 복수의 서브 쿼리의 실행 결과의 정렬을 병렬적으로 수행하는 단계는,상기 서브 쿼리()의 실행 결과 데이터의 크기가 GPU 메모리 크기보다 작은 경우, GPU를 이용하여 상기 서브 쿼리()의 실행 결과 데이터의 정렬 및 다음 서브 쿼리()의 실행을 병렬적으로 수행하는 단계; 및상기 서브 쿼리() 의 실행 결과 데이터의 크기가 GPU 메모리 크기보다 큰 경우, GPU를 이용하여 이기종 정렬 알고리즘의 정렬 단위(chunk)의 중간 결과 데이터의 정렬 및 서브 쿼리()의 실행을 병렬적으로 수행하는 단계를 포함하는,쿼리 실행 방법.