yeolyi.com성열의 컴퓨터공학

조인

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

“주문마다 산 사람의 도시”를 보려면 나눠 둔 회원 표와 주문 표를 다시 붙여야 합니다. 행이 수백만 개라면 이 일은 얼마나 걸릴까요?

조인

이렇게 두 표를 키가 같은 행끼리 맞춰 붙이는 일을 조인(join)이라 합니다. SQL에서는 관계형 데이터베이스 글에서 본 대로 JOIN과 ON으로 어떤 열끼리 맞출지 적습니다.

SELECT orders.item, members.city
FROM orders JOIN members ON orders.member_id = members.id;

어떻게 붙일지는 데이터베이스가 정합니다. 방법은 크게 셋입니다.

주문 100,000
회원 10,000
겹친 반복1,000,000,000번 · 1.0초
인덱스로 찾기1,400,000번 · 0.001초
해시 조인110,000번 · 1밀리초 미만

주문과 회원이 함께 늘면 겹친 반복만 금세 몇 시간, 하루로 늘어납니다. 회원이 10명뿐이면 셋의 차이가 거의 없습니다.

주문이 N개, 회원이 M명이면 겹친 반복은 시간 복잡도로 O(N × M)이고, 해시 조인은 O(N + M)입니다. 그래서 데이터베이스는 표의 크기와 인덱스가 있는지를 보고 방법을 고릅니다. 이렇게 같은 SQL을 어떤 방법으로 실행할지 정하는 일을 쿼리 최적화(query optimization)라 합니다.

도전 문제

주문 1,000건과 회원 1,000명을 조인합니다. 해시 조인은 회원으로 해시 테이블을 만들고(회원마다 1번), 주문마다 1번 찾습니다. 그런데 메모리가 모자라 해시 테이블을 회원 250명분씩만 만들 수 있다면, 회원을 넷으로 나눠 네 번 조인합니다. 매번 주문을 처음부터 다시 훑는다면 모두 몇 번 일할까요? 숫자로 답하세요.