하나의 런타임, 다양한 의미론: UQA Engine의 타입 기반 캐리어 대수

진정한 통합은 각 데이터의 의미를 보존합니다

현대 애플리케이션에서는 하나의 질문에 답하기 위해 여러 데이터 처리 방식을 함께 사용해야 할 수 있습니다. 관계형 조건식으로 검색 대상 문서군을 좁히고, 전문 검색으로 어휘적 근거를 찾고, 벡터 검색으로 의미적으로 가까운 항목을 확보하고, 그래프 탐색으로 구조적 맥락을 더한 뒤, 순위 산정으로 최종 행을 선택합니다.

일반적인 아키텍처는 각 단계를 서로 다른 시스템에 맡깁니다. 그러면 애플리케이션은 의도치 않게 쿼리 엔진 역할을 하게 됩니다. 저장소 간 식별자를 매핑하고, 프로세스 경계를 넘어 후보 집합을 옮기고, 트랜잭션 상태를 맞추고, 서로 무관한 점수를 정규화하고, 전역 통계 없이 실행 순서를 정해야 합니다.

UQA Engine은 반대 방향으로 접근합니다. PostgreSQL 지향 SQL, 텍스트 검색, 벡터 검색, 그래프 쿼리, 확률적 순위 산정을 하나의 체계 안에서 실행 계획을 세우고 처리하는 임베디드 Rust 데이터베이스 엔진입니다. 그 수학적 토대는 기존 UQA, 그래프 확장, 베이지안 하이브리드 검색 연구를 통합하고 개정한 논문 원고 A Typed Carrier Algebra for Unified Query Execution에 정리되어 있습니다.

개정된 논문의 핵심은 데이터를 표현하는 방식의 변화입니다. 모든 값을 하나의 범용 포스팅 리스트로 표현한다는 발상은 매력적이지만, 적용 범위가 지나치게 넓었습니다. 개정된 논문은 이를 타입으로 구분된 캐리어들의 계열로 대체합니다. 새로운 주장은 적용 범위를 더 명확히 한정하면서도, 그 안에서는 더 강한 보장을 제공합니다.

$$\text{unification} \neq \text{one container for every intermediate value},$$ $$\text{unification} = \text{typed composition} + \text{one planning and execution calculus}.$$

즉, 통합은 모든 중간값을 하나의 컨테이너에 담는 것이 아니라, 타입에 따른 합성과 하나의 계획·실행 계산 체계를 결합하는 것입니다. 서로 다른 값은 각자에게 적용되는 법칙을 유지하면서도 하나의 런타임에서 처리될 수 있습니다.

하나의 포스팅 리스트로 모든 의미를 표현할 수 없는 이유

$U$를 문서 식별자의 유한한 전체 집합, $\Pi$를 페이로드 영역이라고 하겠습니다. 페이로드를 지닌 포스팅 리스트는 다음과 같은 유한 부분 함수로 모델링할 수 있습니다.

$$P:U\rightharpoonup\Pi.$$

그 지지집합(support)은 소속 여부를 제외한 모든 정보를 버립니다.

$$\operatorname{supp}(P) = \{d\in U\mid P(d)\text{ is defined}\}.$$

$\operatorname{lift}(D)$가 문서 집합 $D$의 각 식별자에 기본 페이로드를 부여한다면, 문서 집합에 기본 페이로드를 부여한 뒤 다시 지지집합을 구하면 원래 문서 집합을 그대로 얻습니다.

$$\operatorname{supp}(\operatorname{lift}(D))=D.$$

하지만 반대 방향은 일반적으로 그렇지 않습니다.

$$\operatorname{lift}(\operatorname{supp}(P))\neq P.$$

포스팅 리스트를 지지집합으로 사영하면 용어 위치, 점수, 필드 값, 점수 경계값 등 모든 부가 정보가 사라집니다. 따라서 두 포스팅은 지지집합이 같더라도 관찰 가능한 의미가 다를 수 있습니다.

