Nested Loop

Nested Loop는 조인 알고리즘의 하나로 중첩 조인이라고도 합니다.
중첩 조인에서는 어떤 테이블에 먼저 접근하는지가 성능에 있어 중요하게 작용합니다.
우선 용어를 정리하자면, Join이 대상이 되는 테이블 중 먼저 접근하는 테이블을 드라이빙 테이블, 이후에 접근하는 테이블을 드리븐 테이블이라고 합니다.

중첩 조인의 작동 방식은 다음과 같습니다.
1. 쿼리에 포함된 조건절에 따라 드라이빙 테이블을 필터링 합니다.
2. 필터링 된 드라이빙 테이블의 한 행당 드리븐 테이블을 탐색해 매치되는 행을 찾습니다. (인덱스가 없다면 풀 테이블 스캔, 있다면 인덱스 스캔을 합니다.)
3. 드라이빙 테이블의 모든 행에 대해 반복합니다.
4. 공통된 데이터를 출력합니다.
이런 로직을 따르기 때문에, 먼저 접근되는 드라이빙 테이블의 행 수가 적을수록 유리합니다. 행의 갯수만큼 드리븐 테이블에 접근하기 때문입니다.
따라서 조건절의 결과로 반환되는 행의 갯수가 더 적은 테이블에 가장 먼저 접근하는 것이 조인시 유리합니다.

문제 쿼리

    private async findUserDogJournalsByDate(
        userId: number,
        dogId: number,
        startDate: Date,
        endDate: Date,
    ): Promise<Journals[]> {
        return await this.entityManager
            .createQueryBuilder(Journals, 'journals')
            .innerJoin(JournalsDogs, 'journals_dogs', 'journals.id = journals_dogs.journal_id')
            .where('journals.user_id = :userId', { userId })
            .andWhere('journals_dogs.dog_id = :dogId', { dogId })
            .andWhere('journals.started_at >= :startDate', { startDate })
            .andWhere('journals.started_at < :endDate', { endDate })
            .getMany();
    }

SELECT  distance, duration, started_at FROM journals
INNER JOIN journals_dogs ON journals.id = journals_dogs.journal_id
WHERE journals.user_id = 1 AND journals_dogs.dog_id = 1
AND journals.started_at >= "2024-06-30T15:00:00.000Z" AND journals.started_at < "2024-07-31T14:59:59.999Z";

산책 일지를 담고 있는 journals 테이블과, 관계형 테이블 journals_dogs 테이블을 조인해 user_id = 1, dog_id = 1이며 한달 날짜 기준에 부합하는 산책일지를 리턴하는 쿼리입니다.

이 쿼리의 실행 계획중 JOIN과 관련된 부분만 살펴보겠습니다.

id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	journals_dogs		ref	PRIMARY,FK_65d6e1349dda45ff53bc0d865af	FK_65d6e1349dda45ff53bc0d865af	4	const	1011	100.0	Using index
1	SIMPLE	journals		eq_ref	PRIMARY,FK_dcd8f26897887ea1ca19e9b910a	PRIMARY	4	performance.journals_dogs.journal_id	1	5.0	Using where

• 실행 계획의 첫번째에 오는 테이블이 보통 드라이빙 테이블(먼저 접근하는 테이블)입니다.
• id는 실행 순서를 표시하는 숫자로 조인 시에는 같은 id가 표시됩니다.
• type : 테이블의 데이터를 어떻게 찾을지에 관한 정보를 제공하는 항목입니다. 테이블을 처음부터 끝까지 전부 확인할지, 아니면 인덱스를 통해 바로 데이터를 찾아갈지 등을 해석할 수 있습니다.
  • ref: 테이블 검색 시 조건에 해당하는 데이터가 2개 이상 존재하는 경우입니다. 이 경우 dog_id = 1인 데이터가 jouanals_dogs 테이블에 여러 건 존재하기에 ref가 사용됩니다.
  • eq_ref: 테이블 검색 시 고유 인덱스 또는 기본 키로 단 1건의 데이터를 조회한다는 뜻입니다. 이 경우에는 journals_dogs와 journals 사이 조인이 수행될 때 조인 조건이 PK 등으로 유니크하다는 뜻입니다.
