계층 구조의 데이터를 다루는 Recursive Query 도입기

들어가는 글 🙋‍♀️

이번 글에서는 계층형 데이터를 API server에서 불러올 때 생겼던 문제와, 그래서 Recursive Query를 도입하여 속도 문제를 개선한 사례를 소개합니다.

계층형 데이터 구조를 다루게 된 계기

저는 기존의 코드를 인수인계 받아, 콘텐츠의 소속을 정할 수 있는 카테고리 기능의 성능 개선 및 추가 개발을 한 바가 있습니다.

계층형 데이터 구조는 말 그대로 데이터 간의 계층이 존재한다는 것이고, 이는 곧 부모-자식의 관계가 있는 트리 구조라는 말과 동일합니다.
이 트리 구조의 데이터는 일반적으로,

plain
1) 글의 카테고리를 나눈다거나,
2) 폴더 구조를 지원한다거나,
3) 조직도 표현할 때

구현하기 위해 쓰입니다.

제가 인수인계 받은 카테고리 기능도 트리 형태의 데이터를 다루기 때문에 테이블 설계가 다음과 같은 스펙으로 구성되어 있었습니다.

column name	type	description
id	integer	primary key
parent_id	integer	부모 카테고리 id (셀프 참조 FK, nullable)
name	varchar	카테고리 이름

(이 때 parent_id가 null일 때 root category가 되는 셈입니다.)

API 서버 구현 스펙

백엔드 개발 스펙 중, 본 글과 관련된 것은 다음과 같습니다.

plain
Python Flask - 2.2.2
Flask-SQLAlchemy - 3.0.2

plain
PostgreSQL - 13.10

기존의 코드 파악하기 🔎

앞서 정의한 DB의 테이블을 flask에서는 flask-sqlalchemy를 이용하여 ORM 클래스로 표현할 수 있습니다.(ORM을 사용하면 python 문법으로 DB의 데이터를 다룰 수 있게 됩니다.)
다음의 코드로 Category 클래스가 정의되어 있음을 파악했습니다.

python
from flask_sqlalchemy import SQLAlchemy

db = SQLAlchemy()

# config 설정은 생략

class Category(db.Model):
	__tablename__ = "categories"

    id = db.Column(db.Integer, primary_key=True, autoincrement=True, nullable=False)
    parent_id = db.Column(db.Integer, foreign_key=[id])
    name = db.Column(db.String)

그리고 재귀 함수(메소드)에서 특정 카테고리의 모든 descendant를 가져올 수 있게 되어 있었습니다.

python
class Category(db.Model):
    # 생략
    @classmethod
    def get(cls, id_):
    	"""특정 id 값의 데이터를 가져옵니다."""
    	return cls.query.filter(cls.id == id_).one_or_none()

    def get_descendant(self):
    	"""category 인스턴스의 모든 자식(자손)을 가져와서 dictionary 형태로 보내줍니다."""
        children = Categories.query.filter(Categories.parent == self).all()
        children_list = []
        for child in children:
            ele = child.get_descendants()
            children_list.append(ele)
        return {
            "id": self.id,
            "name": self.name
            "children": res_children
        }

python
# 다음으로 전체 카테고리 정보를 불러옵니다
category = Category.get(1)
print(category.get_descendant())

위의 쿼리를 이용하면, (DB에 임의의 데이터가 있다고 했을 때) 다음과 같이 자식 카테고리 리스트를 children이라는 키로 품고 있는 재귀 모양의 딕션너리를 얻을 수 있습니다.

python
{
    "id": 1,
    "name": "first",
    "children": [
        {
            "id": 2,
            "name": "second",
            "children": []
        },
        {
            "id": 3,
            "name": "third",
            "children": [
                {
                    "id": 4,
                    "name": "fourth",
                    "children": [
                      	# ... 생략
                    ]
                },
                # ... 생략
             ]
        },
        {
            # .. 생략
        }
	]
}

하지만 문제가 생겼다 😱

기존의 문제점

위의 코드를 실행하면 큰 문제가 생깁니다. 데이터의 양이 늘어나면 늘어날수록 속도가 너무 느려진다는 것입니다. 실제로 카테고리의 개수가 100개 이상 늘어났을 땐 해당 쿼리를 호출하는 부분에서만 10초 이상 걸려, API호출이 느려졌습니다.

도대체 왜?

get_descendant 메소드 내에서 all()이라는 메소드를 호출할 때마다 API 서버에서 DB에 쿼리를 날립니다. 그리고 또 for문으로 돌면서 데이터의 개수만큼 child category의 get_descendant 메소드를 호출하고 있습니다. 말인 즉슨 위의 코드를 실행하면 DB에 조회할 쿼리의 개수가 늘어난다는 것이고, 이는 곧,

n+1 query를 초래합니다.

우리가 app 단에서 ORM을 사용할 때 주의할 점은 DB에 조회할 query의 수를 줄이고 commit 횟수를 줄여야 한다는 것입니다. 왜냐면 query 조회수가 많아지거나 commit 횟수가 많아지면 session을 열고 닫는 횟수가 늘면서 그만큼 API handler 내에서의 성능 저하가 있기 때문입니다.

따라서 다음과 같은 목적을 가지고 해결점을 찾아 나아갔습니다.

plain
1. 유지해야 할 것
- 위의 dictionary 형태를 유지할 것(재귀 형태의 데이터로)
- 단, 검색 기능이 존재하고 해당 검색어에 맞는 카테고리와 그 카테고리의 조상 노드를 모두 찾아줘야 함

