aggregation-optimization

分类: 数据库与数据存储 | 上传者: SolidLao | 下载: 0 | 版本: v1.0（最新）
Aggregation optimization for SQL queries with GROUP BY or aggregate functions (SUM, AVG, COUNT, MIN, MAX). Covers hash aggregation, sorted aggregation, thread-local merge, direct array lookup for low-cardinality groups, precision management for large-magnitude sums.
更新日志: Source: GitHub https://github.com/SolidLao/GenDB
目录结构

当前层级: .claude/skills/aggregation-optimization/
📄 SKILL.md 13.1 KB
SKILL.md

---
name: aggregation-optimization
description: Aggregation optimization for SQL queries with GROUP BY or aggregate functions (SUM, AVG, COUNT, MIN, MAX). Covers hash aggregation, sorted aggregation, thread-local merge, direct array lookup for low-cardinality groups, precision management for large-magnitude sums.
user-invocable: false
---

# Skill: Aggregation Optimization

## When to Load
Queries with GROUP BY or aggregate functions (SUM, AVG, COUNT, MIN, MAX).

## Algorithm Selection by Group Cardinality

These ranges are approximate guidelines. The actual crossover points depend on slot size (key + value bytes), cache hierarchy, and thread count. Always compute `groups × slot_size` and compare against cache levels.

| Group Cardinality (approx.) | Strategy | Notes |
|-----------------------------|----------|-------|
| Very low (flat array fits L1) | Direct flat array (if keys mappable to small int) | Zero hash, O(1) |
| Low (per-thread map fits L1/L2) | Direct array with lightweight hash or small hash map | Cache-resident per thread |
| Moderate (per-thread map fits LLC) | Thread-local hash tables + merge | See parallelism skill for thread-local sizing |
| High (total thread-local memory exceeds LLC) | Thread-local hash tables + partitioned merge, or scan-time partitioned aggregation | Evaluate Memory Budget Gate below |
| High cardinality + integer accumulator (groups >> threads) | Shared hash table with LOCK XADD (`__atomic_fetch_add`) | See Shared XADD Aggregation below |
| Very high (groups cannot be estimated) | Two-phase: sample to estimate, then partitioned | Memory management critical |

## Memory Budget Gate (MANDATORY — evaluate before choosing thread-local strategy)

Compute total memory: `total_agg_mem = nthreads × next_pow2(estimated_groups × 2) × slot_size_bytes`

Compare against hardware LLC (last-level cache) total capacity. Query the target machine's L3 size; do not assume a fixed number.

| total_agg_mem vs LLC | Strategy |
|---------------------|----------|
| ≤ LLC total | Per-thread hash maps (standard thread-local pattern) |
| > LLC total, per-partition map fits per-core cache | Per-thread maps + partitioned merge (see below) |
| > LLC total, per-partition map does NOT fit per-core cache | Strongly prefer scan-time partitioned aggregation (skip per-thread maps entirely) |
| > LLC total, integer accumulator AND groups >> nthreads | Shared XADD aggregation (single pass, no partition buffers) — see below |

The deciding factor is whether the working set (per-thread or per-partition) fits the relevant cache level. When it doesn't, initialization and merge costs dominate — this scales with total_agg_mem, not with any fixed byte threshold.

### Scan-Time Partitioned Aggregation
Instead of allocating T full-cardinality hash maps:
1. During scan: each thread maintains P partition buffers (vectors of key-value tuples)
2. Partition assignment: `pid = hash(key) & (P-1)`, where P = next_pow2(nthreads)
3. After scan barrier: thread t drains ALL T buffers for partition t into one small hash map
   sized to fit the per-core private cache (L2 typically)
4. Zero contention, no large per-thread maps, embarrassingly parallel merge

This replaces the T full-cardinality maps + post-scan merge pattern.
Relationship to C9: C9 applies to per-thread maps when they ARE used. When scan-time
partitioned aggregation eliminates per-thread maps, C9 does not apply to the append-only
partition buffers.

VIOLATION DIAGNOSTIC: If build_joins + aggregation_merge > 2× main_scan, the aggregation
strategy is wrong — re-evaluate using this Memory Budget Gate.

### Shared XADD Aggregation
When to use: integer accumulator (COUNT, SUM of int), groups significantly outnumber threads (low collision probability), key domain excludes 0 (0 used as empty sentinel).

Why it wins: single pass over data, no partition buffers, no per-thread maps, no merge phase. LOCK XADD (`__atomic_fetch_add`) is a single hardware instruction with no CAS retry loop — contention is negligible when groups far outnumber threads because concurrent threads rarely hit the same slot.

