정렬 ORDER BY

1. ORDER BY 처리

정렬을 처리하는 방법은 인덱스를 이용하는 방법과 쿼리가 실행될 때 'Filesort'라는 별도의 처리를 이용하는 방법이 있다.

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

이미 인덱스를 이용한 정렬은  B-Tree 인덱스의 정렬에서 한번 살펴봤다. 다음과 같은 이유로 모든 정렬을 인덱스를 이용하도록 튜닝하기란 불가능에 가깝다. 

• 정렬 기준이 너무 많아서 요건별로 모두 인덱스를 생성하는 것이 불가능한 경우
• GROUP BY의 결과 또는 DISTINCT 처리의 결과를 정렬해야 하는 경우
• UNION 결과와 같은 임시 테이블을 다시 정렬해야 하는 경우
• 랜덤하게 결과 레코드를 가져와야 하는 경우

MySQL은 인덱스를 이용해서 정렬할 수 없다면 Filesort를 이용한다.

 

2. 소트 버퍼

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

정렬해야 할 레코드가 소량이어서 메모리에 할당된 소트 버퍼만으로 정렬할 수 있다면 아주 빠르게 정렬이 처리될 것이다. 하지만 정렬해야 할 레코드 건수가 소트 버퍼 크기보다 크다면 MySQL은 정렬해야 할 레코드를 여러 조각으로 나눠서 처리하는데 이 과정에서 임시 저장을 위해 디스크를 사용한다. 

메모리의 소트 버퍼에서 정렬을 수행하고, 그 결과를 임시로 디스크에 기록해 둔다. 그리고 다음 레코드를 가져와서 다시 정렬해서 디스크에 임시 저장한다. 이처럼 각 버퍼 크기만큼 정렬된 레코드를 다시 병합하면서 정렬을 수행해야 한다. 이 병합 작업을 멀티 머지(Multi-merge)라고 표현하며 수행된 멀티 머지 횟수는 sort_merge_passes라는 상태 병수에 누적해서 집계된다. 아래 쿼리로 확인할 수 있다.

-- sort_merge_passes 값 확인
SHOW GLOBAL STATUS LIKE 'sort_merge_passes';
SHOW SESSION STATUS LIKE 'sort_merge_passes';

-- sort_buffer_size 값 확인
SHOW VARIABLES WHERE variable_name LIKE 'sort%';

이 작업들이 모두 디스크 I/O 유발하며 레코드 건수가 많을수록 이 반복 작업의 횟수가 많아진다.  MySQL의 소트 버퍼는 세션 메모리 영역에 해당하므로 커넥션 별로 메모리 공간이 할당된다. 즉, 커넥션이 많을수록, 정렬 작업이 많을수록 소트 버퍼로 소비되는 메모리 공간이 커진다. 소트 버퍼의 크기를 크게하고 대량의 레코드를 정렬하는 쿼리가 여러 커넥션에서 동시에 실행되면 운영체제는 메모리 부족 현상을 겪을 수 있다. 그러면 운영체제는 메모리를 가장 많이 사용하는 프로세스를 강제 종료할 수 있는데 MySQL 서버가 강제 종료 1순위가 될 확률이 높다. 일반적인 트랜잭션 처리용 MySQL 서버의 소트 버퍼 크기는 56KB에서 1MB미만이 적절하다. 

MySQL 서버에 데이터가 많거나 디스크 I/O 성능이 낮은 장비라면 소트 버퍼의 크기를 적당히 더 크게 설정하는 것이 도움이 될 수도 있지만 너무 많이 할당하면 오히려 메모리 부족 현상으로 독이 될 수도 있다. 대량 데이터의 정렬이 필요한 경우 해당 세션의 소트 버퍼만 일시적으로 늘려서 쿼리를 실행하고 다시 줄이는 것도 좋은 방법이다.

 

3. 정렬 알고리즘

레코드를 정렬할 때 레코드 정보를 소트 버퍼에 저장하는 방식에 따라 2가지 정렬 모드로 구분할 수 있다.

• A case: 레코드 전체를 저장한다.
• B case: 정렬 기준 컬럼과 PK만 저장한다.

정렬을 수행하는 쿼리가 어떤 정렬 모드를 사용하는지 다음과 같이 옵티마이저 트레이스 기능으로 확인할 수 있다.

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

-- 쿼리 실행
SELECT * FROM employees 
 ORDER BY last_name LIMIT 100000, 1;

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

