새로운 접근법으로 복잡한 비즈니스 SQL 처리 성능을 대폭 증가시켜
KAIST, 기존 美 옴니사이(OmniSci) DBMS 대비, 최대 88배나 처리속도 향상

김민수 교수(좌측 위), 남윤민 박사 (우측 위), 한동형 박사과정(우측 아래)

국내 연구진이 방대한 정보를 저장하고 목적에 맞게 검색, 관리할 수 있는 시스템을 통칭하는 데이터베이스관리시스템(DBMS, DataBase Management System)을 세계 최고 수준의 성능으로 끌어올렸다.

KAIST(한국과학기술원)는 전산학부 김민수 교수 연구팀이 데이터베이스 질의 언어 SQL(Structured Query Language, 구조화 질의어) 처리 성능을 대폭 높인 세계 최고 수준의 DBMS 기술을 개발했다고 23일 밝혔다.

KAIST 관계자에 따르면 김 교수 연구팀은 데이터 처리를 위해 산업 표준으로 사용되는 SQL 질의를 기존 DBMS와는 전혀 다른 방법으로 처리함으로써 성능을 기존 옴니사이(OmniSci) DBMS 대비 최대 88배나 높인 신기술을 개발했다. 김 교수팀이 개발한 이 기술은 오라클·마이크로소프트 SQL서버·IBM DB2 등 타 DBMS에도 적용할 수 있어 고성능 SQL 질의 처리가 필요한 다양한 곳에 폭넓게 적용될 수 있을 것으로 기대된다.

대부분의 DBMS는 SQL 질의를 처리할 때 내부적으로 데이터 테이블들을 `왼쪽 깊은 이진 트리(left-deep binary tree)' 형태로 배치해 처리하는 방법을 사용한다. 지난 수십 년간 상용화돼 온 대부분의 DBMS는 데이터 테이블들의 배치 가능한 가지 수가 기하급수적으로 많기 때문에 이를 `왼쪽 깊은 이진 트리' 형태로 배치해 SQL 질의를 처리해 왔다.

임의의 두 테이블이 기본 키(primary key, PK)와 외래 키(foreign key, FK)라 불리는 관계로 결합(조인 연산)하는 경우에는 이러한 방법으로 SQL 질의를 효과적으로 처리할 수 있다. 여기서 기본 키는 각 데이터 행(row)을 유일하게 식별할 수 있는 열(column)이고, 외래 키는 그렇지 않은 열이다.

지난 수십 년간 산업에서 사용되는 DB의 구조가 점점 복잡해지면서 두 테이블은 PK-FK 관계가 아닌 FK-FK 관계, 즉 외래 키와 외래 키의 관계로 결합하는 복잡한 형태의 SQL 질의들이 많아지고 있다. 실제 DBMS의 성능을 측정하는 산업 표준 벤치마크인 TPC-DS에서 전체 벤치마크의 26%가 이런 복잡한 SQL 질의들로 구성돼 있고 기계학습(머신러닝), 생물 정보학 등 다양한 분야들서도 이러한 복잡한 SQL 질의 사용이 점차 증가하는 추세다.

이전에 나온 DBMS들은 두 테이블이 주로 PK-FK 관계로 결합한다는 가정하에 개발됐기 때문에 FK-FK 결합이 필요한 복잡한 SQL 질의를 매우 느리거나 심지어 처리하지 못하는 실패를 거듭해왔다.

김 교수팀은 문제 해결을 위해 테이블들을 하나의 커다란 `왼쪽 깊은 이진 트리' 형태가 아닌 여러 개의 작은 `왼쪽 깊은 이진 트리'를 `n항 조인 연산자'로 묶는 형태로 배치해 처리하는 기술을 개발했다. 이때 각각의 `작은 이진 트리' 안에는 FK-FK 결합 관계가 발생하지 않도록 테이블들을 배치하는 것이 핵심이다.

각각의 `작은 이진 트리'의 처리 결과물을 `n항 조인 연산자'로 결합해 최종 결과물을 구하는 것도 난제로 꼽히는데 연구팀은 `최악-최적(worst-case optimal) 조인 알고리즘'이라는 방법으로 이 문제를 해결했다.

`최악-최적 조인 알고리즘'은 그래프 데이터를 처리할 때 이론적으로 가장 우수하다고 알려진 알고리즘이다. 김 교수 연구팀은 세계에서 가장 먼저 이 알고리즘을 SQL 질의 처리에 적용해 난제를 해결하는 데 성공했다.

