대규모 언어 모델(LLMs)에서 환각을 줄이기 위해, 연구자들은 LLM을 외부 지식 그래프(KG)와 통합하는 추론 방법에 대해 점점 더 많은 연구를 수행하고 있다.기존 접근법은 LLM이 생성한 질의 그래프를 KG에 매핑하거나, LLM이 전체 그래프를 순회하도록 하는 방식 중 하나에 해당한다. 전자는 노이즈가 포함된 질의 그래프가 검색을 방해한다는 점에서 취약한 반면, 후자는 대규모 그래프에 대한 엔터티 수준 추론을 수행해야 하므로 비효율적이다.이러한 문제를 해결하기 위해, 우리는 지식 그래프 질의를 효율적으로 수행하기 위한 스키마 그래프 기반 근사 거리 조인(SAFE, Schema-Driven Approximate Distance Join)을 제안한다. 이 프레임워크는 견고한 질의 그래프 생성을 위해 스키마 그래프를 활용하고, KG 검색을 효율적으로 수행한다.SAFE는 두 가지 핵심 아이디어를 도입한다.(1) LLM이 생성한 의사 질의 그래프(pseudo query graphs)를 KG의 구조에 유연하게 정렬함으로써 정제하는 근사 거리 조인(ADJ, Approximate Distance Join) 알고리즘, 그리고 (2) 간결한 스키마 그래프를 활용하여 ADJ를 효율적으로 수행함으로써 오버헤드를 줄이고 검색 정확도를 향상시키는 접근이다. WebQSP, CWQ, GrailQA에 대한 광범위한 실험 결과, SAFE는 정확도와 효율성 모두에서 최신 기술 수준의 방법을 능가하며, LLM 기반 지식 검색이 지니는 본질적 한계를 극복하기 위한 견고하고 확장 가능한 해결책을 제공하는 것으로 나타났다.

부분그래프 카운팅은 그래프 구조화 데이터의 이해와 분석에 있어 근본적인 문제이지만, 계산적으로 매우 어렵다. 이에 따라 질의 그래프의 모든 동형 임베딩(isomorphic embeddings) 개수를 데이터 그래프에서 추정하는 부분그래프 차수(Subgraph Cardinality Estimation)를 위한 정확하고 효율적인 알고리즘이 요구된다. 우리는 (1) 표본 공간(sample space)을 크게 줄이기 위한 강력한 필터링 기법, (2) 정확하고 효율적인 추정을 위한 적응형 트리 샘플링(adaptive tree sampling) 알고리즘, (3) 어려운 인스턴스에 대한 최악의 경우(worst-case) 최적화된 층화 그래프 샘플링(stratified graph sampling) 알고리즘을 결합한 새로운 알고리즘 FaST est 를 제안한다. 실제 세계 데이터셋에 대한 광범위한 실험 결과, FaST est 는 정확도 측면에서 기존의 샘플링 기반 최신 방법을 최대 2자릿수(orders of magnitude)까지, 그리고 GNN 기반 방법을 최대 3자릿수까지 능가하는 것으로 나타났다.

JSON 표현 형식의 주요 장점 중 하나인 스키마리스(schemalessness)는, 쿼리 최적화, 인덱싱 또는 데이터 검증과 같은 다양한 핵심 기능을 배제함으로써 검색 및 연산에서 높은 대가를 수반한다. JSON 문서의 묶음으로부터 정확한 JSON 스키마 발견 알고리즘을 개발하기 위한 노력이 지속되어 왔다. 그러나 기존 스키마 발견 기법들은 상향식이 아닌 하향식(top-down) 알고리즘에 기반하고 있어, JSON 트리의 자식 노드에 대한 가시성이 부족하다는 문제에 직면한다. 하위 수준의 JSON 요소에 대한 정보가 부재한 경우, 하향식 알고리즘은 노드의 스키마 유형을 결정하기 위해 가정과 휴리스틱을 활용해야 한다. 하지만 이러한 정적 결정은 데이터셋에서 종종 위반되며, 그 결과 하향식 알고리즘의 성능이 저하된다. 이를 극복하기 위해 우리는 JSON 문서를 하향식이 아닌 하향(bottom-up) 방식으로 처리하는 ReCG라는 알고리즘을 제안한다. 이 알고리즘은 JSON 문서 트리에서 리프(leaf) 요소로부터 위로 스키마를 구축함으로써, 스키마 노드 유형에 대해 보다 정보에 기반한 결정을 내릴 수 있다. 또한 스키마를 구축하는 과정에서 MDL(최소 기술 길이, Minimum Description Length) 원칙을 체계적으로 적용하여, 후보 스키마들 중 일반성(generality)은 적절히 균형을 이루면서도 가장 간결하면서도 정확한 스키마를 선택한다. 평가는, 제안 기법이 발견된 스키마의 재현율과 정밀도를 최대 47%까지 향상시키며, 그로 인해 F1 점수가 46% 더 개선되는 동시에 최신 기술 대비 평균 2.11배 더 빠른 성능을 보임을 나타낸다.

