[논문]NUMA 구조 기반의 효율적인 해시 조인 알고리즘

최성준; 김홍연; 민준기

NUMA 구조 기반의 효율적인 해시 조인 알고리즘
An efficient algorithm for hash-join on NUMA architecture 원문보기

최성준 (한국기술교육대학교 (KOREATECH) 컴퓨터공학부) , 김홍연 (한국기술교육대학교 (KOREATECH) 컴퓨터공학부) , 민준기 (한국기술교육대학교 (KOREATECH) 컴퓨터공학부)

최근, 불균일 기억 장치 접근 (NUMA) 구조가 부각됨에 따라 NUMA 구조 기반의 관계 연산 기법들이 제안되고 있다. 본 논문에서는 NUMA 구조 기반의 효율적인 해시 조인 기법을 제안한다. NUMA 구조에서 조인 속성 값의 분포가 편중된 릴레이션들 간의 조인은 NUMA 노드들 간의 부하 불균형과 과도한 원격 메모리 접근을 발생시킬 수 있다. 제안 기법에서는 근사 히스토그램을 이용하여 조인 속성 값의 분포를 파악하고, 이를 기반으로 원격 메모리 접근을 줄이는 전달 방안을 제안한다. 실험에서는 입력 릴레이션들에 대해 조인 속성 값의 분포를 변화시키면서 제안 기법에 대한 성능을 평가한다.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

최근 데이터베이스 관계 연산의 성능을 향상시키기 위해 NUMA 구조를 활용한 연구들이 활발히 진행되고 있다 [1, 6-9]. 본 논문에서는 NUMA 구조 기반의 효율적인 해시 (hash) 조인 기법을 제안한다.

가설 설정

그림 3에 나타난 NUMA 구조는 2개의 NUMA 노드들 n_i와 n_j로 구성되어 있으며, 각 튜플의 조인 속성 값이 짝수이면 n_i로, 홀수이면 n_j로 각각 전달된다. 그리고 조인 속성 값으로 3을 갖는 튜플들은 릴레이션 R에서, 조인 속성 값으로 1을 갖는 튜플들은 릴레이션 S에서 각각 빈번히 발생된다고 가정한다. 그림 3에서 조인 속성 값 3을 갖는 튜플들은 릴레이션 R에서만 빈번히 발생되므로, 각 청크 R_i에서 조인 속성 값 3을 갖는 튜플들은 각 NUMA 노드 n_i의 지역 메모리에 적재되고, 각 청크 S_i에서 조인 속성 값 3을 갖는 튜플들은 전체 NUMA 노드들 n_i와 n_j에게 전파된다.
본 논문에서는 N개의 NUMA 노드들로 구성된 NUMA 구조를 고려하고, 각 NUMA 노드 ni(0≤i<N)는 하나의 스레드를 수행시킨다고 가정한다.

제안 방법

조인 속성 값의 편중 정도를 판별하기 위해, 본 논문에서는 근사 히스토그램 [5]을 사용한다. 그리고 NUMA 노드들 간의 부하를 균등하게 만들기 위해, 각 조인 속성 값의 편중된 정도에 따라 해당 속성 값을 지닌 튜플을 지역 메모리에 유지할지 또는 다른 NUMA 노드로 전달할지를 결정한다.
근사 히스토그램 생성 단계: 이 단계에서, 각 NUMA 노드 n_i에서 청크 R_i과 S_i에 속한 튜플들의 조인 속성 값들에 대한 분포를 파악한다. 이를 위하여, 각 NUMA 노드 n_i는 청크 R_i와 S_i에 대해 샘플링을 수행하고, 샘플링된 튜플들의 조인 속성 값들에 대해 R_i와 S_i에 대한 지역 (local) 근사 히스토그램들 hist(R_i)와 hist(S_i)를 각각 생성한다.
기존 조인 기법에 반하여, 본 논문에서 제안하는 해시 조인 기법은 각 NUMA 노드들 간의 부하 균형 및 원격 메모리 접근을 최소화하기 위하여 각 튜플의 조인 속성 값이 편중되는지를 판단하고 이에 따라 효율적인 조인 전략을 적용한다.
본 논문에서 제안하는 해시 조인 기법은 다음과 같은 3 단계-근사 히스토그램 생성, 지역 해시 테이블 생성, 지역 조인-로 구성되어 진다.
본 논문의 제안 기법에서는 NUMA 구조를 고려한 효율적인 해시 조인 기법을 제안하였다. 본 논문의 실험에서 조인 속성 값에 대한 분포가 편중될수록 제안 기법의 원격 메모리 접근 횟수는 감소하므로, 단순 해시 조인 기법의 비하여 제안 기법의 성능이 뛰어남을 보였다.
에 속한 튜플들의 조인 속성 값들에 대한 분포를 파악한다. 이를 위하여, 각 NUMA 노드 n_i는 청크 R_i와 S_i에 대해 샘플링을 수행하고, 샘플링된 튜플들의 조인 속성 값들에 대해 R_i와 S_i에 대한 지역 (local) 근사 히스토그램들 hist(R_i)와 hist(S_i)를 각각 생성한다. 이 때, 사용자 정의 값 λ 이상의 빈도수를 지니는 조인 속성 값들을 편중된 조인 속성 값들이라 하고 sk(R_i), sk(S_i)로 표기한다.
그리고 각 NUMA 노드는 4개의 스레드들을 수행시켜 조인을 수행한다. 제안 기법은 ubuntu 16.04 환경에서 C++로 구현하고 gcc version 5.1.0 컴파일러를 이용하여 컴파일 하였다.