따라서 불 대수의 단순화 규칙을 모든 포스팅에 일괄 적용할 수는 없습니다. 같은 문서가 양쪽에 나타날 때 포스팅 병합이 점수를 더한다고 가정해 보겠습니다. 점수가 $0.8$인 문서에 대해,

$$P\mathbin{\widetilde\cup}P\neq P$$

입니다. 병합된 점수가 $1.6$이 되기 때문입니다. 충돌하는 필드에서 오른쪽 피연산자를 우선한다면 병합은 교환법칙도 만족하지 않습니다. 지지집합은 여전히 집합처럼 동작하지만, 페이로드까지 포함한 포스팅 전체는 같은 법칙을 따르지 않습니다.

다른 영역에서도 같은 손실이 발생합니다. SQL 다중집합(bag)을 집합으로 바꾸면 중복 횟수가 사라집니다. 조인 결과를 하나의 문서 ID로 축소하면 튜플의 식별 정보가 사라집니다. 그래프 매칭 결과를 지지집합으로 축소하면 정점, 간선, 경로, 그래프 이름이 사라집니다. 순위가 있는 결과를 순서 없는 포스팅 리스트로 바꾸면 순서가 사라집니다. 하나의 물리적 컨테이너에 이런 값들을 담을 수는 있지만, 값들 사이의 차이까지 없앨 수는 없습니다.

데이터의 특성에 따른 캐리어

논문은 관찰 가능한 각 구조에 고유한 캐리어를 부여합니다. 캐리어란 값의 영역과 그 값들에 대해 성립하는 법칙을 함께 일컫습니다.

이는 하나의 캐리어가 다른 캐리어를 암묵적으로 대체하는 클래스 계층이 아닙니다. 연산자의 출력 캐리어가 다음 연산자의 입력 캐리어와 일치하거나, 명시적인 어댑터가 변환과 그에 따른 정보 손실을 기록할 때만 합성이 허용됩니다.

이 구분은 다음과 같은 유용한 역할 분담으로 이어집니다.

• DocSet은 합집합, 교집합, 차집합, 명시적인 전체 집합에 대한 여집합 등 유한 불 대수를 담당합니다.
• Relation<K>는 반환 $K$가 제공하는 점별 덧셈과 곱셈을 담당합니다.
• PostingList는 불 대수의 멱등성을 물려받지 않고 페이로드 충돌 정책을 담당합니다.
• RankedView는 포스팅의 저장 순서를 바꾸지 않으면서 점수 순서, 결정적 동점 처리, 상위 $k$개 선택을 담당합니다.
• SQL 실행은 다중집합, NULL, 정렬 의미론을 유지합니다.
• 조인과 그래프 결과는 후속 연산자에 필요한 식별 정보와 맥락을 유지합니다.

이렇게 한다고 통합성이 줄어드는 것은 아닙니다. 모든 합성이 무엇을 보존하는지 명시하는 시스템이 됩니다.

관찰 가능한 정보에 따라 적용할 수 있는 법칙이 달라집니다

옵티마이저가 보존해야 하는 것은 값의 모든 세부 정보가 아니라, 재작성된 표현식을 사용하는 상위 연산자가 관찰할 수 있는 정보입니다.

$\operatorname{obs}_C$를 캐리어 $C$에서 드러나는 관찰이라고 하겠습니다. 더 많은 정보를 담은 관찰 결과에서 더 적은 정보를 담은 관찰 결과를 복원할 수 있다면, 전자는 후자를 정제한다고 합니다. 검색 캐리어의 정제 순서 중 일부는 다음과 같습니다.

$$\operatorname{obs}_{\mathsf{support}} \sqsubseteq \operatorname{obs}_{\mathsf{payload}} \sqsubseteq \operatorname{obs}_{\mathsf{ranked}}, \qquad \operatorname{obs}_{\mathsf{support}} \sqsubseteq \operatorname{obs}_{\mathsf{graph}}.$$

