Every database textbook teaches that hash joins are faster than sort-merge joins for large tables, and that in-memory aggregation outperforms disk-based spilling. These performance relationships hold when the query executor has sufficient memory. They catastrophically invert when memory is scarce—a hash join that overflows to disk can be orders of magnitude slower than a sort-merge join that fits in memory.

In production database systems, memory is shared among concurrent queries, background processes, and the operating system. The amount of memory available to any single query fluctuates continuously as other workloads start and stop. A query plan chosen at optimization time based on assumed memory availability may become suboptimal—or catastrophically slow—by the time it executes, because memory conditions have changed.

Otaki et al. address this with resource-adaptive query execution: a runtime system that monitors available memory and dynamically adjusts query algorithms as memory pressure changes. Rather than choosing a single execution plan at compilation time and hoping memory conditions hold, the adaptive executor maintains the ability to switch strategies mid-execution—transitioning from hash-based to sort-based algorithms when memory shrinks, or upgrading to hash-based algorithms when memory becomes available.

The Performance Cliff Problem

The performance cliff occurs at the transition from in-memory to disk-spilling execution. A hash join operating entirely in memory might process a million rows per second. The same hash join, when its hash table exceeds available memory and spills partitions to disk, might process only thousands of rows per second—a performance degradation of 100x or more.

Traditional database systems attempt to prevent spilling through careful memory allocation: the optimizer estimates memory requirements, the memory manager reserves appropriate amounts, and queries proceed with their allocated budgets. This works when memory estimation is accurate and workloads are predictable. It fails when:

• Multiple large queries arrive simultaneously, each expecting full memory availability
• Memory estimation is inaccurate (common for queries with complex predicates or skewed data)
• Background processes (compaction, index maintenance, statistics gathering) consume memory unpredictably

The resource-adaptive approach accepts that memory availability is inherently unpredictable and builds adaptation into the execution engine itself.

Paged Memory Management for Queries

The paging mechanism adapts the operating system's virtual memory concept to query execution. Query execution operators (joins, aggregations, sorts) are implemented with paged memory interfaces that:

Allocate incrementally: Rather than requesting a large contiguous memory block upfront, operators allocate memory in small pages as needed

Release gracefully: When memory pressure is detected, operators can release pages without aborting—they continue execution with reduced memory by switching to more memory-efficient (but slower) algorithms

Adapt continuously: The executor monitors system-wide memory pressure and sends signals to operators, allowing them to adjust their memory consumption in real time

Dynamic Programming for Plan Selection

Kozlova & Filippov provide a complementary perspective from PostgreSQL's query optimizer, which uses dynamic programming to select query plans from an exponentially large space of possibilities. Their analysis of how PostgreSQL's optimizer navigates the join ordering problem—considering memory, I/O, and CPU costs simultaneously—reveals both the sophistication of modern query planners and their limitations when runtime conditions diverge from planning-time assumptions.

The connection to resource-adaptive execution is direct: even the best plan selected by dynamic programming at optimization time becomes suboptimal when runtime memory conditions differ from the optimizer's assumptions. Adaptive execution addresses this gap by maintaining multiple viable strategies and switching between them as conditions change.

Claims and Evidence

<

Claim	Evidence	Verdict
Memory scarcity causes catastrophic query performance degradation	Well-documented in database systems literature and production experience	✅ Well-established
Resource-adaptive execution prevents performance cliffs	Otaki et al. demonstrate graceful degradation under memory pressure	✅ Supported
Paged memory management reduces peak memory requirements	Incremental allocation avoids large upfront reservations	✅ Supported
Adaptation overhead is negligible compared to spill penalty	Monitoring and switching cost is small relative to disk I/O cost	✅ Supported
Current production databases implement full resource adaptation	Most databases use static memory allocation with limited adaptation	❌ Not yet mainstream

Open Questions

Adaptation granularity: Should operators adapt individually or should the executor coordinate adaptation across all concurrent operators? Individual adaptation is simpler but may lead to oscillation; coordinated adaptation is more stable but more complex.

Prediction vs. reaction: Should the system predict memory pressure before it occurs (using workload forecasting) or react after it is detected? Prediction enables proactive adaptation but requires accurate workload models.

User expectations: If a query plan adapts mid-execution, the query's resource consumption and latency become unpredictable. How do we set user expectations and provide progress estimates for adaptive queries?

Cloud cost implications: In cloud databases where users pay per resource-second, adaptive execution that uses more CPU to compensate for less memory affects billing. How should adaptive resource usage be priced?

What This Means for Your Research

