MySQL/MariaDB Single-pass, Two-pass Sort Algorithm

MySQL/MariaDB Single-pass, Two-pass Sort Algorithm

 

·       Version : MySQL 5.X Later,  MariaDB 5.X Later

 

MySQL/MariaDB에서는 정렬 알고리즘으로Single-pass 와 Two-pass  알고리즘을 사용한다. 그리고 정렬처리 방식으로 인덱스를 사용한 방식과 테이블을 사용하여 정렬하는 방식이 있다.

 

Single-pass 알고리즘은 Sort Buffer에 정렬 기준 칼럼을 포함한 SELECT에 포함된 컬럼의 데이터를 버퍼 메모리에 담아서 정렬을 수행하는 방식이다. Two-pass 알고리즘은 정렬 컬럼과  프라이머리 키 값만 Sort buffer에 담아서 정렬을 수행하고, 정렬된 순서대로 다시 프라이머리키로 테이블을 읽어서 SELECT 에 포함된 컬럼의 데이터를 가져오는 방식이다. Two-pass 알고리즘은 같은 테이블을 2번 읽어야 하기 때문에 매우 불합리해 보일 수 있으나, Sing-pass 알고리즘은 더 많은 소트 버퍼의 공간이 필요하다.

 

MySQL 5.0 및 MariaDB 5.X 버전부터는새로운 정렬 알고리즘은 Single-pass 방식이 사용되지만 아래와 같은 경우에는 Two-pass 알고리즘이 사용된다.

·       레코드의 크기가 max_length_for_sort_data 파라미터로 설정된 값보다 클 때

·       BLOB 이나 TEXT 타입의 컬럼이 SELECT 대상에 포함될때

 

싱글패스 알고리즘은 정렬 대상 건수가 작을때 빠른 성능을 보이며, 투 패스 알고리즘은 데이터 레코드의 건수가 많을 때 효율적이다. 쿼리에 ORDER BY가 사용되면 정렬을 하기 위해 아래 3가지 방식중 하나로 처리 된다. 옵티마이저는 가장 먼저 인덱스를 이용할 수 있을지 검토하고, 인덱스가 없을 경우 조건에 일치하는 레코드를 검색하여 버퍼에 저장하면서 정렬을 처리(Filesort)한다.

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

 

하나의 테이블로부터 SELECT해서 정렬을 하는 경우라면 임시 테이블이 필요하지 않다. 하지만 2개 이상의 테이블을 조인해서 그 결과를 정렬해야한다면 임시 테이블이 필요할 수도 있다. 드라이빙 테이블만 정렬된 경우에는 임시 테이블을 사용하지 않는다.

 

 

 

2019-09-20 / 강성욱 / http://sungwookkang.com

 

MySQL, MariaDB, Sort Buffer, Single-pass, Two-pass , Filesort