1. 쿼리 비교

이중 연결 리스트

<aside>

이중 연결리스트는 아래와 같이 이전 연결 리스트와 이후 연결리스트 아이디를 가져야 한다.

만약 그렇다면 이 경우에 페이징을 어떻게 해서 가지고 올 것 인가?

@Entity
@Getter
@Setter(AccessLevel.NONE)
@NoArgsConstructor(access = AccessLevel.PROTECTED)
@Table(
        indexes = {
                @Index(name = "idx_play_list_id", columnList = "playListId"),
        }
)
public class DoubleLinkedListItem {

    @Id @SnowflakeId
    @GeneratedValue
    @Column(name = "doubleLinkedListItemId")
    private Long id;

    @Column(unique = true)
    @Comment("이전 연결리스트 아이디")
    private Long prevId;

    @Column(unique = true)
    @Comment("이후 연결리스트 아이디")
    private Long nextId;

    @Column(name = "playListId")
    private Long playListId;
}

</aside>

<aside>

페이징 쿼리

@Repository
public interface TestDoubledListRepository extends JpaRepository<DoubleLinkedListItem, Long> {

    @Query(value = """
        WITH RECURSIVE chain AS (
            SELECT  d.double_linked_list_item_id,
                    d.prev_id,
                    d.next_id,
                    d.play_list_id,
                    0 AS depth
            FROM    double_linked_list_item d
            WHERE   d.double_linked_list_item_id = :cursorId
              AND   d.play_list_id               = :playListId
        
            UNION ALL
        
            SELECT  d.double_linked_list_item_id,
                    d.prev_id,
                    d.next_id,
                    d.play_list_id,
                    c.depth + 1
            FROM    double_linked_list_item d
            JOIN    chain c
                   ON d.double_linked_list_item_id = c.next_id
            WHERE   d.play_list_id = :playListId
              AND   c.depth < :pageSize - 1
        )
        SELECT  double_linked_list_item_id,
                prev_id,
                next_id,
                play_list_id
        FROM    chain
        ORDER BY depth
        LIMIT   :pageSize
    """, nativeQuery = true)
    List<DoubleLinkedListItem> findNextPage(Long playListId,
                                            Long cursorId,
                                            int pageSize);
}

WITH RECURSIVE

cursorId ──▶  첫 줄(앵커)      ──▶  재귀로 next_id 따라가기      ──▶  depth<pageSize 까지 모으기  
           (depth = 0)              (depth = 1,2,3 …)              (최대 pageSize-1 단계)

WITH RECURSIVE는 재귀적 방식을 의미한다.

즉, 임시 테이블을 하나 만들고 하나씩 가지고 와서 임시테이블이 채운다.

이 과정에서 가지고 온 데이터를 토대로 JOIN 연산이 들어간다.

종료 조건

왜 depth라는 값이 필요할까? depth의 값이 없다면 재귀적 호출을 다음 연결리스트가 없을때 까지 진행된다.

즉, 나는 20개의 데이터만 필요한데 모든 데이터가 임시 테이블로 올라오는 것이다.

이는 결국 CPU와 I/O의 오버헤드가 발생하는 것이다. 따라서 depth를 통해 최대 가지고 오는 수를 제한하는 것이다.

</aside>

Gap-Based-Numbering

<aside>

gap-based-numbering 방식은 순서를 주면서 각 순서 사이에 간격을 주는 것이다.

즉, [0, 10000, 20000, 30000] 이런식의 간격을 준다.

이렇게 주는 이유는 20000을 0과 10000 사이로 옮길때 둘 사이의 평균 값인 5000으로 바꾸는 것이다.

즉, 20000을 0과 10000 사이로 옮긴다면 [0, 5000, 10000, 30000] 이 되는 것이다.

자세한 설명은 해당 페이지에 정리해두었다.

@Entity
@Getter
@Setter(AccessLevel.NONE)
@NoArgsConstructor(access = AccessLevel.PROTECTED)
@Table(
        uniqueConstraints = {
                @UniqueConstraint(
                        name = "uk_playlist_position",
                        columnNames = { "playListId", "position" }
                )
        }
)
public class GapOrderingItem {

    @Id @SnowflakeId
    @GeneratedValue
    @Column(name = "gapOrderingItemId")
    private Long id;

    @Column(nullable = false)
    @Comment("정렬용 숫자 값으로 같은 플레이리스트 내에서 유일해야 한다")
    private Long position;

    @Column(name = "playListId")
    private Long playListId;
}

</aside>

<aside>

페이징 쿼리

@Repository
@RequiredArgsConstructor
public class TestGapPaginationRepository {

	private final JPAQueryFactory query;

	public List<GapOrderingItem> getItemByCursor(
			Long playListId,
			Long cursor
	) {
		return query.select(gapOrderingItem)
				.from(gapOrderingItem)
				.where(
						getId(playListId),
						getAfter(cursor)
				)
				.orderBy(gapOrderingItem.position.asc())
				.limit(MAX_PLAY_PAGE_SIZE + 1)
				.fetch();
	}

	private BooleanExpression getAfter(Long cursor) {
		return cursor == null ? null : gapOrderingItem.position.gt(cursor);
	}

	private BooleanExpression getId(Long playListId) {
		return playListId == null ? null : gapOrderingItem.playListId.eq(playListId);
	}
}

즉, 위와같이 훨씬 깔끔한 쿼리로 성능을 테스트할 수 있다

프로세스

1. gapOrderingItem.position.gt(cursor) 조건을 만족하는 데이터를 찾는다.
2. 해당 데이터를 기반으로 LinkedLisk 방식으로 조회후 가지고 온다. 즉, 추가적인 Log(N)의 방식이 아닌 트리의 리프페이지에서 링크드 리스트 연결로 가지고 오는 것이다. </aside>

2. 성능테스트

프로세스

<aside>

GapOrderingItem

1. 5,000,000개의 데이터가 있다
2. playListId 당 1000개의 GapOrderingItem를 가진다.
3. 커서 기반 + Recursive With을 통한 페이지네이션을 사용한다. 이때 최적화를 위해 Depth까지만 가지고 온다

DoubleLinkedListItem

1. 5,000,000개의 데이터가 있다.
2. playListId 당 1000개의 GapOrderingItem를 가진다.
3. 커서 기반 페이지 네이션을 사용한다.

HTTP 요청

사용자의 수를 5분동안 5000명으로 증가시킨다.

각 요청은 특정 playListId를 하나 랜덤으로 고른 후 거기서 특정 페이지를 가지고 와 반환한다

</aside>

1️⃣ 이중 연결리스트

<aside>

2️⃣ Gap-Based-Numbering