분산 데이터베이스 TigerBeetle이 공개한 코딩 규범 문서 'Tiger Style'에는 제어 흐름을 한곳에 모으라는 조언이 담겨 있다. 큰 함수를 쪼갤 때 switch나 if 같은 분기문은 '부모' 함수에 남겨 두고, 분기가 없는 로직 조각만 헬퍼 함수로 옮기라는 것이다. 제어 흐름은 한 함수가 책임지고 나머지는 그것에 신경 쓰지 않게 하라는 이 원칙을 한 문장으로 압축한 표현이 'push ifs up and fors down', 즉 '조건은 위로, 반복은 아래로'다. Rust 개발자로 잘 알려진 matklad도 이 격언을 여러 각도에서 옹호하는 글을 쓴 바 있다. 언뜻 사소한 스타일 규칙처럼 보이지만, 이 격언은 쿼리 옵티마이저와 함수형 프로그래밍의 대수(algebra)에서 반복적으로 등장하는 더 넓은 구조적 통찰과 맞닿아 있다.
두 가지 움직임, 그리고 그 합성
'조건을 위로'는 함수가 입력에 따라 분기한다면 그 분기를 호출자 쪽으로 끌어올리라는 뜻이다. matklad의 예시에서 frobnicate(walrus: Option)는 내부에서 Option을 열어 None을 처리하지만, 대신 호출자가 None을 처리하고 함수는 평범한 Walrus만 받도록 바꾼다. 그러면 함수의 타입 자체가 전제 조건을 선언하게 되고, 입력이 가질 수 있는 상태 공간이 좁아진다. 핵심은 데이터가 얼마나 흐르느냐가 아니라 '결정이 어디에 사는가'다. 반대로 '반복을 아래로'는 루프를 가능한 한 늦게, 데이터를 거르고 줄인 뒤에 돌리라는 것이다. frobnicate(walrus)를 루프로 호출하는 대신 frobnicate_batch(walruses)를 제공하고 루프를 그 안쪽에 둔다. 그러면 뜨거운 루프가 분기 없이 돌아 벡터화 대상이 된다. 두 움직임은 자연스럽게 합쳐진다. Option의 컬렉션이 있을 때, 호출자가 None을 버리고 나머지를 Vec로 풀어 batch 함수에 넘기면, 그 함수는 None의 존재 자체를 고려할 필요가 없어진다.옵티마이저가 오래전부터 알던 것
같은 원칙이 관계형 데이터베이스의 쿼리 최적화에 이미 녹아 있다. 필요한 컬럼만 추리는 프로젝션과 WHERE 조건에 해당하는 셀렉션은 가능한 한 일찍 수행하고, 비싼 조인은 뒤로 미루라는 것은 교과서적 상식이다. 다만 어휘가 뒤집혀 있어 혼란스럽다. 쿼리 플랜은 잎이 테이블 스캔이고 뿌리가 결과를 내는 트리이며 데이터가 잎에서 위로 흐른다. 그래서 '트리 아래로'가 곧 '실행에서 더 일찍'을 뜻한다. 옵티마이저가 술어를 'push down'한다고 말할 때 그것은 가능한 한 이르게 평가한다는 의미이고, 이는 이 격언이 말하는 '위로' 혹은 '일찍'과 같은 동작이다. 셀렉션과 프로젝션을 조인 아래로 내려 조인이 더 작은 입력 위에서 돌게 하면, 가장 비싼 결합 연산자가 쿼리 의미가 허용하는 가장 작은 입력만 처리하게 된다.실행 방식에서도 '반복을 아래로'의 대응물이 보인다. 고전적인 볼케이노(Volcano) 모델은 각 연산자가 가상 next() 호출을 통해 한 번에 한 행씩 처리한다. 대안인 벡터화 혹은 배치 실행에서는 연산자가 천 개 안팎의 튜플 묶음마다 한 번씩 호출되고 그 안에서 촘촘한 루프가 돈다. 이것이 쿼리 엔진 수준에서의 frobnicate 대 frobnicate_batch다. 호출당 오버헤드와 호출당 결정 비용을 배치마다 한 번만 지불하고, 안쪽 루프는 분기가 적고 캐시 친화적이 된다.
어떤 재작성이 '합법'인가
함수형 프로그래밍과 범주론의 렌즈로 보면 왜 이것이 단순한 취향 문제가 아닌지가 드러난다. 범주론적으로 Option는 '아무것도 없음' 아니면 '바다코끼리'인 코프로덕트 1 + Walrus다. 이런 코프로덕트에서 나가는 함수는 보편 성질에 의해 각 요소에 대한 함수 한 쌍과 정확히 같다. 조건을 위로 올린다는 것은 이 쌍을 분해해, 호출자가 1 쪽을 맡고 핵심 함수는 Walrus 성분만 다루게 하는 일이다. 흔히 듣는 'map 전에 filter하라'는 조언도 같은 뿌리를 갖는다. 다만 filter p . map f와 map f . filter p는 서로 다른 타입을 가지며 그냥 같지 않다. 둘을 실제로 연결하는 법칙은 filter p . map f == map f . filter (p . f)이고, 이는 catMaybes :: [Maybe a] -> [a]의 자연성(naturality)에서 따라 나온다. 즉 어떤 재작성이 합법인지는 취향이 아니라 대수가 말해 준다.중요한 단서는 오른쪽 식이 자동으로 더 싸지는 않다는 점이다. filter (p . f)도 테스트를 위해 모든 원소에 대해 f를 계산한다. 이 재작성이 이득이 되는 경우는 p . f가 입력에 대한 값싼 술어 q로 단순해질 때뿐이다. 대개 p가 f는 건드리지 않는 부분만 들여다볼 때 그렇다. 그러면 filter p . map f == map f . filter q가 성립하고, f는 살아남은 원소에만 실행된다. 양쪽 모두 여전히 한 번의 O(n) 순회지만, 버려질 원소에 대한 f 호출을 아끼는 것이다.