ORDER BY 처리

정렬 처리

• 레코드 1~2건을 가져오는 쿼리를 제외하면 대부분의 SELECT 쿼리에서 정렬은 필수적으로 사용된다.
• 데이터 웨어하우스처럼 대량의 데이터를 조회해서 일괄 처리하는 기능이 아니라면 아마도 레코드 정렬 요건은 대부분의 조회 쿼리에 포함되어 있을 것이다.
• 정렬을 처리하는 방법은 크게 인덱스를 이용하는 방법과 쿼리가 실행될 때 Filesort 라는 별도의 처리를 이용하는 방법으로 나눌 수 있다.

인덱스 정렬 vs Using Filesort

정렬 처리 방법	장점	단점
인덱스 이용	- INSERT, UPDATE, DELETE 쿼리가 실행될 때 이미 인덱스가 정렬되어 있어서 순서대로 읽기만 하면 되므로 매우 빠르다.	- INSERT, UPDATE, DELETE 작업 시 부가적인 인덱스 추가/삭제 작업이 필요하므로 느리다. - 인덱스 때문에 디스크 공간이 더 많이 필요하다. - 인덱스의 개수가 늘어날 수록 InnoDB의 버퍼 풀을 위한 메모리가 많이 필요하다.
Filesort 이용	- 인덱스를 생성하지 않아도 되므로 인덱스를 이용할 때의 단점이 장점으로 바뀐다. - 정렬해야 할 레코드가 많지 않으면 메모리에서 Filesort가 처리되므로 충분히 빠르다.	- 정렬 작업이 쿼리 실행 시 처리되므로 레코드 대상 건수가 많아질 수록 쿼리의 응답 속도가 느리다.

• 인덱스를 이용한 정렬은 앞서 B-Tree 인덱스의 정렬 및 스캔 방향에서 살펴 봤다.
• 다음과 같은 이유로 모든 정렬을 인덱스를 이용하도록 튜닝하기란 거의 불가능하다.
  • 정렬 기준이 너무 많아서 요건별로 모두 인덱스를 생성하는 것이 불가능한 경우
  • GROUP BY의 결과 또는 DISTINCT 같은 처리의 결과를 정렬해야 하는 경우
  • UNION의 결과와 같이 임시 테이블의 결과를 다시 정렬해야 하는 경우
  • 랜덤하게 결과 레코드를 가져와야 하는 경우

정렬 처리 수행 확인

• 실행 계획의 Extra 칼럼을 통해 MySQL 서버에서 인덱스를 이용하지 않고 별도의 정렬 처리를 수행했는지 판단할 수 있다.
  • “Using filesort” 메시지가 표시되는지 여부로 판단
• MySQL의 정렬 특성을 이해하면 쿼리를 튜닝할 때 어떻게 하면 조금이라도 더 빠른 쿼리가 될지 쉽게 판단할 수 있을 것이다.

소트 버퍼

• MySQL에서 정렬을 수행하기 위해 할당받은 별도의 메모리 공간을 소트 버퍼(Sort buffer)라고 한다.
• 소트 버퍼는 정렬이 필요한 경우에만 할당된다.
• 소트 버퍼의 크기는 정렬해야 할 레코드의 크기에 따라 가변적으로 증가한다.
• 최대 사용 가능한 소트 버퍼의 공간은 sort_buffer_size 시스템 변수로 설정할 수 있다.
• 소트 버퍼를 위한 메모리 공간은 쿼리의 실행이 완료되면 즉시 시스템으로 반납된다.

멀티 머지

• MySQL은 정렬해야 할 레코드를 여러 조각으로 나눠서 처리하는데, 이 과정에서 임시 저장을 위해 디스크를 사용한다.
  • 메모리의 소트 버퍼에서 정렬을 수행하고, 그 결과를 임시로 디스크에 기록해 둔다. 그리고 다음 레코드를 가져와서 다시 정렬해서 반복적으로 디스크에 임시 저장한다.
• 이처럼 각 버퍼 크기만큼 정렬된 레코드를 다시 병합하면서 정렬을 수행해야 하는데, 이 병합 작업을 멀티 머지(Multi-merge)라고 표현한다.
• 수행된 멀티 머지 횟수는 Sort_merge_passes 라는 상태 변수에 누적해서 집계된다.
  • SHOW STATUS VARIABLES 명령 참조

정렬의 문제

• 정렬해야 할 레코드가 아주 소량이어서 메모리에 할당된 소트 버퍼만으로 정렬할 수 있다면 아주 빠르게 정렬이 처리될 것이다.
• 하지만 정렬해야 할 레코드 건수가 소트 버퍼로 할당된 공간보다 크다면 다음과 같은 문제가 발생한다.
  • 멀티 머지의 작업들이 모두 디스크의 쓰기와 읽기를 유발하며, 레코드 건수가 많을 수록 이 반복 작업의 횟수가 많아진다.
  • 소트 버퍼를 크게 설정해도 실제 벤치마크 결과로는 큰 차이를 보이진 않는다.