GPU 가속 관계형 질의 실행 엔진은 연산자들의 연속인 파이프라인의 실행을 병렬화한다. 이를 위해 엔진은 파이프라인의 첫 연산자(스캔)가 스캔할 테이블의 튜플을 균등하게 분할하고, 각 스레드는 해당 분할에 속한 튜플에 대해 파이프라인을 실행한다. 그러나 이 접근법은 연산자가 입력 튜플당 서로 다른 수의 출력 튜플을 반환하기 때문에, 특히 치우친 조인 키 값과 같은 비균일한 데이터 분포 하에서 부하 불균형을 초래한다. 이러한 부하 불균형은 1) 스레드가 워프(warp)로 묶이고 2) 단일 명령-다중 스레드(single-instruction-multiple-thread) 방식에 따라 워프 내의 모든 스레드가 입력 튜플에 대해 동일한 연산자를 동시 평가하기 때문에, 워프 내부 및 워프 간 부하 불균형(intra- and inter-warp load imbalances, intra-WLIs 및 inter-WLIs)으로 분류된다. 반면 워프가 다른 경우에는 스레드가 서로 다른 연산자를 동시에 평가할 수 있다. 부하 균형화 기법이 제안되었음에도 불구하고, 다양한 워크로드에서 이러한 부하 불균형을 해결하지 못한다. 본 논문에서는 공정성의 신을 따서 Themis로 명명한 질의 실행 엔진을 제안하며, 이는 우리의 맥락에서 균형 잡힌 워크로드를 상징한다. Themis는 다양한 워크로드에서 intra-WLIs 및 inter-WLIs를 최소화한다. 첫째, Themis는 워프 내 스레드 간에 튜플을 재분배하고, 모든 스레드가 입력을 보유한 경우에만 연산자를 평가하도록 하여 intra-WLIs를 최소화한다. 둘째, Themis는 부하가 큰 워프의 튜플을 유휴 워프로 재분배함으로써 inter-WLIs를 완화한다. 워프의 워크로드가 무거운지 확인하기 위해, 워프 워크로드의 크기를 근사하는 방법을 제안한다. 이러한 근사에 기초하여 Themis는 워프의 워크로드가 무거운 것으로 판정하기 위한 임계값을 적응적으로 조정한다. TPC-H에 치우친 조인 키 분포를 도입하는 최근 벤치마크 JCC-H에서, Themis는 inter-WLIs와 intra-WLIs를 유의하게 완화하여 2위 대비 최대 379배 더 나은 성능을 보인다.

데이터베이스 리플레이 시스템(DRS)은 운영 환경의 워크로드를 캡처한 뒤 테스트 환경에서 이를 재생(replay)하여 정확성과 성능을 검증한다. 리플레이 과정에 앞서 DRS는 워크로드로부터 의존성 그래프를 초기 생성하여 출력 결정성(determinism)을 보장하고 테스트 시스템에서의 리플레이 동시성(concurrency)을 최대화한다. 그러나 현존하는 최신 기술은 불필요하게 더 큰 의존성 그래프를 생성하는 비효율성을 보이며, 이로 인해 종단 간(end-to-end) 파이프라인에서 주요 병목이 발생한다. DoppelGanger++는 빠른 의존성 그래프 생성을 지원하는 새로운 DRS이다. 본 데모는 의존성 그래프를 효율적으로 간결(compact)하게 생성하는 데 중점을 두어, 워크로드를 캡처하고 재생하는 방법을 보여준다. 구체적으로, 우리는 전체 데이터베이스 리플레이 워크로드를 사용한 종단 간 데이터베이스 리플레이 워크플로를 시연하며, 의존성 그래프 생성 과정을 애니메이션하고 중요한 내부 데이터 구조를 시각화할 수 있는 데모용 웹 도구를 함께 제공한다.