이 순서는 전순서가 아닌 부분순서입니다. SQL의 중복 횟수와 그래프 매칭 맥락은 서로 비교할 수 없습니다. 어느 쪽도 다른 쪽을 재구성할 수 없기 때문입니다.

이를 통해 정확한 재작성 규칙을 얻을 수 있습니다. 표현식 $e_1$과 $e_2$가 캐리어 관찰 $C$에서 동등하고, 주변 문맥이 그 관찰만을 통해 결정된다면, 하나를 다른 하나로 대체해도 올바릅니다.

$$e_1\equiv_C e_2 \;\land\; \mathcal K=\overline{\mathcal K}\circ\operatorname{obs}_C \quad\Longrightarrow\quad \mathcal K[e_1]\equiv\mathcal K[e_2].$$

이 원칙은 Rust 코드에도 구현되어 있습니다. OperatorTree::is_membership_only는 모든 연산자 변형을 빠짐없이 분류합니다. 대수적 단순화는 영향을 받는 모든 하위 트리가 기본 페이로드를 생성할 때만 중복 항을 제거하거나 흡수법칙을 적용합니다. 점수나 부가 정보를 가진 연산자가 새로 추가되면, 페이로드 동작을 검토하기 전까지는 이 최적화의 대상이 될 수 없습니다.

안전한 재작성을 거부하면 최적화 기회를 놓칩니다. 안전하지 않은 재작성을 허용하면 답이 바뀝니다. 구현은 의도적으로 전자를 택합니다.

순위 산정에는 집합 대수의 법칙을 그대로 적용할 수 없습니다

상위 $k$개 선택은 결정적이지만, 불 대수의 준동형은 아닙니다. 점수가 있는 두 포스팅과, 충돌 시 점수를 더하는 병합을 생각해 보겠습니다.

$$A=\{d_1\mapsto3,\ d_2\mapsto2\}, \qquad B=\{d_2\mapsto2\}.$$

먼저 병합하면 $d_2$가 점수 $4$로 1위가 됩니다.

$$\operatorname{top}_1(A\mathbin{\widetilde\cup}B)=\{d_2\}.$$

각 하위 연산의 결과에서 상위 항목만 먼저 남기면, $d_2$를 $d_1$보다 높게 만들었을 $A$의 기여분이 사라집니다.

$$\operatorname{top}_1\!\left( \operatorname{top}_1(A) \mathbin{\widetilde\cup} \operatorname{top}_1(B) \right) =\{d_1\}.$$

UQA Engine은 더 빨라 보인다는 이유만으로 불 연산이나 융합에 앞서 텍스트 검색 결과를 상위 $k$개로 제한하지 않습니다. WAND와 Block-Max WAND는 물리적 실행의 정제로 취급합니다. 즉, 결과의 의미를 보존하면서 실제 계산량을 줄이는 실행 기법입니다. 유효한 상한을 통해 정확한 최종 순위가 바뀌지 않음을 증명할 수 있을 때만 계산을 생략합니다. 점수 계산 방식이나 필드 통계가 바뀌면 영속화된 경계값은 무효화됩니다. 실행은 오래된 메타데이터를 신뢰하는 대신 정확한 결과를 계산하는 경로로 되돌아갑니다.

확률에도 타입이 있습니다

검색 시스템은 f64라는 표현은 같지만 의미는 다른 숫자들을 흔히 결합합니다. 원시 BM25 점수, 우도비 기여분, 관련성 사전확률, 사후확률에는 각각 허용되는 연산이 다릅니다. UQA Engine은 이를 서로 다른 Rust 타입으로 표현합니다.

• RawBm25Score
• EvidenceLogit
• PriorLogit
• PosteriorProbability

정확한 융합 규칙은 사전확률을 포함하지 않는, 부호 있는 증거에서 시작합니다. $R\in\{0,1\}$을 관련성이라고 하고, 신호 $x_1,\ldots,x_n$이 관련성이 있는 경우와 없는 경우 모두에서 조건부 독립이라고 가정하겠습니다. 각 신호가 제공하는 증거는 다음 로그 우도비로 표현됩니다.

