Hierarchical SQL in Django: Adjacent List

• RDB에서 계층 구조를 나타내기에 가장 일반적이고 자연스러운 방법

• Foreign Key로 자식 노드, 부모 노드를 가르킨다.

• FK가 가르키고 있는 부모, 자식 노드를 찾기 위해 Recursive한 메소드가 필요하다.

  • ORM 단계에서 Recursive하게 호출하거나
  • 단일 쿼리에서 Self Join, CTE를 이용해 부모, 자식 노드를 재귀적으로 호출

• 간단한 계층 구조에서 적합한 방법이지만 복잡한 계층 구조에서는 쿼리 작성 난이도 상승, Join으로 인한 DB 성능 저하가 발생할 수 있다.

Django Model Example

class Node(models.Model):
		parent = models.ForeignKey(
				"self",
				on_delete=models.CASCADE,
				related_name='child'
		)
		
		...

ORM/SQL Example

Descendants를 조회하는 ORM

from itertools import chain
from typing import Iterable

def get_descendants(node: Node) -> Iterable[Node]:
	queryset = Node.objects.filter(parent=node)
	results = chain(queryset)
	for child in queryset:
			results = chain(results, get_descendants(child))
	return results

descendants_of_node_7 = list(get_descendants(Node.objects.get(pk=7)))
# [4, 10, 6, 5, 11]

Ascendants를 조회하는 ORM

def get_ascendants(node: Node) -> Iterable[Node]:
	if node.parent:
    	return chain([node.parent], get_ancestors(node.parent))
        
    return chain()

ascendants_of_node_11 = get_ascendants(Node.objects.get(pk=11))
# [6, 7, 2]

• 간단한 계층 구조에서 descendant, ascendant 노드들을 쉽게 가져올 수 있다.
• 하지만 복잡한 구조에서는 비효율적인 쿼리(N+1 쿼리)로 인한 성능저하를 겪을 수 있다.
  • 조회하고자 하는 Sub Tree의 모든 Node에 대해 추가적으로 쿼리를 수행하기 때문이다.

Self Join을 이용한 Raw Query

# descendants_of_node_7 = list(get_descendants(Node.objects.get(pk=7)))
SELECT t1.id, t2.id, t3.id, t4.id
FROM Node as t1
LEFT JOIN Node as t2 ON t2.parent_id=t1.id
LEFT JOIN Node as t3 ON t3.parent_id=t2.id
LEFT JOIN Node as t4 ON t4.parent_id=t3.id
WHERE t1.id = 7

• 테이블 Join을 이용해 추가 쿼리 없이 한번에 쿼리할 수 있다.
• 조회하고자 하는 sub tree의 depth가 얕고, depth가 정해진 경우 적절한 방법이다.

Recursive CTE 참고

WITH RECURSIVE descendants 
	(id, name, depth, parent_id)
AS (
	SELECT 
    	id, 
    	name, 
    	0, 
    	parent_id, 
	FROM Node
    WHERE parent_id is NULL
    
    UNION ALL
    
    SELECT
    	N1.id,
    	N1.name,
    	T1.depth + 1,
    	T1.id,
    FROM Node N1, descendants T1
    WHERE N1.parent_id = T1.id
)
SELECT * FROM descendants
WHERE depth > 0
ORDER BY depth, parent_id;

• sub tree의 depth 제한 없이 모든 child를 가져올 수 있다.
• postgresql의 경우 WITH clause를 이용한 recursive cte는 parent query로부터 fetch하며 쿼리를 반복한다.
  • postgresql docs에서는 production level에서 사용하지 않기를 권하고, 분석용으로 사용하기를 권한다. (DB 엔진마다 작동방식이 달라 결과가 달라질 수 있기 때문에)
  • query optimizer의 적용이 되지 않으므로 성능상 손해가 발생할 수 있다.
• django-cte 라이브러리를 이용해서 CTE query를 raw query가 아닌 python code로 관리할 수 있다는 장점이 있다.

참고

itertools.chain()을 이용한 쿼리셋 합치기

Recursive SQL Queries with PostgreSQLRecursive SQL Queries with PostgreSQL

Do it in sql recursive tree traversal

postgresql docs - WITH

Joe Celko's Trees and Hierarchies in SQL for Smarties