학습된 카디널리티 추정기는 기계 학습 기법을 활용함으로써 추정 정확도에서 괄목할 만한 개선을 보였으나, 질의 최적화기에 배치될 경우 비효율적이거나 차선의 쿼리 계획을 초래하는 문제를 겪는다. ASM은 엔드투엔드 실행 시간 측면에서 기존 접근법을 유의하게 능가하는 새로운 학습 기반 카디널리티 추정기이다. 본 시연은 순차적(autoregressive) 모델, 샘플링, 다차원 통계 병합을 활용하는 내부 추정 과정을 보여주며, 그 성능을 다른 대안들과 비교한다. 이를 위해 추정 결과를 활용한 상세한 계획 공간 탐색을 시각화한다.

연속 부분그래프 매칭(CSM) 문제는 동적 그래프에서 패턴을 지속적으로 탐지하는 것을 목표로 하며, 사기 탐지와 같은 실제 응용 분야에 사용된다. CSM을 해결하기 위해 다수의 방법이 제안되었으나, 이들 방법 간의 공정한 비교가 이루어지지 못하고 있다. 또한, 기존의 CSM 통합 프레임워크는 하위 최적 구현으로 인해 오해의 소지가 있는 실험 결과를 보인다. 본 논문에서는 적층 뷰(stacked views)를 포함하는 delta 쿼리의 논리적 계획과 물리적 계획으로부터 CSM 코드를 생성하는 새로운 프레임워크를 제안한다. 각 CSM 방법을 delta 쿼리 계획으로 표현함으로써, 본 프레임워크는 CSM 방법들 간의 공정한 비교를 가능하게 한다. 포괄적인 실험을 통해, 선행 논문들에서 관찰된 성능 경향의 차이에 대한 원인-결과적 논증을 제시하고, 다양한 기법들이 전체 성능에 미치는 개별 영향을 추가로 분석한다. 구체적으로, 본 연구의 CSM 코드는 기존 방식의 하나에 대해, 최신 CSM 방법인 CaLiG보다 최대 48.6배까지 유의미하게 더 우수한 성능을 보인다.

데이터베이스 리플레이 시스템(DRS)은 운영 시스템에서 워크로드를 캡처한 뒤 테스트 시스템에서 이를 재생하여 다양한 시스템 변경을 검증함으로써, 프로덕션 환경에 적용하기 전 어떤 위험도 피할 수 있게 한다. DRS에서의 의존성 그래프 생성은 출력 결정성을 보존하면서 동시성을 최대화하는 데 있어 결정적으로 중요하다. 상용 DBMS에 배치된 최신 의존성 그래프 생성 알고리즘은 generate-and-prune(생성-가지치기) 전략을 사용한다. 이 알고리즘은 워크로드의 각 요청에 대해 역방향 스캔을 수행하여 먼저 의존성 그래프를 생성한 다음, 비용이 큰 순서(전이) 감소(transitive reduction) 알고리즘을 사용하여 모든 중복 간선을 제거(가지치기)한다. 그러나 우리는 이 과정에서 중복 간선을 다수 포함하는 큰 의존성 그래프가 생성되며, 최악의 시간 복잡도가 워크로드 내 요청 수에 대해 이차(quadratic)임을 관찰하였다. 이러한 난제를 해결하기 위해 우리는 DRS를 위한 네 가지 범주의 의존성 그래프를 형식적으로 제안한다. 이어서, SSFS(stateful single forward scan)라는 상태 기반 단일 정방향 스캔 알고리즘을 제시하여, 모든 요청에 대해 단 한 번의 스캔을 수행하면서 상태를 간결하게 유지함으로써 어떤 범주의 의존성 그래프든 생성할 수 있게 한다. 여기서 상태(state)는 효율적인 의존성 그래프 생성을 위해 저장되고 유지되는 정보를 의미한다. 또한 다중 코어 CPU의 연산 역량을 활용하면서 부하를 균형 있게 조절하기 위해 병렬 SSFS도 제안한다. 우리는 선도적인 상용 DBMS에 우리의 DRS를 구현하였다. TPC-C 및 SD 벤치마크와 실제 고객 워크로드를 사용한 광범위한 실험 결과, 우리의 DRS는 최신 기술과 비교하여 의존성 그래프 생성 시간을 최대 두 자릿수(2 orders of magnitude)까지 유의하게 향상시키는 것으로 나타났다.