• ref: reference의 약자로, 테이블에 접근할 때 어떤 조건으로 해당 테이블에 액세스 되었는지를 알려주는 정보입니다. jouanls_dogs 테이블과 journal 테이블 조인시 journal_id가 사용되었음을 알 수 있습니다.
• rows: SQL문을 수행하고자 접근하는 데이터의 모든 행row 수를 나타내는 예측 항목입니다.
  • journals_dogs 테이블에 1011 행이 리턴될 것으로 보고 있습니다.
• filtered: SQL문을 통해 DB엔진으로 가져온 데이터 대상으로 필터 조건에 따라 어느 정도의 비율로 데이터를 제거했는지를 의미하는 항목입니다.
  • 여기서는 5%로, 1011 행에 대해 5퍼센트 필터링해 51행이 출력될 것으로 예상하고 있습니다.
• extra: 부가적인 정보입니다.
  • Using where : WHERE 절의 필터 조건을 사용해 MySQL 엔진으로 가져온 데이터를 추출할 것이라는 의미입니다. 여기서는 journals_dogs와 journals 테이블을 jouanr_id가 같은 행만 남도록 JOIN한 뒤, 이 JOIN의 결과에 대해 user_id =1, dog_id = 1, started_at이 (현지 시간 기준으로)7월에 해당하는 행만 남기고 필터링을 한다는 뜻입니다.

설명이 길었지만, 핵심적인 정보는 journals_dogs 테이블이 드라이빙 테이블, journals 테이블이 드리븐 테이블이라는 것입니다.
그런데 ERD 설계상 한 강아지가 여러 주인을 가질 수 있기 때문에,
위와 같은 조건 하에서는 필연적으로 journals_dogs의 결과 행이 더 많을 수밖에 없습니다.
journals 테이블에 먼저 액세스하도록, 즉 journals 테이블을 드라이빙 테이블로 만들면 효율이 더 높아질 것으로 보입니다.

해결

이 문제를 해결하기 위해서는 JOIN의 순서를 명시적으로 지정해줘야 합니다.
STRAIGHT JOIN 구문을 사용하면 FROM 절에 명시된 대로 JOIN 되도록 순서를 지정할 수 있습니다.

SELECT STRAIGHT_JOIN  journals.distance, journals.duration, journals.started_at FROM journals
INNER JOIN journals_dogs ON journals.id = journals_dogs.journal_id
WHERE journals.user_id = 1 AND journals_dogs.dog_id = 1
AND journals.started_at >= "2024-06-30T15:00:00.000Z" AND journals.started_at < "2024-07-31T14:59:59.999Z";

id	select_type	table	partitions	type	possible_keys	key
1	SIMPLE	journals		ref	PRIMARY,FK_dcd8f26897887ea1ca19e9b910a	FK_dcd8f26897887ea1ca19e9b910a
1	SIMPLE	journals_dogs		eq_ref	PRIMARY,FK_65d6e1349dda45ff53bc0d865af	PRIMARY

• journals 테이블이 1행, journals_dogs 테이블이 2행으로 순서가 바뀌어 표시됩니다. journals 테이블이 드라이브 테이블로 사용됨을 알 수 있습니다.

