Hierarchical SQL in Django: Materialized Path

• Materialized Path에서는 Foreign Key 없이 path 정보만으로 Tree구조에서 두 노드 사이의 관계를 알 수 있다.

Materialized Path 원리

• 자식 노드의 path = 부모 노드의 path + 일정한 길이의 string
  • path는 알파벳 대문자 + 숫자로 구성된다.
    • 대부분의 DB에서 정렬기준이 동일한 charset들이다.
  • path_length_per_depth(steplen): depth가 하나씩 늘 때마다 path에 추가되는 string 크기
• 부모 - 자식 노드 판별
  • child_path[:-path_length_per_depth] == parent_path
  • 자식 노드의 path는 부모 노드의 path를 포함한 형태로 저장하기 때문이다.
• Ascendants, Descendants 노드 판별
  • descendants_path[:depth_difference * path_length_per_depth] == ascendants_path
  • descendant이면 ascendant의 path를 항상 포함하고 있기 때문이다.

Materialized Path를 이용한 계층 구조 예시

• 파일 디렉토리
  
  • e.g. 가장 하단의 ee.jpg의 file path
    • path에 부모의 path를 prefix로 가진다
    • /opt/aaa/window/ee.jpg
  • /opt/aaa 에 해당하는 폴더, 파일들
    • 검색하고자 하는 폴더 path를 prefix로 가진 path를 모두 검색하면 된다.
    • /opt/aaa/aa.txt, /opt/aaa/linux, /opt/aaa/window/ddd, /opt/aaa/window/ee.jpg

Django Model Example

class MPNode(models.Model):
    path_length_per_depth = 1
    alphabet = [ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789]
    path = models.CharField(
        "materialized_path",
    	max_lenghth=256,
        editable=False
    )
    ...
    
    class Meta:
        indexes = [
            models.Index(
                fields=['path'],
                name='materialized_path_index'
            )
        ]

ORM/SQL Example

Descendants를 조회하는 ORM

def get_descendants(node: MPNode) -> QuerySet:
    descendants_query_set = MPNode.objects.filter(
    	path__startswith=node.path
    )
    descendants_query_set = descendants_query_set.exclude(
        path=node.path
    )
    
    return descendants_query_set

# Descendants of node which is 'AAF'
node_AAF = MPNode.objects.get(path='AAF')
descendants_of_node_AAF = get_descendants(node_AAF)
    

Ascendants를 조회하는 ORM

def get_ascendants(node: MPNode) -> QuerySet:
	ascendants_path_list = [
        node.path[:depth * path_lenghth_per_depth] 
        for depth in range(1, len(node.path))
    ]
    ascendants_query_set = MPNode.objects.filter(
    	path__in=ascendants_path_list
    )
    
    return ascendants_query_set

Descendants를 조회하는 Raw Query

SELECT * FROM MPNode WHERE path LIKE 'AAF' AND NOT PATH = 'AAF'

참고

Joe Celko's Trees and Hierarchies in SQL for Smarties