2. 개선해야 할 것
- 속도
- n+1 쿼리

개선해보자 🔧

위의 유지해야 할 것과 개선해야 할 것을 통틀어서 해결할 수 있는 것은 recursive query라고 판단했습니다.
recursive query는 postgresql cte 중 하나라고 할 수 있습니다. start query와 반복 수행할 query를 union 하여 재귀적으로 데이터를 가져올 수 있습니다.

recursive query를 사용하면 한 번의 query로 각 데이터의 parent_id path도 뽑아올 수 있습니다. 다음의 쿼리를 돌려봅니다.

sql
WITH RECURSIVE category_cte AS (
	SELECT  -- 시작 쿼리를 작성합니다, 일반적으로 시작 쿼리는 parent_id가 null 경우가 됩니다.
		id,
		ARRAY[0] AS "c_path",
		"name",
		1 AS "depth"
	FROM categories
	WHERE parent_id IS NULL
	UNION ALL
	SELECT  -- 재귀로 돌릴 쿼리를 작성하여 UNION ALL 합니다
		c.id,
		category_cte."c_path" || c.parent_id ,  -- path를 계속 찾아 줌
		c."name",
		category_cte."depth" + 1  -- 현재 데이터의 depth를 찾아 줌
	FROM categories c, category_cte
    WHERE c.parent_id = category_cte.id
)
SELECT * FROM category_cte

그럼 다음의 결과가 나오게 됩니다.

id	c_path	name	depth
1	{0}	first	1
2	{0, 1}	second	2
3	{0, 1}	third	2
4	{0, 1, 3}	fourth	3

이렇게 하면 이름의 검색어를 찾는 쿼리를 쓰면서, 조상 노드까지 모두 찾아올 수 있게 됩니다.

sql
-- "th" 라는 검색어로 데이터를 찾아올 때
WITH RECURSIVE category_cte AS (
  -- 생략
)
SELECT * FROM category_cte
WHERE "name" LIKE '%th%'

id	c_path	name	depth
3	{0, 1}	third	2
4	{0, 1, 3}	fourth	3

이를 다시 SQLAlchemy로 작성하면 다음과 같이 작성할 수 있습니다.

python
from sqlalchemy import literal
from sqlalchemy.dialects import postgresql

class Category(db.Model):
    # 생략
    @classmethod
    def get_result_recurvise(cls, term):
    	"""재귀 쿼리 ORM을 이용해 데이터를 가져올 수 있습니다."""
        start_query = db.session.query(
            cls.id,
            cls.name,
            postgresql.array([cls.parent_id]).label("c_path"),
            literal(1).label("depth")
        ).filter(
            cls.parent_id.is_(None)
        ).cte("category_cte", recursive=True)  # 재귀 쿼리임을 여기서 표현합니다

        repeat_query = db.session.query(
            cls.id,
            cls.name,
            start_query.c.c_path + postgresql.array([cls.parent_id]),
            leteral(start_query.c.depth + 1)
        ).filter(
            cls.parent_id == start_query.c.id
        )
        recursive_query = start_query.union_all(repeat_query)
        query = db.session.query(recursive_query)

        return query.filter(
            cls.name.like(f"%{term}%")
        ).all()

결과는?!

유지해야 할 것에 단, 검색 기능이 존재하고 해당 검색어에 맞는 카테고리와 그 카테고리의 조상 노드를 모두 찾아줘야 함라는 조건이 존재했기에, 특정 카테고리와 그 카테고리의 조상 노드의 id을 찾아서 한 번 더 Category.query.filter(Category.id.in({찾아와야 할 모든 카테고리 id의 리스트})).all() 코드로 추가 쿼리 실행 및 따로 python dictionary를 만드는 과정을 추가해야 했습니다만,

plain
n+1 쿼리 문제를 해결하였고, API 호출 속도도 1초 내로 줄일 수 있었습니다.

(그 외에 기능이 많이 추가 되고 데이터가 많아질수록 조금 느려지긴 했으나, API 호출이 1초 선에서 그쳤습니다)

이게 끝은 아니다?

계층적 데이터를 다루는 데에 있어서 가장 쉬운 방법인 parent_id 컬럼을 이용한 재귀적 패턴이지만, Recursive Query를 사용할 수 있는 데이터베이스가 한정되어 있어 상황에 맞게 사용해야 합니다.

또한, 클로저 패턴(closure pattern)을 소개받은 바가 있고 이는 기존에 사용했던 패턴보다 데이터를 다루기에 용이하고 성능이 더 뛰어나다는 설명을 들은 바가 있습니다. 하지만 이미 개발이 많이 진행이 되어 있던 상황이라 당장 테이블 구조를 바꾸기 어렵다는 판단하에 적용하지 못했습니다.
그러나 클로저 패턴의 분명한 장점이 존재했고(노드의 부모가 1개가 아닌 경우에 구조를 짤 수 있다는 점, 부모 조회/자식 조회가 수월하다는 점 등) 이는 다른 기능 개발 시 계층적 데이터 구조일 때 시도하면 좋겠다는 생각이 들었습니다.

마치며 🤗

계층 데이터 구조를 다루고 ORM 사용하는 데에 있어서 더 효율적인 방법을 찾고, 더 많은 고민을 해볼 수 있었습니다.
단, 실제 기능 정의에 맞는 데이터 구조를 더 깊게 고민해봐야 함을 깨달았고 다양한 패턴들에 대한 정의, 장단점을 더 공부해야겠다는 다짐을 한 계기가 됐습니다.