$$e_i = \log\frac{p(x_i\mid R=1)}{p(x_i\mid R=0)}.$$

관련성 사전확률이 $\pi$일 때, 사후확률은 다음과 같습니다.

$$p(R=1\mid x_1,\ldots,x_n) = \sigma\!\left( \operatorname{logit}(\pi)+\sum_{i=1}^{n}e_i \right).$$

이 식에서 세 가지 엔지니어링 규칙이 바로 나옵니다. 증거가 0이면 중립적이어야 하고, 음의 증거는 음수로 유지되어야 하며, 사전확률은 정확히 한 번만 들어가야 합니다. 이미 같은 사전확률을 포함한 사후 로짓들을 더하면 사전확률을 반복해서 반영하게 됩니다.

코드는 이 정확한 연산자를 강건한 양의 증거 풀링과 분리합니다. 후자는 순위 산정에 유용할 수 있으므로 음이 아닌 게이트, 신뢰도 스케일링, 적응형 가중치를 사용할 수 있지만, 정확한 사후확률 정리가 아닌 휴리스틱임을 명시합니다. SQL 인터페이스에도 이 구분이 반영됩니다. fuse_bayesian_evidence와 fuse_log_odds는 하나의 사전확률을 사용하는 정확한 융합을 선택하고, pool_positive_evidence는 강건한 휴리스틱을 선택합니다.

같은 릴레이션의 텍스트 검색과 벡터 검색을 논리곱(AND)으로 결합한 쿼리가 지원 대상 형태에 해당하면, 옵티마이저는 정확한 융합을 적용할 경계를 자동으로 추론할 수 있습니다. 이 경계에서 원시 텍스트 매칭 점수를 보정하고, 벡터 증거에는 사전확률을 포함하지 않습니다. 일반적인 관계형 논리곱 조건은 반드시 충족해야 하는 필터로 유지하며, 해당 문서군에 대해 결정된 사전확률은 한 번만 적용합니다.

그래프 결과는 그래프 결과로 남습니다

그래프 탐색은 매칭된 식별자의 집합을 생성하지만, 그 지지집합이 결과의 전부는 아닙니다. UQA Engine은 그래프 포스팅을 다음과 같이 모델링합니다.

$$GP=(P,\gamma), \qquad \operatorname{dom}(\gamma)\subseteq\operatorname{supp}(P),$$

여기서 $P$는 일반적인 포스팅 페이로드이고, $\gamma(d)$는 그래프 이름, 매칭된 정점, 매칭된 간선, 선택적인 점수 재정의 값을 유지합니다. 이 불변조건은 그래프 메타데이터가 포스팅의 지지집합에 없는 문서를 참조하지 못하게 합니다.

서로 겹치는 그래프 결과에는 합집합, 교집합, 왼쪽 우선, 오른쪽 우선이라는 명시적인 부분 그래프 정책을 사용합니다. 그래프 이름의 충돌을 해결할 수 없으면 오류로 처리합니다. 일반적인 포스팅 필드 우선순위가 우연히 그래프 의미론을 결정하도록 허용하지 않습니다.

그래프 출력이 포스팅 중심의 경계를 넘어야 할 때는 버전이 부여된 $\Phi$ 코덱이 기본 페이로드와 지지집합을 보존하면서 그래프 보조 맵을 예약된 페이로드 필드에 인코딩합니다. 핵심 주장의 범위는 의도적으로 제한되어 있습니다.

$$\Phi^{-1}(\Phi(g))=g$$

이 식은 코덱 계약을 따르는 유효한 그래프 포스팅 값에 대해 성립합니다. 이는 하나의 타입화된 캐리어에 대한 무손실 표현 변환이지, 임의의 그래프와 문서 집합 사이의 동형 관계가 아닙니다.