Pattern:
1. Allocate single shared hash table via `mmap(MAP_ANONYMOUS)` — zero-initialized (0 = empty)
2. Distributed prefault: each thread touches its share of pages in parallel before scan
3. Parallel scan: for each row, hash key → open-address probe → `__atomic_fetch_add(&slot.value, amount, __ATOMIC_RELAXED)` + software prefetch ahead to hide probe latency
4. After scan: linear sweep for non-zero slots; defer `munmap` to after output

Limitation: only works for integer accumulators (XADD). For floating-point, use CAS loop (Probe-Aggregate Fusion) or thread-local approaches.

## Precision Management for Aggregation

This is the authoritative section for floating-point precision in aggregation (experience skill C29 references here).

### General Principle
IEEE 754 double has ~15.95 significant decimal digits. Precision loss occurs when:
- The running SUM accumulator reaches magnitude >10^13, AND
- Output requires specific decimal digit accuracy (e.g., 2 decimal places for financial data)

### Detection
Data sampling during workload analysis shows column max value >= 10^10, AND query uses SUM/AVG with formatted output requiring decimal precision.

### Fix — int64_t Fixed-Point Accumulation
```
// Instead of: double sum += value;
// Use:
int64_t sum_cents = 0;
sum_cents += llround(value * 100.0);  // exact if individual value < ~10^13
// Output: printf("%lld.%02lld", sum_cents/100, llabs(sum_cents%100));
```