트레이스 내용 확인 쿼리에서 TRACE 컬럼에 내용 중 

    {
    	"sorting_table": "employees",
    	"filesort_information": [
            {
                "direction": "asc",
                "expression": "`employees`.`last_name`"
            }
    	] /* filesort_information */,
    	"filesort_priority_queue_optimization": {
    		"limit": 100001
    	} /* filesort_priority_queue_optimization */,
    	"filesort_execution": [
    	] /* filesort_execution */,
    	"filesort_summary": {
            "memory_available": 262144,
            "key_size": 32,
            "row_size": 169,
            "max_rows_per_buffer": 1551,
            "num_rows_estimate": 299920,
            "num_rows_found": 300024,
            "num_initial_chunks_spilled_to_disk": 86,
            "peak_memory_used": 276528,
            "sort_algorithm": "std::stable_sort",
            "sort_mode": "<fixed_sort_key, packed_additional_fields>"
    	} /* filesort_summary */
    }

"sort_mode" 필드가 A case, B case를 나타낸다.

A case	<sort_key, additional_fields>	정렬 키와 레코드 전체를 정렬, 레코드의 칼럼들은 고정 사이즈로 저장
	<sort_key, packed_additional_fields>	정렬 키와 레코드 전체를 정렬, 레코드의 칼럼들은 가변 사이즈로 저장
B case	<sort_key, rowid>	정렬 키와 PK값만을 정렬

"sort_algorithm" 필드에 보여진 "std::stable_sort"는 MySQL 서버에서 실제 정렬을 수행할 때 사용한 라이브러리의 함수 이름을 보여준다.

A case는 소트 버퍼에 정렬 기준 칼럼을 포함해 SELECT 대상이 되는 컬럼 전부를 담아서 정렬을 수행하는 정렬 방식이다.

SELECT emp_no, first_name, last_name
  FROM employees
 ORDER BY first_name;

위 쿼리는 employees 테이블을 읽을 때 정렬에 필요하지 않은 last_name칼럼까지 전부 읽어서 소트 버퍼에 담고 정렬을 수행한다. 그리고 정렬이 완료되면 소트 버퍼의 내용을 그대로 클라이언트로 넘겨준다. 

B case는 정렬 대상 컬럼과 PK값만 소트 버퍼에 담아서 정렬을 수행하고 정렬된 순서대로 다시 PK로 테이블을 읽어서 SELECT할 컬럼을 가져오는 정렬 방식으로, A case 방식이 도입되기 전에 사용하던 방식이다. MySQL 8.0 에서도 특정 조건에서는 B case 방식을 사용한다. B case 방식은 테이블을 두 번 읽어야 하기 때문에 상당히 불합리하지만 소트 버퍼 공간은 A case에 비해 적게 사용한다. 

최신 버전에서는 주로 A case 방식으로 정렬을 하지만 다음의 경우 B case 방식을 사용한다. 

• 레코드의 크기가 max_length_for_sort_data 시스템 변수에 설정된 값보다 클 때
• BLOB, TEXT 타입의 컬럼이 SELECT 대상에 포함할 때

A case는 정렬 대상 레코드의 크기나 건수가 작은 경우 빠른 성능을 보이며, B case는 정렬 대상 레코드의 크기나 건수가 상당히 많은 경우 효율적이다. 그래서 SELECT를 할 때는 정렬 여부에 상관없이 애스터리스트 (*) 사용을 자제하고 꼭 필요한 컬럼만 가져오게 하는 것이 성능상 유리하다.

 

4. 정렬 처리 방법

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

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

옵티마이저는 정렬 처리를 위해 인덱스를 이용할 수 있다면 인덱스를 이용하고 이용할 수 없다면 WHERE 조건에 일치하는 레코드를 검색해 소트 버퍼에 저장하면서 정렬을 처리한다. (Filesort) 이때 MySQL 옵티마이저는 정렬 대상 레코드를 최소화하기 위해 다음 2가지 방법 중 하나를 선택한다.

1. 조인의 드라이빙 테이블만 정렬한 다음 조인을 수행 (효율적)
2. 조인이 끝나고 일치하는 레코드를 모두 가져온 후 정렬을 수행

 

4.1 인덱스를 이용한 정렬

