| 1 |
1
데이터베이스를 포함하는 병합 조인 시스템의 병합 조인 방법으로서,상기 데이터베이스에서 병합 조인에 참여하는 조인 열의 현재 위치 이후의 데이터를 2보다 큰 K개의 파티션으로 불균등하게 파티셔닝하는 단계,상기 K개의 파티션 중 첫 번째 파티션을 제외한 나머지 파티션의 첫 번째 값과 병합 조인을 위해 찾고자 하는 값이 특정 조건을 만족하는지 비교하는 단계,상기 비교의 결과에 기초해서 상기 찾고자 하는 값이 존재할 것으로 예상되는 파티션을 결정하는 단계, 그리고상기 결정한 파티션에 k-ary 탐색을 적용하는 단계를 포함하는 병합 조인 방법
|
| 2 |
2
제1항에서,상기 K개의 파티션 중 첫 번째부터 (K-1)번째 파티션의 파티션 크기는 동일한 제1 크기를 가지며, 마지막 파티션의 파티션 크기는 상기 제1 크기보다 큰 제2 크기를 가지는 병합 조인 방법
|
| 3 |
3
제2항에서,상기 결정한 파티션이 상기 마지막 파티션인 경우, 다음 탐색에 사용할 상기 파티션 크기를 제3 크기로 증가시키는 단계를 더 포함하는 병합 조인 방법
|
| 4 |
4
제3항에서,상기 제3 크기는 상기 제1 크기의 K배인 병합 조인 방법
|
| 5 |
5
제3항에서,상기 k-ary 탐색을 적용하는 단계는,상기 마지막 파티션을 불균등하게 K개의 파티션으로 파티셔닝하는 단계,상기 K개의 새 파티션 중 첫 번째 파티션을 제외한 나머지 파티션의 첫 번째 값과 상기 찾고자 하는 값이 상기 특정 조건을 만족하는지 비교하는 단계,상기 비교의 결과에 기초해서 상기 찾고자 하는 값이 존재할 것으로 예상되는 파티션을 결정하는 단계, 그리고상기 결정한 파티션에 k-ary 탐색을 적용하는 단계를 포함하는 병합 조인 방법
|
| 6 |
6
제2항에서,를 상기 제1 크기로 결정하는 단계를 더 포함하며,상기 ceil() 함수는 소수점 이하를 올림하는 함수이며,상기 Rate는 상기 조인 열의 데이터 개수와 상기 병합 조인에 참여하는 다른 열의 데이터 개수 중 큰 수를 작은 수로 나눈 값인병합 조인 방법
|
| 7 |
7
제1항에서,상기 k-ary 탐색을 적용하는 단계는, 상기 결정한 파티션의 데이터를 균등하게 K개의 파티션으로 파티셔닝하는 k-ary 탐색을 수행하는 단계를 포함하는 병합 조인 방법
|
| 8 |
8
제1항에서,상기 비교하는 단계는,제1 벡터 레지스터에 상기 나머지 파티션의 첫 번째 값을 차례로 로딩하는 단계,제2 벡터 레지스터에 상기 찾고자 하는 값을 중복하여 로딩하는 단계, 그리고상기 제1 벡터 레지스터와 상기 제2 벡터 레지스터를 벡터 비교하여 비교 결과 마스크를 생성하는 단계를 포함하며,상기 결정하는 단계는, 상기 비교 결과 마스크에 기초해서 상기 찾고자 하는 값이 존재할 것으로 예상되는 파티션을 결정하는 단계를 포함하는병합 조인 방법
|
| 9 |
9
제8항에서,상기 비교 결과 마스크를 생성하는 단계는, 상기 제1 벡터 레지스터와 상기 제2 벡터 레지스터의 각 요소의 비교 결과의 최상위 비트 값을 이용하여 상기 비교 결과 마스크를 생성하는 단계를 포함하는 병합 조인 방법
|
| 10 |
10
데이터베이스를 포함하는 병합 조인 시스템의 병합 조인 방법으로서,변형된 k-ary 탐색을 포함하는 복수의 탐색 중에서 상기 데이터베이스에서 병합 조인에 참여하는 조인 열의 현재 위치에서 사용할 탐색을 선택하는 단계, 그리고상기 변형된 k-ary 탐색을 선택한 경우, 상기 변형된 k-ary 탐색을 수행하는 단계를 포함하며,상기 변형된 k-ary 탐색을 수행하는 단계는,상기 조인 열의 현재 위치 이후의 데이터를 2보다 큰 K개의 파티션으로 불균등하게 파티셔닝하는 단계,상기 K개의 파티션 중 첫 번째 파티션을 제외한 나머지 파티션의 첫 번째 값과 병합 조인을 위해 찾고자 하는 값이 특정 조건을 만족하는지 비교하는 단계,상기 비교의 결과에 기초해서 상기 찾고자 하는 값이 존재할 것으로 예상되는 파티션을 결정하는 단계, 그리고상기 결정한 파티션에 k-ary 탐색을 적용하는 단계를 포함하는 병합 조인 방법
|
| 11 |
11
제10항에서,상기 선택하는 단계는,상기 현재 위치에서 각 탐색에 필요한 비교 횟수에 기반하여 비용을 추정하는 단계, 그리고상기 복수의 탐색 중 상기 비용이 적게 드는 탐색을 선택하는 단계를 포함하는 병합 조인 방법
|
| 12 |
12
제10항에서,상기 복수의 탐색은 순차 탐색을 더 포함하며,상기 선택하는 단계는,k-ary 탐색에 필요한 비교 횟수를 계산하는 단계,상기 현재 위치에서 상기 비교 횟수만큼 떨어진 곳의 값이 상기 특정 조건을 만족하는지를 체크하는 단계, 그리고상기 값이 상기 특정 조건을 만족하면 상기 순차 탐색을 선택하고, 상기 값이 상기 특정 조건을 만족하지 않으면 상기 변형된 k-ary 탐색을 선택하는 단계를 포함하는 병합 조인 방법
|
| 13 |
13
제12항에서,상기 비교 횟수는 로 결정되며,상기 ceil() 함수는 소수점 이하를 올림하는 함수이며,상기 PartSize는 불균등하게 상기 K개의 파티션으로 파티셔닝할 때 사용하는 파티션 크기인병합 조인 방법
|
| 14 |
14
제13항에서,상기 K개의 파티션 중 첫 번째부터 (K-1)번째 파티션의 파티션 크기는 상기 PartSize이며, 마지막 파티션의 파티션 크기는 상기 PartSize보다 큰 병합 조인 방법
|
| 15 |
15
데이터베이스를 저장하는 저장 장치, 그리고변형된 k-ary 탐색을 사용하는 경우, 상기 데이터베이스에서 병합 조인에 참여하는 조인 열의 현재 위치 이후의 데이터를 2보다 큰 K개의 파티션으로 불균등하게 파티셔닝하고, 상기 K개의 파티션 중 첫 번째 파티션을 제외한 나머지 파티션의 첫 번째 값과 병합 조인을 위해 찾고자 하는 값이 특정 조건을 만족하는지 비교하고, 상기 비교의 결과에 기초해서 상기 찾고자 하는 값이 존재할 것으로 예상되는 파티션을 결정하고, 상기 결정한 파티션에 k-ary 탐색을 적용하는 프로세서를 포함하는 병합 조인 시스템
|
| 16 |
16
제15항에서,상기 K개의 파티션 중 첫 번째부터 (K-1)번째 파티션의 파티션 크기는 동일한 제1 크기를 가지며, 마지막 파티션의 파티션 크기는 상기 제1 크기보다 큰 제2 크기를 가지는 병합 조인 시스템
|
| 17 |
17
제16항에서,상기 프로세서는, 상기 결정한 파티션이 상기 마지막 파티션인 경우, 다음 탐색에 사용할 상기 파티션 크기를 상기 제1 크기의 K배로 증가시키는 병합 조인 시스템
|
| 18 |
18
제16항에서,상기 프로세서는 를 상기 제1 크기로 결정하고,상기 ceil() 함수는 소수점 이하를 올림하는 함수이며,상기 Rate는 상기 조인 열의 데이터 개수와 상기 병합 조인에 참여하는 다른 열의 데이터 개수 중 큰 수를 작은 수로 나눈 값인병합 조인 시스템
|
| 19 |
19
제15항에서,상기 프로세서는, 제1 벡터 레지스터에 상기 나머지 파티션의 첫 번째 값을 차례로 로딩하고, 제2 벡터 레지스터에 상기 찾고자 하는 값을 중복하여 로딩하고, 상기 제1 벡터 레지스터와 상기 제2 벡터 레지스터를 벡터 비교하여 비교 결과 마스크를 생성하고, 상기 비교 결과 마스크에 기초해서 상기 찾고자 하는 값이 존재할 것으로 예상되는 파티션을 결정하는, 병합 조인 시스템
|
| 20 |
20
제15항에서,상기 프로세서는, 상기 변형된 k-ary 탐색을 포함하는 복수의 탐색 중에서, 상기 현재 위치에서 각 탐색에 필요한 비교 횟수에 기반하여 추정한 비용이 적게 드는 탐색을 선택하는, 병합 조인 시스템
|
