arXiv:2610.08089v2 cs.DB

실행 계획이 결과를 바꿀 때: 시맨틱 쿼리를 위한 비용-정확도 최적화 공식화

When Plans Change Answers: Formalizing Cost-Accuracy Optimization for Semantic Queries

Kyoungmin Kim

제출 2026-10-06

한국어 초록

시맨틱 쿼리 엔진에서는 머신러닝 모델을 통해 술어(predicate)가 평가되므로, 쿼리 실행 계획의 선택이 쿼리 비용뿐만 아니라 그 결과에도 영향을 미칩니다. 기존 시스템들은 조인을 거치며 오차가 어떻게 전파되는지 고려하지 않은 채, 각 시맨틱 연산자에 고정된 임계값을 적용하거나 연산자별로 정확도를 튜닝합니다. 본 논문에서는 이러한 쿼리에 대한 비용-정확도 최적화 문제를 공식적으로 정의합니다. 우리의 출발점은 Jev와 같은 의사결정 모델이 각 결정에 부여하는 보정된 신뢰도(calibrated confidence)입니다. 이는 모든 결정에 대한 기대 오차를 산출하며, 각 결정이 출력에 미치는 기여도(가장 단순한 경우 팬아웃(fan-out))로 이 오차들에 가중치를 부여하면 레이블이 지정된 데이터 없이도 계획의 기대 출력 품질을 얻을 수 있습니다. 또한 동일한 계산을 역으로 수행하면 출력 수준의 정확도 목표를 각 기본 튜플 또는 중간 튜플에 대한 비용으로 변환할 수 있습니다. 이를 바탕으로 우리는 시맨틱 연산자를 포함하는 관계 대수를 위한 오라클 의미론, 논리적 계획과 결정 정책의 쌍으로 이루어진 물리적 계획, 선언적 출력 수준 목표, 그리고 계획 동등성 계층 구조를 정의합니다. 우리는 점별 결정론적(pointwise-deterministic) 정책 하에서는 정확도가 계획에 불변함을 보이고, 승격 대역(escalation band)이 계획 자체의 후보군에 맞춰 보정될 때 셀렉션 푸시다운(selection pushdown)이 품질 건전성(quality-soundness)을 보장하지 않음을 보입니다. 기대 품질은 백 의미론(bag semantics) 하에서는 다항 시간에 계산될 수 있으며, 세트 의미론(set semantics) 하에서는 모든 릴레이션이 시맨틱 술어를 가질 때 튜플 독립적 확률적 데이터베이스의 이분법을 따릅니다. 어떤 튜플을 삭제할지 선택하는 것은 NP-난해인 반면, 최적화 문제는 두 개의 라그랑주 승수를 통해 튜플별 결정으로 분해되며, 우리가 신뢰도 중심 건너뛰기(confidence-centric skipping)라고 부르는 기법을 통해 목표에 더 이상 영향을 미치지 않는 튜플은 점수를 매기지 않고 건너뜁니다. 합성 워크로드에 대한 시뮬레이션은 이러한 효과들을 보여주며, 실제 엔진에서의 평가는 향후 과제로 남겨둡니다.

원문 초록

In semantic query engines, predicates are evaluated by machine-learned models, and the choice of a query plan affects not only the cost of a query but also its result. Existing systems either apply a fixed threshold to each semantic operator or tune accuracy per operator, without accounting for how errors propagate through joins. We give a formal problem definition for cost-accuracy optimization of such queries. Our starting point is the calibrated confidence that decision models such as Jev attach to each decision. It yields an expected error for every decision; weighting these errors by each decision's contribution to the output (in the simplest case, its fan-out) gives the expected output quality of a plan without any labeled data, and the same computation in reverse turns an output-level accuracy target into a price on each base or intermediate tuple. Building on this, we define an oracle semantics for relational algebra with semantic operators, physical plans as pairs of a logical plan and a decision policy, declarative output-level targets, and a hierarchy of plan equivalence. We show that accuracy is plan-invariant under pointwise-deterministic policies, and that selection pushdown is not quality-sound when escalation bands are calibrated on the plan's own candidates. Expected quality can be computed in polynomial time under bag semantics; under set semantics it follows the dichotomy of tuple-independent probabilistic databases when every relation carries a semantic predicate. Choosing which tuples to drop is NP-hard, while the optimization problem decomposes into per-tuple decisions through two Lagrange multipliers, and, with what we call confidence-centric skipping, tuples that can no longer affect the target are skipped without being scored. Simulations on a synthetic workload illustrate these effects; an evaluation on real engines is left for future work.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2610.08089v2
  2. arXiv:2610.08089v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2606.03946v2cs.DB공통 태그 query optimization