대규모 언어 모델(LLMs)에서 환각을 줄이기 위해, 연구자들은 LLM을 외부 지식 그래프(KG)와 통합하는 추론 방법에 대해 점점 더 많은 연구를 수행하고 있다.기존 접근법은 LLM이 생성한 질의 그래프를 KG에 매핑하거나, LLM이 전체 그래프를 순회하도록 하는 방식 중 하나에 해당한다. 전자는 노이즈가 포함된 질의 그래프가 검색을 방해한다는 점에서 취약한 반면, 후자는 대규모 그래프에 대한 엔터티 수준 추론을 수행해야 하므로 비효율적이다.이러한 문제를 해결하기 위해, 우리는 지식 그래프 질의를 효율적으로 수행하기 위한 스키마 그래프 기반 근사 거리 조인(SAFE, Schema-Driven Approximate Distance Join)을 제안한다. 이 프레임워크는 견고한 질의 그래프 생성을 위해 스키마 그래프를 활용하고, KG 검색을 효율적으로 수행한다.SAFE는 두 가지 핵심 아이디어를 도입한다.(1) LLM이 생성한 의사 질의 그래프(pseudo query graphs)를 KG의 구조에 유연하게 정렬함으로써 정제하는 근사 거리 조인(ADJ, Approximate Distance Join) 알고리즘, 그리고 (2) 간결한 스키마 그래프를 활용하여 ADJ를 효율적으로 수행함으로써 오버헤드를 줄이고 검색 정확도를 향상시키는 접근이다. WebQSP, CWQ, GrailQA에 대한 광범위한 실험 결과, SAFE는 정확도와 효율성 모두에서 최신 기술 수준의 방법을 능가하며, LLM 기반 지식 검색이 지니는 본질적 한계를 극복하기 위한 견고하고 확장 가능한 해결책을 제공하는 것으로 나타났다.

부분그래프 카운팅은 그래프 구조화 데이터의 이해와 분석에 있어 근본적인 문제이지만, 계산적으로 매우 어렵다. 이에 따라 질의 그래프의 모든 동형 임베딩(isomorphic embeddings) 개수를 데이터 그래프에서 추정하는 부분그래프 차수(Subgraph Cardinality Estimation)를 위한 정확하고 효율적인 알고리즘이 요구된다. 우리는 (1) 표본 공간(sample space)을 크게 줄이기 위한 강력한 필터링 기법, (2) 정확하고 효율적인 추정을 위한 적응형 트리 샘플링(adaptive tree sampling) 알고리즘, (3) 어려운 인스턴스에 대한 최악의 경우(worst-case) 최적화된 층화 그래프 샘플링(stratified graph sampling) 알고리즘을 결합한 새로운 알고리즘 FaST est 를 제안한다. 실제 세계 데이터셋에 대한 광범위한 실험 결과, FaST est 는 정확도 측면에서 기존의 샘플링 기반 최신 방법을 최대 2자릿수(orders of magnitude)까지, 그리고 GNN 기반 방법을 최대 3자릿수까지 능가하는 것으로 나타났다.