김민수 교수 연구팀은 새로 개발한 DBMS 기술을 GPU 기반의 DBMS 개발업체인 미국 옴니사이(OmniSci)社 제품에 적용한 결과, OmniSci DBMS보다 성능이 최대 88배나 향상된 결과를 얻었다. 또 TPC-DS 벤치마크에서도 세계 최고 수준의 성능을 가진 기존의 상용 DBMS보다 5~20배나 더 빠른 사실을 확인했다. TPC-DS는 DBMS의 성능을 측정하기 위한 산업 표준의 최신 벤치마크이다.

교신저자로 참여한 김민수 교수는 "연구팀이 개발한 새로운 기술은 대부분의 DBMS에 적용할 수 있기 때문에 산업적 측면에서 파급 효과가 매우 클 것으로 기대한다ˮ 라고 말했다.

이번 연구에는 김 교수의 제자이자 미국 옴니사이(OmniSci)社에 재직 중인 남윤민 박사가 제1 저자로, 김 교수가 교신저자로 참여했으며 지난 18일 미국 오리건주 포틀랜드에서 열린 데이터베이스 분야 최고의 국제학술대회로 꼽히는 `시그모드(SIGMOD)'에서 발표됐다. (논문명 : SPRINTER: A Fast 𝑛-ary Join Query Processing Method for Complex OLAP Queries).

한편, 이 연구는 한국연구재단 선도연구센터 사업 및 중견연구자 지원사업, 과기정통부 IITP SW스타랩 사업의 지원을 받아 수행됐다. (끝)

□ 연구개요

1. 연구 배경
오늘날 메인 메모리 기반의 SQL 질의 처리 시스템들은 산업 분야에서 비즈니스 데이터들을 분석 처리하는 데 필수적으로 사용되고 있다. 예를 들어 Oracle, IBM DB2, 마이크로소프트 SQL Server, OmniSci, MonetDB, MemSQL, SAP HANA, CoGaDB, Kinetica, Peloton, Ocelot, Quickstep, Hyrise 등 많은 상용 DBMS 및 오픈소스 DBMS들이 사용되고 있다. 한편 사회가 고도화됨에 따라 데이터베이스의 구조도 점점 복잡해지고 있다. 그에 따라 데이터 분석의 위해 사용되는 SQL 질의도 전통적인 PK-FK (기본키-외래키) 조인이 아닌, FK-FK(외래키-외래키) 조인이 포함된 복잡한 형태의 SQL 질의가 점점 더 많이 사용되고 있다. 그러나, 위에서 열거한 오늘날의 대부분의 DBMS들은 FK-FK 조인이 포함된 복잡한 SQL 질의를 잘 처리하지 못한다. 외래 키는 특정 투플을 유일하게 식별하지 못하고 여러 투플들과 매치되는 특성이 있어서, 두 테이블이 FK-FK 관계로 조인이 되는 경우 너무 많은 투플 쌍(pair)들이 생성되어 메모리 공간 부족으로 처리하지 못하는 문제가 발생한다. 또한 메모리 사용량을 줄이기 위해 계산을 많이 하는 방식으로 처리할 경우 시간이 매우 오래 걸리는 문제가 발생한다.

2. 연구 내용
복잡한 SQL 질의 처리시 메모리 공간 부족이나 시간이 매우 오래 걸리는 문제가 발생하는 주요 원인이 데이터 테이블들을 하나의 커다란 왼쪽 깊은 이진 트리(left-deep binary tree) 형태로 배치하기 때문에 발생함을 찾아냈다. 테이블들의 개수가 증가할수록 또는 FK-FK 조인이 많이 포함되어 있을수록 문제가 더 심각하게 발생한다. 이 문제를 해결하기 위해 하나의 커다란 왼쪽 깊은 이진 트리 대신 테이블들을 여러 개의 작은 왼쪽 깊은 이진 트리들을 n항 조인 연산자로 묶는 형태로 배치하여 처리하는 기술을 개발했다. 이때 각각의 작은 이진 트리 안에는 FK-FK 결합 관계가 발생하지 않도록 테이블들을 배치를 하는 것이 핵심이다. 그 결과 각각의 작은 이진 트리는 메모리 문제없이 빠르게 처리할 수 있게 된다. 그 다음 각각의 작은 이진 트리의 처리 결과를 모아서 한꺼번에 n항 조인 연산자로 처리한다. 이때 메모리 문제가 발생하지 않으면서 최대한 빠르게 처리할 수 있도록 n항 조인 연산자를 최악 최적(worst-case optimal) 조인 알고리즘이라는 방법으로 처리한다. 최악 최적 조인 알고리즘은 그래프 데이터를 처리할 때 이론적으로 가장 우수하다고 알려져 있는 알고리즘인데, 이를 약간 변형하여 SQL 질의 처리에 적용했다. 본 연구의 기술은 게임 등에서 흔히 사용되는 GPU를 장착할 경우 SQL 처리 속도가 더욱 가속되는 특징을 지닌다. 일반적으로 GPU는 CPU보다 이론적인 계산 성능이 우수하다. 이 점을 이용하여 주어진 SQL 질의에서 시간이 많이 소요되는 부분들을 GPU로 스트리밍하면서 GPU에서 계산함으로써 SQL 질의 처리 속도를 가속한다.

3. 기대 효과
해당 기술을 GPU 기반의 DBMS로 매우 유명한 미국 OmniSci(옴니사이) DBMS에 적용하였으며 그 결과 원래의 OmniSci DBMS에 비해 최대 88배 성능을 향상시킬 수 있었다. 이 수치는 본 기술이 얼마나 효과가 좋고 우수한 기술인지를 단적으로 보여주는 결과이다. 또한 TPC-DS 벤치마크를 이용하여 종래 세계 최고 성능의 상용 DBMS들과 성능 비교를 한 결과 본 기술이 적용된 OmniSCi DBMS가 최소 5배, 최대 20배 더 빠른 성능을 보였다. 본 기술은 이론 수준의 기술이 아니라 이미 OmniSci라는 유명 DBMS에 적용하여 시스템 수준에서 효과를 확인한 상용 직전 수준의 기술이다. 또한, 대부분의 DBMS에 적용 가능한 기술이기 때문에 고성능 SQL 질의 처리가 필요한 다양한 DBMS들에 폭넓게 적용되는 등 산업적 파급 효과가 클 것으로 기대한다.

□ 그림 설명
그림 1. 종래 DBMS들은 데이터 테이블들을 왼쪽 깊은 이진 트리 방식으로 배치하여 밑에서부터 위로 올라가면서 처리한다 (왼쪽 그림). 파란색 또는 초록색 박스는 데이터 테이블이고, 나비 넥타이 모양은 두 테이블을 결합하는 조인 연산자이다. 파란색 테이블이 두 개 이상 있으면 FK-FK 조인이 발생한다. 본 DBMS 기술은 커다른 하나의 이진 트리 대신 여러 개의 작은 이진 트리들을 구성한다 (오른쪽 그림). S1, S2, S3 각각은 왼쪽 깊은 이진 트리이다. 각 이진 트리에는 파란색 테이블이 한 개씩만 있어 FK-FK 조인이 발생하지 않는다. 빨간색 나비 넥타이 모양은 최악 최적 조인 알고리즘이 적용된 n항 조인 연산자이다. 각 이진 트리의 결과물을 n항 조인 연산자로 한꺼번에 결합하여 처리한다. 

김민수 교수 이력사항

□ 인적사항                                       
 ○ 소 속 : KAIST
 ○ 전 화 : 042-350-3582
 ○ e-mail : minsoo.k@kaist.ac.kr

□ 학력
 ○ 2006년 KAIST 박사 (전산학)
 ○ 2000년 KAIST 석사 (전산학)
 ○ 1998년 KAIST 학사 (전산학)
 
□ 경력사항
 ○ 2020~현재 : KAIST 전산학부 영년직 부교수
 ○ 2011~2020년 : DGIST 정보통신융합전공 조교수 / 부교수 / 영년직 부교수
 ○ 2019~2020년 : DGIST 학술정보처장
 ○ 2018~2020년 : 연구재단 ERC 암흑데이터 극한활용 연구센터 센터장
 ○ 2015~2016년 : NVIDIA GPU Research Center 센터장
 ○ 2009~2011년 : 미국 IBM Almaden Research Center 연구원
 ○ 2007~2009년 : 미국 University of Illinois Urbana-Champaign 포닥 연구원

KAIST 홍보실 제공