정규 경로 쿼리도 그래프 고유의 방식으로 처리됩니다. 경로 표현식은 오토마톤 $A_R$로 컴파일되고, 탐색은 곱 그래프 $G\times A_R$에서의 도달 가능성 문제가 됩니다. 이후 결과를 관계형 행과 조인할 수 있지만, 공유 런타임에 참여하기 위해 탐색이 그래프 의미론을 버릴 필요는 없습니다.

Rust 엔진에 대수가 반영되는 방식

현재 UQA Engine 0.1.6 워크스페이스에는 25개의 uqa-* 크레이트가 있습니다. 하지만 이런 모듈화는 책임의 경계를 나누는 것이며, 독립적인 쿼리 엔진을 모아 놓은 것이 아닙니다. 컴파일된 모든 문장은 하나의 최상위 경로를 따릅니다.

UnifiedPlan은 쿼리와 명령 계획을 빠짐없이 표현하는 합 타입입니다. 쿼리 블록은 관계형 행 경로, 특화된 OperatorTree 경로, 포스팅과 잔여 조건을 결합한 하이브리드 경로 중 하나를 선택합니다. 특화된 실행 결과도 합 타입으로 표현하며, 일반 PostingList, GraphPostingList, 튜플을 보존하는 GeneralizedPostingList 중 하나를 반환합니다.

이론에서 구분한 경계는 코드 검토와 실행 과정에 다음과 같이 반영됩니다.

이 핵심 구조를 중심으로 전용 크레이트가 분석, 저장, 점수 계산, 융합, 그래프 처리, 조인, 계획, 물리적 실행, PostgreSQL 지향 프런트엔드, 엔진 파사드, CLI, HTTP 클라이언트, Rust·Python·Node.js·브라우저 WASM 바인딩을 담당합니다. 시스템은 메모리에서 시작해 SQLite나 redb로 영속화할 수도 있고, 같은 형태의 SQL을 로컬 또는 Cloud UQA 데이터 플레인으로 보낼 수도 있습니다.

경계를 통과하는 쿼리

저장소에서 실행할 수 있는 unified-search 예제는 하나의 엔진 세션 안에서 논문 테이블, GIN 텍스트 인덱스, 벡터 인덱스, 인용 그래프, 사용자 정의 함수를 만듭니다. 하이브리드 쿼리는 일반적인 SQL입니다.

SELECT id, title, _score
FROM papers
WHERE text_match(abstract, 'retrieval ranking')
  AND knn_match(embedding, ARRAY[1.0, 0.0, 0.0], 4)
ORDER BY _score DESC, id ASC
LIMIT 4;

이 논리곱 조건은 하나의 실행 계획 안에서 함께 처리됩니다. 플래너는 같은 릴레이션에서 호환되는 텍스트와 벡터 신호를 인식하고, 이를 연산자 대수로 변환하고, 정확한 융합 계약을 적용한 뒤, 사영과 결정적 정렬을 위해 순위가 부여된 지지집합을 관계형 경계로 반환합니다.

같은 예제는 시스템 간 식별자 변환 없이 순위가 부여된 행에서 인용 그래프 탐색으로 이어집니다.

SELECT p.id, p.title, p.venue, p.year
FROM papers AS p
JOIN cypher('citations', $$
    MATCH (:Paper {paper_id: 3})-[:CITES]->(cited:Paper)
    RETURN cited.paper_id
$$) AS cited(id int)
  ON p.id = cited.id
ORDER BY p.year DESC, p.id ASC;

여기서 cypher(...)는 타입이 있는 테이블 소스입니다. 양쪽 모두 실제 식별 정보와 스키마를 유지하므로 그 출력을 일반 SQL 행과 조인할 수 있습니다. 애플리케이션에서 후보를 복사하거나 ID를 맞출 필요가 없습니다.

전체 시나리오는 다음과 같이 실행할 수 있습니다.

git clone https://github.com/cognica-io/uqa-engine.git
cd uqa-engine
cargo run -p example-unified-search --locked

