트리 계층 구조에서의 배치 반복 (개념 증명)

GitLab 그룹 계층 구조에서 재귀 CTE SQL 쿼리를 사용한 배치 반복 알고리즘의 개념 증명을 설명합니다.

GitLab의 그룹 계층 구조는 트리로 표현되며, 루트 요소는 최상위 네임스페이스이고 자식 요소는 하위 그룹 또는 최근에 도입된 Namespaces::ProjectNamespace 레코드입니다. 트리는 namespaces 테이블에서 parent_id 칼럼을 통해 구현됩니다. 이 칼럼은 상위 네임스페이스 레코드를 가리킵니다. 최상위 네임스페이스에는 parent_id 가 없습니다. gitlab-org 의 부분 계층 구조: flowchart TD A("gitlab-org (9979)") --- B("quality (2750817)") B --- C("engineering-productivity (16947798)") B --- D("performance-testing (9453799)") A --- F("charts (5032027)") A --- E("ruby (14018648)") 그룹 계층 구조를 효율적으로 반복하는 것은 여러 잠재적인 사용 사례를 가집니다. 이는 특히 그룹 계층 구조에 대한 쿼리를 수행해야 하는 백그라운드 job에서 중요하며, 빠른 실행 시간보다 안정적이고 안전한 실행이 더 중요합니다. 배치 반복은 더 많은 네트워크 왕복이 필요하지만, 각 배치는 유사한 성능 특성을 제공합니다. 몇 가지 예시: 각 하위 그룹에 대해 무언가를 수행합니다. 계층 구조의 각 프로젝트에 대해 무언가를 수행합니다. 계층 구조의 각 이슈에 대해 무언가를 수행합니다. 문제 설명 # 그룹 계층 구조가 너무 커져서 단일 쿼리로는 제시간에 로드할 수 없는 경우가 있습니다. 쿼리가 statement timeout 오류로 실패할 수 있습니다. 매우 큰 그룹과 관련된 확장성 문제를 해결하려면 동일한 데이터를 다른 형식으로 저장해야 합니다(비정규화). 그러나 그룹 계층 구조를 로드할 수 없다면 비정규화를 구현할 수 없습니다. 한 가지 비정규화 기법은 특정 그룹의 모든 하위 그룹 ID를 저장하는 것입니다. 이를 통해 그룹 및 하위 그룹을 로드해야 하는 쿼리의 속도를 높일 수 있습니다. 예시: flowchart TD A(1) --- B(2) A --- C(3) C --- D(4) GROUP_ID DESCENDANT_GROUP_IDS 1 [2,3,4] 2 [] 3 [4] 4 [] 이 구조를 사용하면, 모든 하위 그룹을 파악하는 데 4개의 행 대신 데이터베이스에서 단 1개의 행만 읽으면 됩니다. 1000개의 그룹으로 구성된 계층 구조의 경우, 이는 큰 차이를 만들 수 있습니다. 계층 구조 읽기 문제는 이 비정규화로 해결됩니다. 그러나 여전히 이 데이터를 테이블에 지속적으로 저장할 방법을 찾아야 합니다. 그룹과 그 계층 구조가 매우 커질 수 있으므로, 단일 쿼리가 여기서 작동할 것으로 기대할 수 없습니다. SELECT id FROM namespaces WHERE traversal_ids && ARRAY[9970] 위 쿼리는 대규모 그룹의 경우 타임아웃이 발생할 수 있으므로, 데이터를 배치로 처리해야 합니다. 트리에서의 배치 로직 구현은 이전에 살펴본 적