• 일반적인 트랜잭션 처리용 MySQL 서버의 소트 버퍼 크기는 56KB에서 1KB 미만이 적절해 보인다.
• 소트 버퍼는 세션 메모리 영역에 해당하므로, 여러 클라이언트가 공유해서 사용할 수 있는 영역이 아니다.
  • 커넥션이 많을수록, 정렬 작업이 많을수록 소트 버퍼로 소비되는 메모리 공간이 커진다.
  • 소트 버퍼의 크기를 10BM 이상으로 설정하면 대량의 레코드를 정렬하는 쿼리가 여러 커넥션에서 동시에 실행되면서 운영체제가 메모리 부족 현상을 겪을 수도 있다.

정렬 알고리즘

• 레코드를 정렬할 때 레코드 전체를 소트 버퍼에 담을지 또는 정렬 기준 칼럼만 소트 버퍼에 담을지에 따라 “싱글 패스”와 “투 패스” 정렬 모드로 나눌 수 있다.
  • 공식적인 명칭은 아니다.

MySQL 서버의 정렬 방식

다음과 같이 3가지가 있다.

• <sort_key, rowid>
  • 투 패스 정렬 방식
  • 정렬 키와 레코드의 로우 아이디(Row ID)만 가져와서 정렬하는 방식
• <sort_key, additional_fields>
  • 싱글 패스 정렬 방식
  • 정렬 키와 레코드 전체를 가져와서 정렬하는 방식
  • 레코드의 칼럼들은 고정 사이즈로 메모리 저장
• <sort_key, packed_additional_fields>
  • 싱글 패스 정렬 방식
  • 정렬 키와 레코드 전체를 가져와서 정렬하는 방식
  • 레코드의 칼럼들은 가변 사이즈로 메모리 저장
  • MySQL 5.7 버전부터 정렬을 위한 메모리 공간의 효율적인 사용을 위해서 추가로 도입된 방식이다.

싱글 패스 정렬 방식

• 소트 버퍼에 정렬 기준 칼럼을 포함해 SELECT 대상이 되는 칼럼 전부를 담아서 정렬을 수행하는 정렬 방식
• 정렬이 완료되면 정렬 버퍼의 내용을 그대로 클라이언트로 넘겨준다.
• 최신 버전에서는 일반적으로 싱글 패스 정렬 방식을 주로 사용한다.
• 싱글 패스 정렬 방식은 더 많은 소트 버퍼 공간이 필요하다.
• 정렬 대상 레코드의 크기나 건수가 작은 경우 빠른 성능을 보인다.

투 패스 정렬 방식

• 정렬 대상 칼럼과 프라이머리 키 값만 소트 버퍼에 담아서 정렬을 수행하고, 정렬된 순서대로 다시 프라이머리 키로 테이블을 읽어서 SELECT할 칼럼을 가져오는 정렬 방식
• 싱글 패스 정렬 방식이 도입되기 전부터 사용하던 방식으로, MySQL 8.0에서도 여전히 특정 조건에서는 투 패스 정렬 방식을 사용한다.
  • 레코드의 크기가 max_length_for_sort_data 시스템 변수에 설정된 값보다 클 때
  • BLOB이나 TEXT 타입의 칼럼이 SELECT 대상에 포함될 때
• 테이블을 두 번 읽어야 하기 때문에 상당히 불합리하다.
• 정렬 대상 레코드의 크기나 건수가 상당히 많은 경우 효율적이다.

정렬 모드 확인하기

-- 옵티마이저 트레이스 활성화
SET OPTIMIZER_TRACE="enabled=on", END_MARKERS_IN_JSON=on;
SET OPTIMIZER_TRACE_MAX_MEM_SIZE=1000000;

-- // 쿼리 실행

-- 트레이스 내용 확인
SELECT * FROM INFORMATION_SCHEMA.OPTIMIZER_TRACE \G

• filesort_summary 섹션의 sort_algorithm 필드에 정렬 알고리즘이 표시된다.
• 또한 예제에선 sort_mode 필드에 <fized_sort_key, packed_additional_files> 가 표시된다.

정렬 처리 방법

정렬 처리 방법

• 쿼리에 ORDER BY가 사용되면 반드시 다음 3가지 처리 방법 중 하나로 정렬이 처리된다.
• 일반적으로 아래쪽에 있는 정렬 방법으로 갈수록 처리 속도는 떨어진다.