MLSkip: 경량 메타데이터를 통한 ML 필터용 데이터 스킵핑

MLSkip: Data Skipping for ML Filters via Lightweight Metadata

데이터베이스 벤더들이 최근 필터 predicate에서 사용할 수 있는 AI 함수를 출시했다. 이러한 함수는 종종 비용이 큰 블랙박스 ML 모델에 의존하므로 새로운 데이터 관리 과제를 드러낸다. 구체적으로, 정수 및 문자열 데이터에 대한 기존 데이터 스킵핑 기법은 새로운 필터 유형에는 적용되지 못한다. 실제로 blob storage에서 파일을 읽을 때와 같이, 조건을 만족하지 않는 row group을 가지치기할 알려진 메커니즘이 없다. 본 연구에서는 ML 필터를 위한 데이터 스킵핑 기법 연구를 시작한다. Parquet의 기본 min-max 메타데이터만으로도 가지치기를 가능하게 하기에 충분하다고 주장한다. 이를 위해 (i) 최근 제안된 ML 모델용 쿼리 언어와 (ii) 신경망 검증이라는 두 연구 계열과의 연관을 맺는다. 렐루 아키텍처에 대한 예비 결과는 TPC-H 및 TPC-DS의 테이블에서 선택도가 0.1% 미만인 필터에 대해 평균 가지치기 효과가 27.4%에 달함을 보여준다. 마지막으로 공간 조인 연구에서 영감을 받아 향상된 메타데이터 구조, 즉 검증 도구가 더 잘 활용할 수 있는 크기 제한 2D 볼록 껍질(convex hull)을 제안하며, row group 및 column pair당 최대 45바이트만 차지하면서 가지치기 효과를 38.31%로 높인다. DuckDB에서 PyTorch 대비 end-to-end 속도 향상 1.07$\times$를 관측한다.

arXiv:2607.21756v1cs.DB공통 태그 query optimization

프롬프트를 데이터 타입으로: 데이터베이스 내 LLM 프롬프트 관리 및 재작성

Prompt as a Data Type: In-Database LLM Prompt Management and Rewriting

대규모 언어 모델(LLM)은 데이터베이스 기반 애플리케이션에서 튜플 분류, 의미적 술어를 이용한 레코드 필터링, 구조화된 속성 추출, 쿼리 결과 보강 등에 점점 더 많이 사용되고 있다. 그러나 이러한 연산을 시작하는 프롬프트는 일반적으로 DBMS 외부의 비구조화 형식으로 저장되어, 쿼리 실행, 메타데이터 관리, 최적화에 보이지 않게 된다. Stonebraker의 'QUEL as a Data Type'과 반성적 프로그래밍(reflective programming) 원칙에 기초하여, 본 논문은 프롬프트를 튜플 수준의 데이터베이스 값으로 취급하는 데이터베이스 시스템 PromptDB를 소개한다. PromptDB는 템플릿, 튜플 속성에 대한 바인딩, 모델 메타데이터, 태스크 메타데이터를 저장하는 논리적 PROMPT 데이터 타입을 제공한다. 릴레이션은 기본 테이블에 PROMPT 속성을 직접 포함하거나, 조인된 튜플에 대한 뷰를 통해 이를 노출할 수 있다. 사용자는 생성된 평가 뷰를 통해 프롬프트 값 속성을 쿼리하고, 시스템은 내부적으로 EVAL 연산자를 통해 프롬프트를 렌더링, 재작성, 최적화, 실행한다. 프롬프트를 데이터베이스에서 볼 수 있게 하면 새로운 최적화 공간이 생긴다. 핵심 아이디어는 옵티마이저 사고방식을 프롬프트에 가져오는 것이다. 쿼리 옵티마이저가 데이터베이스 메타데이터를 활용해 SQL 계획을 재작성하는 것처럼, PromptDB는 데이터베이스 메타데이터를 활용해 프롬프트를 재작성한다. 다양한 태스크에 걸친 합성 및 실제 데이터 워크로드에서 PromptDB를 평가했다. 결과는 데이터베이스 기반 재작성이 출력 유효성을 어떻게 개선하고, 정적·수동 작성 프롬프트에 비해 유리한 비용-품질 트레이드오프를 제공하는지 보여준다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.