현재 저장소에는 Rust 1.90 이상이 필요합니다. 이 글을 위해 0.1.6 체크아웃에서 예제를 실행하여, 한 세션 안에서 어휘 기반 및 베이지안 점수 계산, KNN, 자동으로 적용되는 정확한 융합, 강건한 풀링, 타입 기반 연산자 조인, 호스트 함수, Cypher 합성, 마지막으로 여러 패러다임을 아우르는 쿼리를 확인했습니다.

주장마다 그에 맞는 검증 근거가 필요합니다

논문은 대수적 성질을 성능 우수성의 근거로 내세우지 않으며, 프로젝트 역시 각 주장을 구분하고 그에 맞는 근거로 검증합니다.

이런 원칙은 하나의 성공적인 테스트가 다른 속성의 근거로 쓰이는 것을 막습니다. 보정된 점수가 근사 최근접 이웃(ANN) 검색의 재현율을 증명하지는 않습니다. ANN 재현율이 트랜잭션 내구성을 증명하지도 않습니다. 벤치마크가 대수적 재작성의 타당성을 증명하지도 않습니다. 각 주장에는 고유한 판정 기준이 있습니다.

적용 범위와 한계도 설계의 일부입니다

UQA Engine이 다루는 범위는 넓지만, 논문과 프로젝트 모두 근거가 뒷받침하는 범위를 넘어 주장하지 않습니다.

• 대수는 유한하고 고정된 스냅샷 위에서 정의됩니다. 분산 실행은 현재 핵심 범위 밖에 있습니다.
• SQL 인터페이스는 PostgreSQL을 지향합니다. 임베디드 엔진이 PostgreSQL 서버를 완전히 복제한다는 뜻은 아닙니다.
• IVF와 HNSW는 설계상 근사 방식이며, 그 품질은 문서군과 매개변수에 따라 달라집니다.
• 값이 $[0,1]$ 범위에 있다고 해서 자동으로 보정된 것은 아닙니다. 모델이나 후보 풀이 바뀌면 다시 평가해야 합니다.
• 일반적인 그래프 패턴 매칭과 제약 없는 경로 열거에는 본래의 복잡도가 그대로 남습니다.
• 0.1.6 버전은 활발히 개발 중이므로, 안정 버전 출시 전까지 공개 API와 저장 형식이 바뀔 수 있습니다.

이는 아키텍처를 만든 뒤 덧붙인 주의사항이 아닙니다. 차이를 감추지 않고 보존한다는 타입 기반 캐리어의 원칙에서 나온 결과입니다.

UQA가 "하나의 데이터베이스"에 가져오는 변화

UQA Engine의 가장 중요한 특성은 긴 기능 목록을 구현한다는 점이 아닙니다. 각 기능의 정확성을 뒷받침하는 의미론을 유지하면서도, 하나의 옵티마이저에서 함께 최적화할 수 있다는 점입니다.

관계형 행은 행으로 남습니다. 텍스트 매칭 결과는 위치와 원시 점수를 담을 수 있습니다. 벡터 후보는 어떤 인덱스에서 나왔는지에 관한 정보를 유지합니다. 그래프 매칭 결과는 그래프 맥락을 유지합니다. 조인은 양쪽의 식별 정보를 유지합니다. 사후확률은 증거와 사전확률의 구분을 유지합니다. 플래너가 이들을 합성할 수 있는 이유는 모든 값을 같은 형태로 평탄화했기 때문이 아니라 경계가 명시적이기 때문입니다.

이것이 타입 기반 캐리어 대수의 실용적인 의미입니다. 하나의 런타임에서 서로 다른 의미론을 충실히 유지하고, 최적화 법칙은 성립이 증명된 곳에 정확히 적용하는 것입니다.

더 읽어보기

• A Typed Carrier Algebra for Unified Query Execution
• UQA Engine 소스 코드와 매뉴얼
• A Unified Mathematical Framework for Query Algebras Across Heterogeneous Data Paradigms
• Extending the Unified Mathematical Framework to Support Graph Data Structures
• A Unified Bayesian Framework for Hybrid Search