반드시 ORDER BY에 명시된 컬럼이 제일 먼저 읽는 테이블 (드라이빙 테이블)에 속하고 ORDER BY의 순서대로 생성된 인덱스가 있어야 한다. 또한 WHERE 절에 드라이빙 테이블의 컬럼에 대한 조건이 있다면 ORDER BY와 같은 인덱스를 사용할 수 있어야 한다. 여러 테이블이 조인되는 경우에는 Nested Loops Join 때만 인덱스를 이용하여 정렬을 할 수 있다.

중첩 루프 조인 (Nested Loops Join) 이란? 반복문 여러 개가 겹쳐 있는 구조를 중첩 루프라고 합니다. 드라이빙 테이블(Driving Table, Outer Table)에서 레코드가 추출될 때마다 드리븐 테이블(Driven Table, Inner Table)의 연관된 모든 레코드를 조인으로 액세스하는 것을 의미한다. 드라이빙 테이블의 레코드가 드리븐 테이블보다 작고 드라이빙 테이블, 드리븐 테이블 연결 컬럼에 인덱스가 있을 때 가장 효율이 좋습니다.

인덱스는 이미 정렬이 되어 있기 때문에 인덱스의 순서대로 읽기만 하면 된다. 다음 쿼리를 살펴보자.

-- SELECT (3)
SELECT *
  FROM employees E
 INNER JOIN salaries S
    ON E.emp_no = S.emp_no
 WHERE e.emp_no BETWEEN 100002 AND 100020
 ORDER BY e.emp_no;
 
 
 -- SELECT (4)
SELECT *
  FROM employees E
 INNER JOIN salaries S
    ON E.emp_no = S.emp_no
 WHERE e.emp_no BETWEEN 100002 AND 100020;

select (3), (4)의 차이는 ORDER BY 절의 사용 여부인데 쿼리의 출력은 같다. ORDER BY 절이 없어도 정렬이 되는 이유는 employees 테이블의 PK를 읽고 그다음 salaries 테이블을 조인했기 때문이다. ORDER BY 절이 없이 정렬이 된다고 하더라도 정렬이 필요하다면 꼭 ORDER BY 절을 추가해야 한다. 위와 같은 경우 SELECT(3)은 ORDER BY 절이 추가된다고  부가적으로 불필요한 정렬 작업을 수행하지 않는다. SELECT (4)와 작업량은 같다.

 

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

일반적으로 조인이 수행되면 결과 레코드의 건수가 몇 배로 늘어날 수 있고 레코드의 크기도 늘어날 수 있다. 그래서 조인을 실행하기 전에 첫 번째 테이블의 레코드를 먼저 정렬한 다음 조인을 실행하면 효율적으로 처리할 수 있다. 이 방법으로 정렬을 처리하려면 조인에서 첫 번째로 읽히는 테이블(드라이빙 테이블)의 칼럼만으로 ORDER BY 절을 작성해야 한다.

SELECT *
  FROM employees E
 INNER JOIN salaries S
    ON E.emp_no = S.emp_no
 WHERE E.emp_no BETWEEN 100002 AND 100010
 ORDER BY E.last_name;

WHERE 절이 다음 2가지 조건을 갖추고 있기 때문에 옵티마이저는 employees 테이블을 드라이빙 테이블로 선택한다.

1. WHERE 절의 검색 조건은 employees 테이블의 PK를 이용해 검색하면 레코드 건수를 줄일 수 있다.
2. 드리븐 테이블(salaries)의 조인 컬럼인 emp_no 컬럼에 인덱스가 생성되어 있다.

last_name은 PK와 인덱스에 아무런 연관이 없으므로 인덱스를 이용한 정렬은 불가능하다. 하지만 옵티마이저는  last_name이 드라이빙 테이블(employees)에 포함된 컬럼이라는 것을 알기 때문에 드라이빙 테이블만 먼저 정렬하고 그 결과와 salaries 테이블을 조인한다.

 

그림 (1) 조인의 첫 번째(드라이빙) 테이블만 정렬 실행

 

그림 (1)은 다음 과정을 보여준다.

1. PK 인덱스를 이용해 "emp_no BETWEEN 100002 AND 100010" 조건을 만족하는 레코드 9건을 검색
2. 검색 결과를 소트 버퍼에 저장하고 last_name 컬럼을 기준으로 정렬을 수행 (Filesort)
3. 소트 버퍼의 정렬된 결과를 순서대로 읽으면서 salaries 테이블과 조인을 수행해 레코드 86건의 최종 결과를 출력

 