For database systems researchers, resource-adaptive execution is a promising direction that aligns query execution with the reality of shared, variable-resource environments. The gap between static planning and dynamic execution represents an opportunity for significant practical impact.

For data engineers managing analytics workloads, the key insight is that memory configuration is not just a one-time tuning task—it is a dynamic resource that requires continuous management. Systems that adapt to memory pressure will increasingly outperform those that assume fixed allocations.

면책 조항: 이 게시물은 정보 제공 목적의 연구 동향 개요이다. 학술 저작물에서 인용하기 전에 원본 논문을 통해 특정 연구 결과, 통계 및 주장을 검증해야 한다.

페이지 메모리와 쿼리 실행의 만남: 부하 상황에서의 분석 워크로드를 위한 적응형 자원 관리

모든 데이터베이스 교재는 대용량 테이블에서 hash join이 sort-merge join보다 빠르며, 인메모리 집계(aggregation)가 디스크 기반 스필링(spilling)보다 우수하다고 가르친다. 이러한 성능 관계는 쿼리 실행기에 충분한 메모리가 있을 때 성립한다. 그러나 메모리가 부족할 때는 이 관계가 파국적으로 역전된다—디스크로 오버플로우되는 hash join은 메모리에 맞는 sort-merge join보다 수십 배 이상 느려질 수 있다.

프로덕션 데이터베이스 시스템에서 메모리는 동시 실행 쿼리, 백그라운드 프로세스, 그리고 운영 체제 간에 공유된다. 단일 쿼리에서 사용 가능한 메모리의 양은 다른 워크로드가 시작되고 중단됨에 따라 지속적으로 변동한다. 최적화 시점에 가정된 메모리 가용성을 기반으로 선택된 쿼리 플랜은, 메모리 조건이 변화했을 때 실행 시점에서 차선책이 되거나—혹은 파국적으로 느려질 수 있다.

Otaki et al.은 이 문제를 자원 적응형 쿼리 실행(resource-adaptive query execution)으로 해결한다: 가용 메모리를 모니터링하고 메모리 압박이 변화함에 따라 쿼리 알고리즘을 동적으로 조정하는 런타임 시스템이다. 컴파일 시점에 단일 실행 플랜을 선택하고 메모리 조건이 유지되기를 기대하는 대신, 적응형 실행기는 실행 중에 전략을 전환하는 능력을 유지한다—메모리가 줄어들면 해시 기반 알고리즘에서 정렬 기반 알고리즘으로 전환하거나, 메모리가 확보되면 해시 기반 알고리즘으로 업그레이드한다.

성능 절벽 문제

성능 절벽은 인메모리 실행에서 디스크 스필링 실행으로 전환되는 지점에서 발생한다. 완전히 메모리 내에서 동작하는 hash join은 초당 백만 행을 처리할 수 있다. 동일한 hash join이라도 해시 테이블이 가용 메모리를 초과하여 파티션을 디스크로 스필링하면, 초당 수천 행만 처리할 수 있다—100배 이상의 성능 저하이다.

전통적인 데이터베이스 시스템은 신중한 메모리 할당을 통해 스필링을 방지하려 한다: 최적화기가 메모리 요구량을 추정하고, 메모리 관리자가 적절한 양을 예약하며, 쿼리는 할당된 예산으로 진행된다. 이는 메모리 추정이 정확하고 워크로드가 예측 가능할 때 효과적이다. 다음과 같은 경우에는 실패한다:

• 여러 대형 쿼리가 동시에 도착하여 각각 전체 메모리 가용성을 기대하는 경우
• 메모리 추정이 부정확한 경우 (복잡한 조건자(predicate)나 데이터 편향이 있는 쿼리에서 흔함)
• 백그라운드 프로세스(압축(compaction), 인덱스 유지보수, 통계 수집)가 예측 불가능하게 메모리를 소비하는 경우

자원 적응형 접근 방식은 메모리 가용성이 본질적으로 예측 불가능하다는 것을 받아들이고, 적응 기능을 실행 엔진 자체에 내장한다.

쿼리를 위한 페이지 메모리 관리

페이징(paging) 메커니즘은 운영 체제의 가상 메모리 개념을 쿼리 실행에 적용한 것이다. 쿼리 실행 연산자(join, aggregation, sort)는 다음과 같은 페이지 메모리 인터페이스로 구현된다:

점진적 할당: 미리 대용량의 연속적인 메모리 블록을 요청하는 대신, 연산자는 필요에 따라 작은 페이지 단위로 메모리를 할당한다

우아한 해제: 메모리 압박이 감지되면, 연산자는 실행을 중단하지 않고 페이지를 해제할 수 있다—더 메모리 효율적인(그러나 느린) 알고리즘으로 전환하여 감소된 메모리로 실행을 계속한다