### Why This Works
Each individual `llround(v * 100.0)` is exact when `|v| < ~4.5 * 10^13` (because `v * 100` stays within double's exact integer range of 2^53 ~ 9 * 10^15). The int64_t accumulation is then perfectly exact regardless of sum magnitude.

### Why FP Compensation Fails
Kahan/Neumaier summation reduces error from summation ORDER, not from accumulator MAGNITUDE. When the sum itself exceeds 10^13, the ULP exceeds 0.01 and no reordering can recover sub-ULP precision.

### When NOT Needed
- If output tolerance is large (e.g., +/-$100 on $566B sums, as in TPC-H)
- If column max < 10^10
- If no decimal precision requirement in output
In these cases, double accumulation is fine.

## Key Principles
- Hash aggregation for medium-high cardinality (100-10M groups): O(n), pre-size hash table
- Sorted aggregation for pre-sorted input or very low cardinality: O(n) time, O(1) memory
- For <256 groups with dense integer keys: direct flat array lookup, zero hash overhead
- Partial aggregation for parallel execution: thread-local pre-agg → global merge

## GenDB-Specific
- Thread-local aggregation: each thread maintains own hash table, merge at end
- CRITICAL: Size each thread's hash table for FULL estimated group count, not groups/nthreads (see hash-tables skill: Sizing Rules)
- Merge strategy (MANDATORY — compute T×G and total_agg_mem before implementation; compare against hardware LLC):
  - **T×G < 100K**: Sequential merge into shared hash (acceptable at this scale)
  - **T×G 100K-2M**: Two-phase tree-merge: merge groups of 8 threads in parallel (log₈(T) rounds), then merge 8→1. Reduces sort input by 8×.
  - **T×G > 2M AND total_agg_mem ≤ LLC**: Partitioned merge: during aggregation, hash groups into P partitions (P=next_pow2(T)); during merge, each partition merged independently by one thread. Fully parallel, zero contention.
  - **T×G > 2M AND total_agg_mem > LLC**: Evaluate Memory Budget Gate above — may require scan-time partitioned aggregation.
  - **DEFAULT: Thread-local aggregation is strongly preferred (P20). A single shared aggregation map causes severe contention at scale; only consider it for very few groups where atomic updates are trivially cheap. Exception: integer accumulators with LOCK XADD — see Shared XADD Aggregation above.**
  - VIOLATION DIAGNOSTIC: If build_joins + aggregation_merge > 2× main_scan, wrong strategy chosen — re-evaluate using Memory Budget Gate.
- CRITICAL: Size AGG_CAP per thread to next_pow2(estimated_groups × 2), not a large fixed ceiling. Over-sized per-thread tables waste memory and slow merge (P23, P25).
- GROUP BY key: MUST include ALL SQL GROUP BY columns. For composite GROUP BY keys, see data-structures skill: Composite Key Hashing

## Probe-Aggregate Fusion

When a query joins two tables and then aggregates over the join result, AND the GROUP BY key is a superset of (or equals) the join key, the probe and aggregation can be fused into one operation: during the probe-side scan, on each match, accumulate the aggregate value directly into the join hash table slot rather than materializing intermediate tuples.

### Conditions Favoring This Approach
- GROUP BY key ⊇ join key (each probe-side row maps to exactly one aggregation group via the join key)
- The join is a PK join or the GROUP BY key fully determines the group (no many-to-many ambiguity)
- The intermediate materialization cost is significant (>5M qualifying probe rows that would otherwise fill partition buffers)

### Implementation Pattern
1. Build-side HT includes accumulator fields (e.g., `atomic<uint64_t> revenue`) initialized to zero
2. During probe scan: `if match → atomic_add_double(&ht.revs[slot], revenue_value)`
3. After scan: linear sweep over HT to extract non-zero accumulated results
4. Atomic double-add via CAS loop: `load old_bits → memcpy to double → add → memcpy to uint64_t → CAS`

### Benefits
- Eliminates intermediate tuple materialization (flat buffers, partition buffers)
- Eliminates separate aggregation_merge phase entirely
- Reduces total memory traffic: one HT probe serves both join and aggregation
- Measured: 79ms total vs 188ms with separate partition-buffer aggregation on same workload

### Trade-offs and Caveats
- **FP non-determinism**: atomic CAS addition from multiple threads produces non-deterministic accumulation order, which can cause ±0.01 rounding differences vs reference at float64 precision boundaries. This is acceptable when output tolerance allows it (e.g., TPC-H revenue columns have $100 tolerance) but may fail exact-match validation.
- **Atomic contention**: if many probe rows map to a small number of HT slots (low GROUP BY cardinality), CAS contention increases. In that case, thread-local aggregation may be better.
- **SoA layout recommended**: separate keys[], metadata[], accumulators[] arrays so only the accumulators[] array needs atomic operations — see hash-tables skill: SoA vs AoS Layout.
- **Not compatible with Robin Hood hashing**: Robin Hood displaces existing entries, which conflicts with accumulators that are being atomically updated by other threads. Use simple linear probing with CAS-based build instead.

### When NOT to Use
- GROUP BY key has columns not derivable from the join key (need separate aggregation HT)
- Exact FP reproducibility required and no tolerance on aggregate output
- Very low GROUP BY cardinality where thread-local aggregation + merge is simpler and sufficient

## HAVING Clause Optimization
- Pre-compute scalar subquery thresholds before main aggregation when possible
- Apply HAVING during merge phase (not as separate post-processing pass)
- This avoids materializing groups that will be filtered out

## Aggregation Patterns
- **Direct array**: key domain <256 → allocate flat array, O(1) access, no hashing
- **Open-addressing hash**: pre-sized 2x expected groups, Robin Hood probing
- **Partitioned hash**: divide key space into partitions, each thread owns a partition (contention-free)
- **Two-phase**: Phase 1 (parallel): thread-local hash tables. Phase 2 (merge): atomic updates to global table.
- **Streaming**: Input pre-sorted on GROUP BY key → single-pass O(n), O(1) memory

## Technique Keywords
hash aggregation, sorted aggregation, partial aggregation, thread-local merge,
partitioned aggregation, fixed-point accumulation, direct array aggregation

## Reference Papers
- Ye et al. 2011 — "Scalable Aggregation on Multicore Processors"
- Leis et al. 2014 — "Morsel-Driven Parallelism" (thread-local aggregation pattern)

## Diagnostic-Driven Adaptation

If the chosen aggregation strategy underperforms after implementation, use timing diagnostics to guide the next step:

| Symptom | Likely Cause | Adaptation |
|---------|-------------|------------|
| build_joins + aggregation_merge > 2× main_scan | Per-thread maps too large, initialization/merge dominates | Re-evaluate Memory Budget Gate; try scan-time partitioned aggregation |
| aggregation_merge > 20ms with thread-local maps | Too many groups × threads for sequential merge | Switch to partitioned merge or reduce partition count |
| main_scan unexpectedly slow with aggregation | Hash map probes cache-thrashing during scan | Check per-thread map fits per-core cache; if not, switch to scan-time partitioning |
| No improvement after strategy change | Bottleneck may be elsewhere (data loading, joins) | Profile other phases; aggregation may not be the dominant cost |

The goal is not to prescribe one strategy but to quickly diagnose and pivot when a strategy doesn't fit the workload.

## Common Pitfalls
→ See experience skill: C9 (hash table capacity), C15 (missing GROUP BY dimension), C29 (double precision), P3 (sort vs hash), P15 (merge cost), P20 (thread-local default), P33 (probe-aggregate fusion)
登录后下载/点赞/收藏 ❤ 23 | ★ 0
aggregation-optimization

目录结构

SKILL.md

举报内容

提示
