2025.04.15 nested loop join, huge table
어제 공부하던 것을 복습해 보겠습니다.
join 시 대표적인 알고리즘으로 nested loop join이 있습니다.
이는 드라이빙 테이블을 기준으로 드리븐 테이블을 순회하도록 구현되어 있습니다.
순회 시 인덱스가 없을 경우
드라이빙 테이블과 드리븐 테이블은 n * m으로 동일해 보이지만, 데이터 페이지 접근을 생각해야 합니다.
예로 A테이블은 튜플이 10개, 데이터 페이지 IO는 1번입니다. B테이블은 튜플이 100개 데이터 IO는 10번입니다.
A를 드라이빙 테이블로 하게 된다면 A데이터 페이지 IO(1) + [A튜플(10) * B데이터페이지(10)] = 101이 됩니다.
B를 드라이빙 테이블로 하게 된다면 B데이터 페이지 IO(10) + [B튜플(100) * A데이터페이지(1)] = 110이 됩니다.
차이가 얼마 나지 않는 것처럼 보이지만 튜플의 수가 많아지면 선형적으로 증가하게 됩니다.
인덱스가 있다면 대괄호 안의 데이터 페이지가 log_b(드리븐 테이블 튜플 수)이 될 것입니다.
더 작아지겠지요.
또 조인이 많으면 탐색이 중첩되니 느려지겠지요.
넘어가 봅시다.
로우 수가 많아지면 데이터 조회가 느려집니다.
단순히 데이터가 많아지기 때문만이 아니라, 디스크 접근, 인덱스 탐색, 메모리등 다양한 자원의 사용량이 증가하기 때문입니다.
버퍼 풀
모든 것이 버퍼에 저장될 수 없으므로 디스크 IO가 증가됩니다.
인덱스
b+tree 인덱스는 fanout 구조이지만 데이터가 많아지면 트리가 깊어집니다.
인덱스 탐색 또한 더 많은 인덱스 페이지를 읽어야 하기에 시간이 소모됩니다.
조인
앞에서 말한 nested loop join을 사용했을 때 드라이빙이건 드리븐이건 데이터가 많은 테이블을 조인하는 것은 순회를 많이 하게 되는 안 좋은 선택입니다.
정렬, 그룹핑
처리중에 데이터가 크면 메모리에서 처리할 수 없어서 임시 테이블과 디스크 spill이 이뤄지고 많이 느려지게 됩니다.
집계
단순 sum, count는(select sum(price) from order] 메모리에 올리지 않고 row를 순회하면서 누적집계를 합니다.
버퍼에 없다면 디스크IO는 이뤄집니다.
count(*)[select count(*) from orders]과 count(col) 둘은 좀 다른게, 전자는 데이터 페이지를 스캔합니다. 후자는 null을 제외해야하니 데이터를 읽어야합니다.
count(distinct col)은 중복 제거를 위해 메모리에 저장해야하고 클 경우 디스크 spill이 발생할 수 있습니다.
테이블이 커지면 단순히 데이터가 많아서 읽기 오래 걸리는 문제보다 버퍼 풀에서 없어 캐시 미스, 이로 인한 많은 디스크 IO, 인덱스의 깊이가 늘어나는 등 여러 문제들이 복합적인 원인이 됩니다.
내일 추가 공부.
++++
엔지니어로서, 나는 침묵을 지키는 것보다 멍청하다고 불리는 게 낫다 | GeekNews
바보가 되는 것보다 침묵하는 것이 더 나쁜 이유"제 자신을 드러내고 어리석은 질문을 던지는 게 실제로 제 엔지니어 경력에 도움이 됐습니다."바보처럼 보일까 봐 두려운가요? 당신만 그런 게
news.hada.io
질문을 해서 모르는 것을 알아내는 것이 즐겁습니다. 애매한 체로 회의가 끝나면 뭔가 찝찝합니다. 혼자 골똘히 생각해 보지만, 생각이 꼬리에 꼬리를 물고 주제에서 벗어나는 경우도 종종 있습니다.
그냥 질문합니다. 다른 사람들도 모르는데 가만히 있는 겁니다.
제가 아무도 안 하면 내가 한다는 마인드가 있긴 합니다.