대상 데이터

본 논문에서 제안 기법의 성능 평가를 위해 2개의 NUMA 노드들로 구성된 컴퓨터를 사용하였으며, 각 NUMA 노드의 CPU는 Intel Xeon E5-2609 v3이고 지역 메모리의 크기는 32 Gbyte이다. 그리고 각 NUMA 노드는 4개의 스레드들을 수행시켜 조인을 수행한다.
본 논문의 실험에서는 합성 데이터를 이용하였으며 릴레이션 R의 튜플 수는 1.0*10⁵개이고 조인 속성 값의 분포는 균등 분포이다. 릴레이션 S의 튜플 수는 1.

이론/모형

조인 속성 값의 편중 정도를 판별하기 위해, 본 논문에서는 근사 히스토그램 [5]을 사용한다. 그리고 NUMA 노드들 간의 부하를 균등하게 만들기 위해, 각 조인 속성 값의 편중된 정도에 따라 해당 속성 값을 지닌 튜플을 지역 메모리에 유지할지 또는 다른 NUMA 노드로 전달할지를 결정한다.

성능/효과

기존 단순 해시 조인 기법에서는 조인 속성 값의 빈도수와 상관없이 데이터 분할 단계를 수행하여 튜플들을 각 NUMA 노드에 전달한다. 그러나 본 논문에서 제안하는 NUMA 구조 기반의 해시 조인 기법에서는 원격 메모리 접근 횟수를 줄이기 위하여 릴레이션 R과 S의 속한 튜플 들의 조인 속성 값의 발생 빈도에 따라서 선별적으로 튜플들을 다른 NUMA 노드들에게 전달한다.
본 논문의 제안 기법에서는 NUMA 구조를 고려한 효율적인 해시 조인 기법을 제안하였다. 본 논문의 실험에서 조인 속성 값에 대한 분포가 편중될수록 제안 기법의 원격 메모리 접근 횟수는 감소하므로, 단순 해시 조인 기법의 비하여 제안 기법의 성능이 뛰어남을 보였다.
따라서 단순 해시 조인 기법에서는 릴레이션 S에 속한 편중된 조인 속성 값을 지닌 튜플들을 한 NUMA 노드의 지역 메모리로 전송하기 위한 원격 메모리 접근이 빈번히 발생되어 skew factor 값이 증가함에 따라서 전체적인 조인 성능이 저하된다. 이에 반하여 제안 기법에서는 릴레이션 S에 속한 편중된 조인 속성 값을 지닌 튜플들을각 NUMA 노드의 지역 메모리에 유지하고 대신 빈번히 발생되지 않는 릴레이션 R에 속한 튜플들을 각 NUMA 노드에 전파하여 원격 메모리 접근을 줄임으로서 skew factor 값이 증가함에 따라서 조인 시간이 감소하게 된다. 또한 각 스레드 간의 작업량을 균등하게 유지하는 효과도 얻을 수 있다.
따라서 전체적인 조인 수행 성능이 저하된다. 이에 반하여 제안 기법은 스레드들에 대한 수행 시간이 균등하여 전체적인 조인 성능이 향상된다.

핵심어

질문

논문에서 추출한 답변

기존 대칭형 다중 처리 구조의 문제점은 무엇인가?

최근, 기존 대칭형 다중 처리 구조 (Symmetric Multi Processing: SMP)의 문제점인 프로세서들의 대기와 병목 현상을 완화시킬 수 있는 불균일 기억 장치 접근 구조 (Non-Uniform Memory Access: NUMA)가 부각되고 있다 [1-3]. NUMA 구조에서는 복수 개의 NUMA 노드 (node)들이 물리적으로 분산되어 있고, 각 노드는 1개 이상의 프로세서들과 하나의 공용 메모리로 구성된다 [4].

불균일 기억 장치 접근 구조의 장점은?

최근, 기존 대칭형 다중 처리 구조 (Symmetric Multi Processing: SMP)의 문제점인 프로세서들의 대기와 병목 현상을 완화시킬 수 있는 불균일 기억 장치 접근 구조 (Non-Uniform Memory Access: NUMA)가 부각되고 있다 [1-3]. NUMA 구조에서는 복수 개의 NUMA 노드 (node)들이 물리적으로 분산되어 있고, 각 노드는 1개 이상의 프로세서들과 하나의 공용 메모리로 구성된다 [4].

단순 해시 조인 기법에서 전체적인 조인 성능이 저하되는 이유는 무엇 때문인가?

릴레이션 R에 속한 튜플들은 skew factor 값과 상관없이 균등 분포를 따르나 skew factor가 증가함에 따라 릴레이션 S에 속한 튜플들의 조인 속성 값이 편중되게 된다. 따라서 단순 해시 조인 기법에서는 릴레이션 S에 속한 편중된 조인 속성 값을 지닌 튜플들을 한 NUMA 노드의 지역 메모리로 전송하기 위한 원격 메모리 접근이 빈번히 발생되어 skew factor 값이 증가함에 따라서 전체적인 조인 성능이 저하된다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

NUMA 구조 기반의 효율적인 해시 조인 알고리즘
An efficient algorithm for hash-join on NUMA architecture 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

NUMA 구조 기반의 효율적인 해시 조인 알고리즘 An efficient algorithm for hash-join on NUMA architecture 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

NUMA 구조 기반의 효율적인 해시 조인 알고리즘
An efficient algorithm for hash-join on NUMA architecture 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper