[Real MariaDB] 최적화 - 정렬의 처리 방식

정렬의 처리 방식

 쿼리에 order by 가 사용되면 반드시 다음 3가지 방식 중 하나로 정렬이 처리된다. 일반적으로 밑쪽에 있는 정렬 방법으로 갈수록 처리는 점점 느려진다.

정렬 처리 방법	실행 계획의 Extra 코멘트
인덱스를 사용한 정렬	별도의 내용 표기 없음
드라이빙 테이블만 정렬 (조인이 없는 경우 포함)	"Using sort"가 표시됨
조인 결과를 임시 테이블로 저장한 후, 임시 테이블에서 정렬	"Using temporary; Using filesort"가 같이 표시됨

 

인덱스를 사용한 정렬

• 반드시 ORDER BY에 명시된 컬럼이 제일 먼저 읽는 테이블(조인이 사용된 경우 드라이빙 테이블)에 속하고, ORDER BY의 순서대로 생성된 인덱스가 있어야 한다.
• WHERE 절에 첫 번째 읽는 테이블의 컬럼에 대한 조건이 있다면 그 조건과 ORDER BY는 같은 인덱스를 사용할 수 있어야 한다.
• B-Tree 계열의 인덱스가 아닌 해시 인덱스나 전문 검색 인덱스 등에서는 인덱스를 이용한 정렬을 사용할 수 없다. (R-Tree 방식도 사용할 수 없다.)
• 여러 테이블이 조인되는 경우에는 네스티드 루프(Nested-loop) 방식의 조인에서만 사용할 수 있다.

 

드라이빙 테이블만 정렬 ("Using sort")

• 조인에서 드라이빙 테이블의 컬럼만으로 ORDER BY 절이 작성돼야 한다.

SELECT * FROM employees e, salaries s
WHERE s.emp_no = e.emp_no
	AND e.emp_no BETWEEN 100002 AND 100010
ORDER BY e.last_name;

• WHERE 절 조건을 통해서 employees 테이블의 primary key 를 이용하여 검색하면 작업량을 줄일 수 있다.
• 검색은 인덱스 레인지 스캔으로 처리할 수 있지만 ORDER BY 절에 명시된 컬럼은 employees 테이블의 primary key와 전혀 연관이 없으므로 인덱스를 이용한 정렬은 불가능하지만 드라이빙 테이블에 포함된 컬럼이므로 드라이빙 테이블만 먼저 검색하여 정렬을 수행하고 salaries 테이블과 조인한다.
• 정렬을 수행할 때는 SortBuffer로 복사하여 정렬을 수행한다.

 

임시 테이블을 이용한 정렬 ("Using temporary; Using filesort")

• 드라이빙 테이블만 정렬을 하는 경우에는 임시 테이블이 필요하지 않지만 그 외 패턴의 쿼리에서는 항상 조인의 결과를 임시 테이블에 저장하고, 그 결과를 다시 정렬하는 과정을 거친다.
• 이 방법은 정렬해야 할 레코드 건수가 가장 많아지기 때문에 가장 느리다.

SELECT * FROM employees e, salaries s
WHERE s.emp_no=e.emp_no AND e.emp_no BETWEEN 100002 AND 100010
ORDER BY s.salary;

• 위 쿼리는 ORDER BY 절의 정렬 기준 컬럼이 드라이빙 테이블에 존재하지 않으므로 정렬이 수행되기 전에 반드시 salaries 테이블을 읽어야 하므로 이 쿼리는 반드시 조인된 데이터를 가지고 정렬해야 한다.

 

정렬 방식의 성능 비교

• LIMIT 는 테이블이나 처리 결과의 일부만 가져오기 때문에 DB가 처리해야 할 작업량을 줄이는 역할을 한다.
• ORDER BY 나 GROUP BY 와 같은 작업은 조건을 만족하는 레코드를 모두 가져와서 정렬을 수행하거나 그룹핑 작업을 실행해야만 LIMIT 로 건수 제한을 할 수 있으므로 WHERE 조건이 이무리 인덱스를 잘 활용하도록 튜닝해도 쿼리가 느려지는 경우가 자주 발생한다.
• 쿼리가 처리되는 방법은 "스트리밍 처리" 와 "버퍼링 처리" 라는 2가지 방식으로 구분된다.

 

스트리밍(streaming) 방식

• 서버 쪽에서 처리해야 할 데이터가 얼마나 될지에 관계없이 조건에 일치하는 레코드가 검색될 때마다 바로바로 클라이언트로 전송해주는 방식이다.
• 스트리밍 방식으로 처리되는 쿼리는 얼마나 많은 레코드를 조회하느냐에 상관없이 빠른 응답 시간을 보장해 준다.

* 스트리밍 처리는 어떤 클라이언트 도구나 API를 사용하느냐에 따라 그 방식에 차이가 있을 수 있다. 대표적으로 JDBC 라이브러리를 이용해 "SELECT * FROM tb_bigtable"와 같은 쿼리를 실행하면 DB는 레코드를 읽자마자 클라이언트로 결과를 전달한다. 하지만 JDBC는 DB로부터 받는 레코드를 자체적인 버퍼에 모두 담아두고, 마지막 레코드를 전달되면 클라이언트의 애플리케이션에 반환한다.

 

버퍼링(Buffering) 방식

• ORDER BY 나 GROUP BY 와 같은 처리는 WHERE 조건에 일치하는 모든 레코드를 가져온 후, 정렬하거나 그룹핑을 해서 차례대로 보내야 하기 때문에 쿼리의 결과가 스트리밍 되는 것을 불가능하게 한다.
• DB에서 모든 레코드를 검색하고 정렬하는 동안 클라이언트는 아무것도 하지 않고 기다려야 하므로 응답 시간이 느려진다.

 

* 정렬 처리 방식 중에서 인덱스를 사용한 정렬 방식만 스트리밍 형태의 처리이며, 나머지는 모두 버퍼링된 후에 정렬된다.

 

* 일반적으로 RDBMS의 조인에서는 WHERE 조건에 일치하는 대상 레코드 건수가 적은 테이블을 우선으로 드라이빙 테이블로 선정한다. 일반적으로 네스티드 루프 조인 방식에서는 드라이빙 테이블의 레코드 건수만큼 드리븐 테이블에 대해서 랜덤 액세스가 발생하기 때문이다.

 

* 가능하다면 인덱스를 사용한 정렬로 유도하고 그렇지 못하다면 최소한 드라이빙 테이블만 정렬해도 되는 수준으로 유도하는 것도 좋은 튜닝 방법이다.

 

ORDER BY .. LIMIT n 최적화

• ORDER BY 절을 가진 쿼리가 인덱스를 사용하지 못할 때 실시간 정렬(Using filesort)을 수행해야만 한다.
• 조건절에 일치하는 레코드들을 모두 가져와서 소트 버퍼를 이용해서 퀵 소트(Quick sort) 알고리즘을 수행하게 된다.
• 정렬해야할 대상 레코드가 너무 많으면 소트 버퍼 크기만큼의 레코드를 모아서 정렬하고 정렬된 결과를 다시 병합(Sort_merge_pass)하는 과정을 거쳐야 한다. 이 과정은 CPU 뿐만 아니라 디스크에도 많은 부담을 주게 된다.
• MySQL 5.6과 MariaDB 10.0에서는 ORDER BY 절과 LIMIT n 절을 함께 사용하는 경우에 소트 버퍼에 우선 순위 큐를 이용하여 정렬을 수행하도록 개선되었다.
• 우선 순위 큐를 이용하는 경우에 정렬의 대상이 많더라도 유지해야할 힙의 크기를 작게 유지하므로 공간, 시간 복잡도 상으로 많은 이점이 있다.
• LIMIT n 으로 가져가는 레코드의 바이트 크기가 우선 순위 큐가 만들어지는 소트 버퍼의 크기보다 작은 경우에만 이 방법이 적용 가능하다.

 

---

참고자료

Real MariaDB - 이성욱 지음 <위키북스>