4.3 임시 테이블을 이용한 정렬

쿼리가 단일 테이블의 결과를 정렬할 때는 임시 테이블이 필요하지 않는다. 하지만 2개 이상의 테이블을 조인할 때는 경우에 따라 임시 테이블이 필요할 수 있다. 6.2 조인의 드라이빙 테이블만 정렬의 경우를 제외한 조인은 모두 임시 테이블을 사용한다. 임시 테이블을 이용한 정렬은 3가지 방법 중 정렬해야 할 레코드 건수가 가장 많기 때문에 가장 느린 정렬 방법이다. 다음 쿼리를 살펴보자.

-- SELECT (5)
SELECT *
  FROM employees E
 INNER JOIN salaries S
    ON E.emp_no = S.emp_no
 WHERE E.emp_no BETWEEN 100002 AND 100010
 ORDER BY S.salary;

위 쿼리도 employees 테이블이 드라이빙 테이블로 사용되며 salaries 테이블이 드리븐 테이블이 된다. 이번 쿼리에서 ORDER BY 절의 정렬 기준 칼럼이 드라이빙 테이블이 아니라 드리븐 테이블에 있는 칼럼이다. 즉 정렬이 수행되기 전에 salaries 테이블을 읽어야 하므로 이 쿼리는 조인된 데이터를 가지고 정렬할 수밖에 없다.
쿼리 실행 계획을 보면 Extra 컬럼에 "Using Temporary; Using filesort"가 표시된다. 이는 조인의 결과를 임시 테이블에 저장하고 그 결과를 다시 정렬 처리했음을 의미한다. 아래 그림 (2)는 이 쿼리의 처리 절차를 보여준다.

 

그림 (2) 임시 테이블을 이용한 정렬

 

 

4.4 정렬 처리 방법의 성능 비교

주로 웹 서비스용 쿼리에서는 ORDER BY와 LIMIT이 거의 필수로 사용되는 경향이 있다. 일반적으로 LIMIT은 레코드의 일부만 가져오기 때문에 MySQL 서버가 처리해야 할 작업량을 죽이는 역할을 한다. 그런데 ORDER BY나 GROUP BY 같은 작업은 WHERE 조건을 만족하는 레코드를 LIMIT 건수만큼만 가져와서는 처리할 수 없다. 우선 WHERE 조건을 만족하는 레코드를 모두 가져와서 정렬을 수행하거나 그루핑 작업을 실행해야만 비로소 LIMIT으로 건수를 제한할 수 있다. WHERE 조건이 아무리 인덱스를 잘 활용하도록 튜닝해도 잘못된 ORDER BY나 GROUP BY 때문에 쿼리가 느려지는 경우가 많은 이유가 이것 때문이다. 

 

4.4.1 스트리밍 방식

서버쪽에서 처리할 데이터의 크기에 상관없이 조건에 일치하는 레코드가 검색될 때마다 바로바로 클라이언트로 레코드를 전송해주는 방식을 의미한다. 이 방식으로 쿼리를 처리할 경우 클라이언트는 쿼리를 요청하고 곧바로 원했던 첫 번째 레코드를 전달받는다. 물론 가장 마지막 레코드는 언제받을지 알 수 없다.
쿼리가 스트리밍 방식으로 처리될 수 있다면 클라이언트는 MySQL 서버가 일치하는 레코드를 찾는 즉시 전달받기 때문에 동시에 데이터의 가공 작업을 시작할 수 있다. 웹 서비스 같은 OLTP 환경에서는 쿼리의 요청에서부터 첫 번째 레코드를 전달받게 되기까지의 응답 시간이 중요하다. 스트리밍 방식으로 처리되는 쿼리는 레코드 수에 상관없이 빠른 응답 시간을 보장해준다. 이것은 풀 테이블 스캔의 결과가 아무런 버퍼링 처리나 필터링 과정 없이 바로 클라이언트로 스트리밍되기 때문이다.  또한 스트리밍 방식으로 처리되는 쿼리에서 LIMIT처럼 건수를 제한하는 조건들은 쿼리의 전체 실행 시간을 상당히 줄여줄 수 있다. MySQL은 스트리밍 방식으로 데이터를 전달하여도 클라이언트에서 버퍼링 방식으로 처리를 할 수도 있다. 대표적인 경우가 JDBC이다. 즉, JDBC는 MySQL 서버로부터 받는 레코드를 일단 내부 버퍼에 모두 담아둔다. 그리고 마지막 레코드가 전달되면 그때서야 클라이언트의 애플리케이션(웹서버)측에 전달한다. JDBC은 기본적으로 버퍼링 방식으로 처리하지만 아주 대량의 데이터를 가져와야 할 때는 MySQL 서버와 JDBC 간의 전송 방식을 스트리밍 방식으로 변경할 수 있다.

 

