정렬 알고리즘 - Githubissues

hyeonic commented 2 years ago

주제

레코드를 정렬할 때 레코드 전체를 소트 버퍼에 담을지 또는 정렬 기준 칼럼만 소트 버퍼에 담을지에 따라 "싱글 패스(Single-pass)"와 "투 패스(Two-pass)" 2가지 정렬 모드로 나눌 수 있다. 두 가지 정렬 모드에 대해 간단히 알아보자.

선정 이유

모든 칼럼을 가져오도록 개발하는 것이 좋지 않다는 이야기를 종종 들었다. 이에 대한 이유들을 알아보려 한다.

해당 텍스트

싱글 패스 정렬 방식

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

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

first_name으로 정렬해서 emp_no, first_name, last_name을 SELECT 하는 쿼리를 싱글 패스 정렬 방식으로 처리하는 그림은 아래와 같다.

처음 employees 테이블을 읽을 때 정렬에 필요하지 않은 last_name 칼럼까지 전부 읽어 소트 버퍼에 담고 정렬한다.

투 패스 정렬 방식

정렬 대상 칼럼과 프라이머리 키 값만 소트 버퍼에 담아서 정렬을 수행하고 정렬된 순서대로 다시 프라이머리 키로 테이블을 읽어서 SELECT할 칼럼을 가져오는 정렬 방식이다.

employees 테이블을 읽을 때 정렬이 필요한 first_name 칼럼과 프라이머리 키인 emp_no만 읽어서 정렬을 수행한 것을 확인할 수 있다. 정렬이 완료되면 그 결과 순서대로 employees 테이블을 한 번 더 읽어서 last_name을 가져오고 결과를 클라이언트로 전달한다.

비교하기

투 패스 방식은 테이블을 두 번 읽어야만 온전한 결과를 확인할 수 있다.
싱글 패스 방식의 경우 한 번의 쿼리만으로 결과를 확인할 수 있다. 하지만 소트 버퍼의 공간이 더 필요하게 된다.

최신 버전에서는 싱글 패스 정렬 방식을 주로 활용한다. 하지만 아래와 같은 특정한 경우에 MySQL 서버는 싱글 패스 정렬 방식을 사용하지 않고 투 패스 정렬 방식을 사용한다.

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

주의할 점

투 패스 정렬 방식이 더 빠를 수 있지만 항상 그런 것은 아니다. 싱글 패스 방식은 정렬 대상 레코드의 크기나 건수가 작은 경우 빠른 성능을 보이며 투 패스 방식은 정렬 대상 레코드의 크기나 건수가 상당히 많은 경우 효율적이다.

우리는 때때로 SELECT를 활용할 때 (*)을 활용하곤 한다. 이것은 정렬 버퍼를 몇 배에서 몇 십배 까지 비효율적으로 사용할 가능성이 크다. 특히 정렬이 필요한 SELECT는 불필요한 칼럼을 SELECT 하지 않게 쿼리를 작성하는 것이 효율적이다.

woowacourse-study / 2022-Real-MySQL

정렬 알고리즘 #20

주제