지속적 적응: 실행기는 시스템 전체의 메모리 압박을 모니터링하고 연산자에게 신호를 보내어, 실시간으로 메모리 소비를 조정할 수 있게 한다

플랜 선택을 위한 동적 프로그래밍

Kozlova & Filippov는 PostgreSQL의 쿼리 옵티마이저 관점에서 보완적인 시각을 제시한다. PostgreSQL의 쿼리 옵티마이저는 동적 프로그래밍(dynamic programming)을 사용하여 지수적으로 방대한 가능성의 공간에서 쿼리 계획을 선택한다. PostgreSQL 옵티마이저가 조인 순서 결정 문제(join ordering problem)를 탐색하는 방식—메모리, I/O, CPU 비용을 동시에 고려하는—에 대한 분석은 현대 쿼리 플래너의 정교함과 함께, 런타임 조건이 계획 수립 시점의 가정에서 벗어날 때 나타나는 한계를 드러낸다.

리소스 적응형 실행(resource-adaptive execution)과의 연관성은 직접적이다. 최적화 시점에 동적 프로그래밍으로 선택된 최선의 계획도, 런타임 메모리 조건이 옵티마이저의 가정과 달라지면 최적이 아닌 상태가 된다. 적응형 실행은 복수의 실행 가능한 전략을 유지하고, 조건이 변화함에 따라 전략 간 전환을 수행함으로써 이 격차를 해소한다.

주장과 근거

<

주장	근거	판정
메모리 부족은 쿼리 성능의 급격한 저하를 야기한다	데이터베이스 시스템 문헌 및 실제 운영 경험에서 충분히 문서화됨	✅ 충분히 확립됨
리소스 적응형 실행은 성능 절벽을 방지한다	Otaki 등은 메모리 압박 하에서의 점진적 성능 저하를 실증함	✅ 지지됨
페이지 기반 메모리 관리는 최대 메모리 요구량을 줄인다	증분 할당(incremental allocation)은 대규모 선행 예약을 회피함	✅ 지지됨
적응 오버헤드는 스필(spill) 패널티에 비해 무시할 수 있는 수준이다	모니터링 및 전환 비용은 디스크 I/O 비용에 비해 작음	✅ 지지됨
현재 상용 데이터베이스는 완전한 리소스 적응을 구현한다	대부분의 데이터베이스는 제한적인 적응 기능을 갖춘 정적 메모리 할당을 사용함	❌ 아직 주류가 아님

미해결 질문

적응 단위(Adaptation granularity): 연산자가 개별적으로 적응해야 하는가, 아니면 실행기(executor)가 모든 동시 실행 연산자에 걸쳐 적응을 조율해야 하는가? 개별 적응은 단순하지만 진동(oscillation)으로 이어질 수 있고, 조율된 적응은 더 안정적이지만 더 복잡하다.

예측 대 반응(Prediction vs. reaction): 시스템이 메모리 압박을 발생 전에 예측해야 하는가(워크로드 예측 사용), 아니면 감지된 후에 반응해야 하는가? 예측은 선제적 적응을 가능하게 하지만 정확한 워크로드 모델을 필요로 한다.

사용자 기대치(User expectations): 쿼리 계획이 실행 도중 적응하면, 쿼리의 리소스 소비와 지연 시간이 예측 불가능해진다. 적응형 쿼리에 대해 사용자 기대치를 어떻게 설정하고 진행 상황 추정치를 제공할 것인가?

클라우드 비용 영향(Cloud cost implications): 사용자가 리소스-초(resource-second) 단위로 비용을 지불하는 클라우드 데이터베이스에서, 메모리 감소를 CPU로 보완하는 적응형 실행은 청구에 영향을 미친다. 적응형 리소스 사용은 어떻게 과금해야 하는가?

연구에 대한 시사점

데이터베이스 시스템 연구자에게 있어, 리소스 적응형 실행은 공유되고 가변적인 리소스 환경의 현실에 쿼리 실행을 부합시키는 유망한 방향이다. 정적 계획과 동적 실행 사이의 격차는 상당한 실질적 영향을 줄 수 있는 기회를 나타낸다.

분석 워크로드를 관리하는 데이터 엔지니어에게 있어, 핵심 통찰은 메모리 구성이 단순한 일회성 튜닝 작업이 아니라 지속적인 관리를 필요로 하는 동적 리소스라는 점이다. 메모리 압박에 적응하는 시스템은 고정 할당을 가정하는 시스템보다 점점 더 우수한 성능을 발휘하게 될 것이다.