코드로 표현시 TypeORM은 STRAIGHT_JOIN 구문을 지원하지 않아 Raw 쿼리의 사용이 필요합니다.

    private async findUserDogJournalsByDate(
        userId: number,
        dogId: number,
        startDate: Date,
        endDate: Date,
    ): Promise<DogWalkJournalEntry[]> {
        return await this.entityManager.query(
            `
        SELECT STRAIGHT_JOIN journals.distance, journals.duration, journals.started_at as startedAt 
        FROM journals 
        INNER JOIN journals_dogs ON journals.id = journals_dogs.journal_id
        WHERE journals.user_id = ?
          AND journals_dogs.dog_id = ?
          AND journals.started_at >= ?
          AND journals.started_at < ?
      `,
            [userId, dogId, startDate, endDate],
        );
    }

쿼리 빌더의 SELECT 인자 배열 첫번째 요소를 'STRAIGHT_JOIN journlas.distance' 로 주어 자연스럽게 STRAIGHT_JOIN이 맨 앞에 가는 방법을 시도해보았지만, 배열의 첫번째 요소로 넣어도 실제로는 항상 두번째 컬럼으로 실행되어 실패했습니다.
.addSelect()로 체이닝 하는 방법도 써봤지만 이 방법 역시 순서를 보장하지 않아 Raw 쿼리 외에는 현재로서 방법이 없는 것 같습니다.

개선 결과

전

-> Nested loop inner join  (cost=457 rows=50.6) (actual time=0.137..6.65 rows=31 loops=1)
    -> Covering index lookup on journals_dogs using FK_65d6e1349dda45ff53bc0d865af (dog_id=1)  (cost=104 rows=1011) (actual time=0.08..0.919 rows=1011 loops=1)
    -> Filter: ((journals.user_id = 1) and (journals.started_at >= TIMESTAMP'2024-06-30 15:00:00') and (journals.started_at < TIMESTAMP'2024-07-31 14:59:59.999'))  (cost=0.25 rows=0.05) (actual time=0.00535..0.00538 rows=0.0307 loops=1011)
        -> Single-row index lookup on journals using PRIMARY (id=journals_dogs.journal_id)  (cost=0.25 rows=1) (actual time=0.00456..0.00462 rows=1 loops=1011)

• Single-row index lookup on journals using PRIMARY (id=journals_dogs.journal_id) (cost=0.25 rows=1) (actual time=0.00456..0.00462 rows=1 loops=1011) 이 부분이 journals_dogs 테이블과 journals 간 중첩 조인을 수행하는 부분입니다. journals_dogs 테이블에 먼저 접근해 반환된 1011개의 행으로 journals 테이블에 접근하고 있어, 1011번 루프가 실행됨을 알 수 있습니다.

후

-> Nested loop inner join  (cost=307 rows=114) (actual time=0.502..5.05 rows=31 loops=1)
    -> Filter: ((journals.started_at >= TIMESTAMP'2024-06-30 15:00:00') and (journals.started_at < TIMESTAMP'2024-07-31 14:59:59.999'))  (cost=268 rows=114) (actual time=0.48..4.71 rows=55 loops=1)
        -> Index lookup on journals using FK_dcd8f26897887ea1ca19e9b910a (user_id=1)  (cost=268 rows=1025) (actual time=0.464..4.36 rows=1025 loops=1)
    -> Single-row covering index lookup on journals_dogs using PRIMARY (journal_id=journals.id, dog_id=1)  (cost=0.251 rows=1) (actual time=0.00558..0.00561 rows=0.564 loops=55)

• Single-row covering index lookup on journals_dogs using PRIMARY (journal_id=journals.id, dog_id=1) (cost=0.251 rows=1) (actual time=0.00558..0.00561 rows=0.564 loops=55) 이번에는 journal 테이블에 먼저 접근해서 필터링을 한 뒤 반환된 55개의 행으로 journals_dogs 테이블에 접근하고 있습니다. 루프는 55번만 실행됩니다.

이로써 1011번 -> 55번의 반복으로 조인을 수행할 수 있게 되어
최종 cost가 457 -> 307로 약 32퍼센트 감소했습니다.
(Actual time은 캐싱의 영향으로 정확도가 떨어지는 것 같아 지표로 삼지 않았습니다.)