정렬 처리 방법	실행 계획의 Extra 칼럼 내용
인덱스를 사용한 정렬	별도 표기 없음
조인에서 드라이빙 테이블만 정렬	“Using filesort” 메시지가 표시됨
조인에서 조인 결과를 임시 테이블로 저장 후 정렬	“Using temporary; Using filesort” 메시지가 표시됨

옵티마이저의 정렬

먼저 옵티마이저는 정렬 처리를 위해 인덱스를 이용할 수 있을지 검토할 것이다.

• 인덱스를 이용할 수 있다면 별도의 “Filesort” 과정 없이 인덱스를 순서대로 읽어서 결과를 반환한다.
• 인덱스를 사용할 수 없다면 WHERE 조건에 일치하는 레코드를 검색해 정렬 버퍼에 저장하면서 정렬을 처리(Filesort)할 것이다.

이때, MySQL 옵티마이저는 정렬 대상 레코드를 최소화하기 위해 다음 2가지 방법 중 하나를 선택한다.

• 조인의 드라이빙 테이블만 정렬한 다음 조인을 수행
• 조인이 끝나고 일치하는 레코드를 모두 가져온 후 정렬을 수행

일반적으로 조인이 수행되면서 레코드 건수와 레코드의 크기는 거의 배수로 불어나기 때문에, 가능하다면 드라이빙 테이블만 정렬한 다음 조인을 수행하는 방법이 효율적이다.

인덱스를 이용한 정렬

• 인덱스를 이용한 정렬을 위해서는 반드시 다음 조건을 지켜야 한다.
  • ORDER BY에 명시된 칼럼이 제일 먼저 읽는 테이블(조인이 사용된 경우 드라이빙 테이블)에 속해야 한다.
  • ORDER BY의 순서대로 생성된 인덱스가 있어야 한다.
  • WHERE 절에 첫 번재로 읽는 테이블의 칼럼에 대한 조건이 있다면 그 조건과 ORDER BY는 같은 인덱스를 사용할 수 있어야 한다.
  • B-Tree 계열의 인덱스가 아닌 해시 인덱스나 전문 검색 인덱스 등에서는 인덱스를 이용한 정렬을 사용할 수 없다.
  • R-Tree는 특성상 이 방식을 사용할 수 없다.
  • 여러 테이블이 조인되는 경우에는 네스티드-루프(Nested-loop) 방식의 조인에서만 이 방식을 사용할 수 있다.
• 인덱스를 이용해 정렬이 처리되는 경우에는 실제 인덱스의 값이 정렬되어 있기 때문에, 인덱스의 순서대로 읽기만 하면 된다.
  • 실제로 MySQL 엔진에서 별도의 정렬을 위한 추가 작업을 수행하지는 않는다.
• 인덱스를 사용한 정렬이 가능한 이유는 B-Tree 인덱스가 키 값으로 정렬돼 있기 때문이다.
• 조인이 네스티드-루프 방식으로 실행되기 때문에 조인 때문에 드라이빙 테이블의 인덱스 읽기 순서가 흐트러지지 않는다.
  • 하지만 조인이 사용된 쿼리의 실행 계획에 조인 버퍼(Join buffer)가 사용되면 순서가 흐트러질 수 있기 때문에 주의해야 한다.

조인의 드라이빙 테이블만 정렬

• 조인을 실행하기 전에 첫 번째 테이블의 레코드를 먼저 정렬한 다음 조인을 실행한다.
• 조인에서 첫 번째로 읽히는 테이블(드라이빙 테이블)의 칼럼만으로 ORDER BY 절을 작성해야 한다.

임시 테이블을 이용한 정렬

• 2개 이상의 테이블을 조인해서 그 결과를 정렬해야 한다면 임시 테이블이 필요할 수 있다.

  • 다음 패턴이 아닌 쿼리에서는 항상 조인의 결과를 임시 테이블에 저장하고 그 결과를 다시 정렬하는 과정을 거친다.

    -- ORDER BY에 드라이빙 테이블의 칼럼 선언
    SELECT *
    FROM employees e, salaries s
    WHERE s.emp_no = s.emp_no
    	AND e.emp_no BETWEEN 100002 AND 10010
    ORDER BY e.last_name;

• 정렬의 3 가지 방법 중 정렬해야 할 레코드 건수가 가장 많기 때문에 가장 느린 정렬 방법이다.

정렬 처리 방법의 성능 비교

• 쿼리에서 인덱스를 사용하지 못하는 정렬이나 그루핑 작업이 왜 느리게 작동할 수밖에 없는지 살펴본다.
• 쿼리가 처리되는 방법을 다음 2가지로 구분한다.
  • 스트리밍 처리
  • 버퍼링 처리

스트리밍(Streaming) 방식