JSON 표현 형식의 주요 장점 중 하나인 스키마리스(schemalessness)는, 쿼리 최적화, 인덱싱 또는 데이터 검증과 같은 다양한 핵심 기능을 배제함으로써 검색 및 연산에서 높은 대가를 수반한다. JSON 문서의 묶음으로부터 정확한 JSON 스키마 발견 알고리즘을 개발하기 위한 노력이 지속되어 왔다. 그러나 기존 스키마 발견 기법들은 상향식이 아닌 하향식(top-down) 알고리즘에 기반하고 있어, JSON 트리의 자식 노드에 대한 가시성이 부족하다는 문제에 직면한다. 하위 수준의 JSON 요소에 대한 정보가 부재한 경우, 하향식 알고리즘은 노드의 스키마 유형을 결정하기 위해 가정과 휴리스틱을 활용해야 한다. 하지만 이러한 정적 결정은 데이터셋에서 종종 위반되며, 그 결과 하향식 알고리즘의 성능이 저하된다. 이를 극복하기 위해 우리는 JSON 문서를 하향식이 아닌 하향(bottom-up) 방식으로 처리하는 ReCG라는 알고리즘을 제안한다. 이 알고리즘은 JSON 문서 트리에서 리프(leaf) 요소로부터 위로 스키마를 구축함으로써, 스키마 노드 유형에 대해 보다 정보에 기반한 결정을 내릴 수 있다. 또한 스키마를 구축하는 과정에서 MDL(최소 기술 길이, Minimum Description Length) 원칙을 체계적으로 적용하여, 후보 스키마들 중 일반성(generality)은 적절히 균형을 이루면서도 가장 간결하면서도 정확한 스키마를 선택한다. 평가는, 제안 기법이 발견된 스키마의 재현율과 정밀도를 최대 47%까지 향상시키며, 그로 인해 F1 점수가 46% 더 개선되는 동시에 최신 기술 대비 평균 2.11배 더 빠른 성능을 보임을 나타낸다.

GPU 가속 관계형 질의 실행 엔진은 연산자들의 연속인 파이프라인의 실행을 병렬화한다. 이를 위해 엔진은 파이프라인의 첫 연산자(스캔)가 스캔할 테이블의 튜플을 균등하게 분할하고, 각 스레드는 해당 분할에 속한 튜플에 대해 파이프라인을 실행한다. 그러나 이 접근법은 연산자가 입력 튜플당 서로 다른 수의 출력 튜플을 반환하기 때문에, 특히 치우친 조인 키 값과 같은 비균일한 데이터 분포 하에서 부하 불균형을 초래한다. 이러한 부하 불균형은 1) 스레드가 워프(warp)로 묶이고 2) 단일 명령-다중 스레드(single-instruction-multiple-thread) 방식에 따라 워프 내의 모든 스레드가 입력 튜플에 대해 동일한 연산자를 동시 평가하기 때문에, 워프 내부 및 워프 간 부하 불균형(intra- and inter-warp load imbalances, intra-WLIs 및 inter-WLIs)으로 분류된다. 반면 워프가 다른 경우에는 스레드가 서로 다른 연산자를 동시에 평가할 수 있다. 부하 균형화 기법이 제안되었음에도 불구하고, 다양한 워크로드에서 이러한 부하 불균형을 해결하지 못한다. 본 논문에서는 공정성의 신을 따서 Themis로 명명한 질의 실행 엔진을 제안하며, 이는 우리의 맥락에서 균형 잡힌 워크로드를 상징한다. Themis는 다양한 워크로드에서 intra-WLIs 및 inter-WLIs를 최소화한다. 첫째, Themis는 워프 내 스레드 간에 튜플을 재분배하고, 모든 스레드가 입력을 보유한 경우에만 연산자를 평가하도록 하여 intra-WLIs를 최소화한다. 둘째, Themis는 부하가 큰 워프의 튜플을 유휴 워프로 재분배함으로써 inter-WLIs를 완화한다. 워프의 워크로드가 무거운지 확인하기 위해, 워프 워크로드의 크기를 근사하는 방법을 제안한다. 이러한 근사에 기초하여 Themis는 워프의 워크로드가 무거운 것으로 판정하기 위한 임계값을 적응적으로 조정한다. TPC-H에 치우친 조인 키 분포를 도입하는 최근 벤치마크 JCC-H에서, Themis는 inter-WLIs와 intra-WLIs를 유의하게 완화하여 2위 대비 최대 379배 더 나은 성능을 보인다.