4.4.2 버퍼링 방식

ORDER BY나 GROUP BY 같은 쿼리는 스트리밍 방식으로 처리할 수 없다. 왜냐하면 모든 레코드를 읽은 후 작업이 가능하기 때문에 클라이언트는 작업이 마칠 때까지 기다려야 하기 때문에 응답 속도가 느리다. 우선 WHERE 조건에 일치하는 모든 레코드를 가져온 후, 정렬하거나 그루핑해서 차례대로 보내야 한다. 그래서 LIMIT처럼 결과 건수를 제한하는 조건이 있어도 성능 향상에 크게 도움되지는 않는다. 
6.3 정렬 처리 방법 중 인덱스를 사용한 정렬 방식만 스트리밍 형태의 처리이며 나머지는 모두 버퍼링된 후에 정렬된다. 

조인과 함께 ORDER BY절과 LIMIT 절이 사용될 경우 정렬 처리 방법별로 어떤 차이가 있는지 살펴보자.

/*  
    tb_test1 테이블의 레코드 수:   100건
    tb_test2 테이블의 레코드 수: 1,000건
    
    tb_test1 레코드 1건 당 tb_test2 레코드 10건씩 존재한다고 가정
    두 테이블의 조인 결과는 전체 1,000건이라고 가정
*/
SELECT *
  FROM tb_test1 A
 INNER JOIN tb_test2 B
    ON A.col1 = B.col1
 ORDER BY A.col2
 LIMIT 10;

 

tb_test1이 드라이빙 테이블인 경우 

정렬 방법	읽어야 할 건수	조인 횟수	정렬해야 할 대상 건수
인덱스 사용	tb_test1:        1건 tb_test2:      10건	1번	0건
조인의 드라이빙 테이블만 정렬	tb_test1:    100건 tb_test2:      10건	1번	100건 (tb_test1 테이블의 레코드 건수만큼 정렬 필요)
임시 테이블 사용 후 정렬	tb_test1:    100건 tb_test2: 1,000건	100번 (tb_test1 테이블의 레코드 건수만큼 조인 발생)	1,000건 (조인된 결과 레코드 건수를 전부 정렬해야 함)

tb_test2이 드라이빙 테이블인 경우 

정렬 방법	읽어야 할 건수	조인 횟수	정렬해야 할 대상 건수
인덱스 사용	tb_test1:      10건 tb_test2:      10건	10번	0건
조인의 드라이빙 테이블만 정렬	tb_test1:      10건 tb_test2: 1,000건	10번	1,000건 (100 * 10) (tb_test2 테이블의 레코드 건수만큼 정렬 필요)
임시 테이블 사용 후 정렬	tb_test1:    100건 tb_test2: 1,000건	1,000번 (tb_test2 테이블의 레코드 건수만큼 조인 발생)	1,000건 (조인된 결과 레코드 건수를 전부 정렬해야 함)

어느 테이블이 드라이빙 테이블이 되는지도 중요하지만 어떤 정렬 방식으로 처리되는지는 더 큰 성능 차이를 만든다. 가능하다면 인덱스를 사용한 정렬로 유도하고 차선책으로 드라이빙 테이블만 정렬로 정렬이 될 수 있도록 튜닝하는 것이 좋다.

 

4.4.3 정렬 관련 상태 변수

정렬과 관련해서 지금까지 몇 건의 레코드나 정렬 처리를 수행했는지 소트 버퍼에서 병합 작업(멀티 머지)은 몇 번이나 발생했는지 등을 다음 명령으로 확인할 수 있다.

FLUSH STATUS; -- 버퍼, 캐시에 있는 명령들을 모두 적용
SHOW STATUS LIKE 'Sort%';

Variable 의미

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

쿼리를 실행하기 전 해당 Variable 횟수를 확인한다. 그리고 쿼리를 실행 후 변화된 값을 확인하는 용도로 많이 사용된다.