• 서버에서 처리할 데이터가 얼마인지에 관계없이 조건에 일치하는 레코드가 검색될 때마다 바로바로 클라이언트로 전송해주는 방식이다.
  • 클라이언트는 쿼리를 요청하고 곧바로 원했던 첫 번째 레코드를 전달받는다.
  • 가장 마지막 레코드는 언제 받을지 알 수 없다.
• 클라이언트는 MySQL 서버가 일치하는 레코드를 찾는 즉시 전달받기 때문에 동시에 데이터의 가공 작업을 시작할 수 있다.
• 쿼리가 얼마나 많은 레코드를 조회하느냐에 상관없이 빠른 응답 시간을 보장해준다.
• LIMIT처럼 결과 건수를 제한하는 조건들은 쿼리의 전체 실행 시간을 상당히 줄여줄 수 있다.
  • 전체적으로 가져오는 레코드 건수가 줄어들기 때문에 마지막 레코드를 가져오기까지의 시간을 상당히 줄일 수 있다.

버퍼링(Buffering) 방식

• ORDERY BY나 GROUP BY 같은 처리는 쿼리의 결과가 스트리밍되는 것을 불가능하게 한다.
  • WHERE 조건에 일치하는 모든 레코드를 가져온 후, 정렬하거나 그루핑해서 차례대로 보내야 하기 때문
• MySQL 서버에서는 모든 레코드를 검색하고 정렬 작업을 하는 동안 클라이언트는 아무것도 하지 않고 기다려야 하기 때문에 응답 속도가 느려진다. 따라서 이 방식을 스트리밍의 반대 표현으로 버퍼링이라고 표현해본 것이다.
• 버퍼링 방식으로 처리되는 쿼리는 먼저 결과를 모아서 MySQL 서버에서 일괄 가공해야 하므로 모든 결과를 스토리지 엔진으로부터 가져올 때까지 기다려야 한다.
• LIMIT처럼 결과 건수를 제한하는 조건이 있어도 성능 향상에 별로 도움이 되지 않는다.
  • 네트워크로 전송되는 레코드의 건수를 줄일 수는 있지만 MySQL 서버가 해야 하는 작업량에는 그다지 변화가 없다.

💡 JDBC는 기본으로 버퍼링 처리 방식이다.

정렬 처리 방법

• ORDER BY의 3가지 처리 방법 중 인덱스를 사용한 정렬 방식은 스트리밍 형태의 처리이며, 나머지는 모두 버퍼링된 후에 정렬된다.
• 즉, 인덱스를 사용한 정렬 방식은 LIMIT로 제한된 건수만큼만 읽으면서 바로바로 클라이언트로 결과를 전송해줄 수 있다.
• 인덱스를 사용하지 못하는 경우의 처리는 필요한 모든 레코드를 디스크로부터 읽어서 정렬한 후에야 비로소 LIMIT로 제한된 건수만큼 잘라서 클라이언트로 전송해줄 수 있다.
• 조인과 함께 ORDER BY절과 LIMIT절이 사용된 경우, 정렬 처리 방법별로 차이가 있다.
  • 어느 테이블이 먼저 드라이빙되어 조인되는지도 중요하지만 어떤 정렬 방식으로 처리되는지는 더 큰 성능 차이를 만든다.
  • 가능하다면 인덱스를 사용한 정렬로 유도하고, 그렇지 못하다면 최소한 드라이빙 테이블만 정렬해도 되는 수준으로 유도하는 것도 좋은 튜닝 방법이다.

정렬 관련 상태 변수

• MySQL 서버는 처리하는 주요 작업에 대해서는 해당 작업의 실행 횟수를 상태 변수로 저장한다.
• 정렬과 관련해서도 지금까지 몇 건의 레코드나 정렬 처리를 수행했는지, 소트 버퍼 간의 병합 작업(멀티 머지)은 몇 번이나 발생했는지 등을 확인해 볼 수 있다.

  FLUSH STATUS;
  SHOW STATUS LIKE 'Sort%';

  이 값들을 이용해 지금까지 MySQL 서버가 처리한 정렬 작업의 내용을 어느 정도 이해할 수 있다.
  

각 상태 값의 의미

• Sort_merge_passes
  • 멀티 머지 처리 횟수
• Sort_range
  • 인덱스 레인지 스캔을 통해 검색된 결과에 대한 정렬 작업 횟수
  • 정렬 작업 횟수를 누적하고 있다.
• Sort_scan
  • 풀 테이블 스캔을 통해 검색된 결과에 대한 정렬 작업 횟수
  • 정렬 작업 횟수를 누적하고 있다.
• Sort_rows
  • 지금까지 정렬한 전체 레코드 건수

Reference

참고 서적

📔 Real MySQL 8.0