Skip to content
HeliosDB HeliosDB Full

F3.5 Distributed Query Optimization - Quick Reference

F3.5 Distributed Query Optimization - Quick Reference

Feature: F3.5 Distributed Query Optimization ARR Value: $14M Priority: P0 (Critical) Timeline: 14 weeks (3.5 months) Investment: $1.2M-$1.5M

Key Innovations

  1. Network-Aware Multi-Region Optimization ($8M-$12M value)

    • Real-time latency/bandwidth measurement
    • Dynamic cost model adaptation
    • 40-60% latency reduction

  2. Histogram-Based Partition Pruning ($3M-$5M value)

    • Combined histogram + Bloom filter
    • 60-85% partition elimination
    • 50-70% I/O reduction

  3. Adaptive Skew-Aware Joins ($2M-$4M value)

    • Runtime skew detection
    • Dynamic strategy switching
    • 5-10x improvement on skewed data

  4. Streaming Online Aggregation ($4M-$6M value)

    • Incremental results with confidence intervals
    • 10-100x faster perceived latency
    • Interactive OLAP on massive datasets

Architecture Overview

SQL Query → Parser → Logical Plan → Optimizer → Physical Plan → Executor
                          ↑              ↑             ↑
                      Metadata      Statistics    Feedback

Core Components:

  • Network-Aware Cost Model
  • Join Strategy Selector
  • Predicate Pushdown Engine
  • Streaming Executor
  • Adaptive Re-optimizer

Performance Targets

MetricTargetStretch Goal
Planning time (simple)<10ms<5ms
Planning time (complex)<100ms<50ms
Network efficiency60-70% reduction80%
Partition pruning60-70% eliminated85%
Join performance3-5x faster10x
Scale1,000 shards5,000

Implementation Phases

Phase 1: Enhanced Cost Model (2 weeks)

  • Multi-region network cost modeling
  • Histogram-based cardinality
  • Deliverables: NetworkTopologyManager, MultiRegionCostModel

Phase 2: Join Strategy Selection (3 weeks)

  • 5 join strategies (broadcast, shuffle, co-located, sort-merge, skew-aware)
  • Skew detection and handling
  • Deliverables: JoinStrategySelector, SkewDetector

Phase 3: Predicate Pushdown (2 weeks)

  • Multi-level pushdown (storage, partition, node)
  • Histogram-based partition pruning
  • Deliverables: EnhancedPartitionPruner, JoinPredicateExtractor

Phase 4: Streaming & Aggregation (3 weeks)

  • Streaming query execution
  • Online aggregation with confidence intervals
  • Deliverables: StreamingExecutor, OnlineAggregator

Phase 5: Adaptive Execution (2 weeks)

  • Runtime statistics collection
  • Adaptive re-optimization
  • Deliverables: RuntimeStatsCollector, AdaptiveReoptimizer

Phase 6: Integration & Testing (2 weeks)

  • Full system integration
  • TPC-H benchmark validation
  • Production readiness
  • Deliverables: Complete F3.5 feature, documentation

Key Algorithms

1. Network Cost Estimation

cost = latency + (data_size / bandwidth) * congestion_factor + protocol_overhead

2. Broadcast Threshold

threshold = base_threshold_mb * (bandwidth_factor / sqrt(num_nodes))

3. Partition Pruning

FOR EACH partition:
  IF predicate_overlaps(partition.min, partition.max):
    KEEP partition
  ELSE:
    PRUNE partition

4. Join Strategy Selection

IF co_located:
  RETURN ColocatedJoin
ELSE IF smaller_table < broadcast_threshold:
  RETURN BroadcastJoin
ELSE IF skew_detected:
  RETURN SkewAwareJoin
ELSE:
  RETURN ShuffleHashJoin

API Quick Reference

Main Optimizer API

pub struct DistributedQueryOptimizer {
    pub fn optimize_query(&self, sql: &str) -> Result<DistributedQueryPlan>;
    pub fn optimize_logical_plan(&self, plan: LogicalPlan) -> Result<PhysicalPlan>;
    pub fn explain(&self, sql: &str) -> Result<String>;
    pub fn update_network_topology(&self, topology: NetworkTopology) -> Result<()>;
    pub fn get_metrics(&self) -> OptimizerMetrics;
}

Cost Model API

pub trait CostModel {
    fn estimate_scan_cost(&self, table: &TableInfo, predicates: &[Predicate]) -> QueryCost;
    fn estimate_join_cost(&self, left: &PhysicalPlan, right: &PhysicalPlan) -> QueryCost;
    fn estimate_network_cost(&self, source: NodeId, target: NodeId, bytes: u64) -> Duration;
}

Statistics API

pub trait StatisticsCollector {
    async fn collect_table_statistics(&self, table: &str) -> Result<TableStatistics>;
    async fn collect_column_histogram(&self, table: &str, column: &str) -> Result<Histogram>;
    async fn update_runtime_statistics(&self, query_id: QueryId, stats: RuntimeStatistics) -> Result<()>;
}

Configuration

Default Configuration

OptimizerConfig {
    enable_cost_based: true,
    enable_partition_pruning: true,
    enable_predicate_pushdown: true,
    enable_join_reordering: true,
    max_join_reorder_tables: 8,
    planning_timeout_ms: 100,
    enable_adaptive_execution: true,
    broadcast_threshold_mb: 100.0,
    enable_online_aggregation: true,
    stats_freshness_threshold_secs: 300,
}

Production Configuration

OptimizerConfig::production() {
    max_join_reorder_tables: 6,  // Faster planning
    planning_timeout_ms: 50,      // Strict timeout
    broadcast_threshold_mb: 50.0, // Conservative
}

Aggressive Configuration

OptimizerConfig::aggressive() {
    max_join_reorder_tables: 12,  // More optimization
    planning_timeout_ms: 200,      // Allow more time
    broadcast_threshold_mb: 200.0, // Larger broadcasts
}

Integration Points

1. heliosdb-metadata

  • Get cluster topology
  • Get table schemas
  • Get partition locations

2. heliosdb-sharding

  • Detect co-located tables
  • Get partition strategies
  • Route queries to shards

3. heliosdb-compute

  • Execute physical plans
  • Collect runtime statistics
  • Stream results

4. heliosdb-cache

  • Cache query plans
  • Cache metadata
  • Cache statistics

Testing Strategy

Unit Tests (90%+ coverage)

  • Cost model calculations
  • Partition pruning logic
  • Join strategy selection
  • Cardinality estimation

Integration Tests

  • End-to-end query optimization
  • Multi-region query execution
  • Adaptive re-optimization
  • Fault tolerance

Performance Tests

  • TPC-H benchmark suite (all 22 queries)
  • TPC-DS benchmark (selected queries)
  • Scale tests (1000+ shards)
  • Concurrent query tests (10,000 queries/sec)

Stress Tests

  • Network failures
  • Node failures
  • Extreme data skew
  • Memory pressure

Success Metrics

Functional

  • All TPC-H queries execute correctly
  • Join strategies >90% correct choice
  • Partition pruning >60% on filtered queries
  • Cost estimation within 2x of actual

Performance

  • Planning: <100ms for 95% of queries
  • Execution: 3-5x improvement over naïve
  • Network: 60-80% reduction in data transfer
  • Throughput: 10,000 queries/sec on 100 nodes

Scalability

  • 1,000 shards without degradation
  • 10-table joins in <500ms planning
  • Linear scaling to 500 nodes

Reliability

  • Single node failure: <10s recovery
  • Network partition: graceful degradation
  • Zero data loss on failures

Common Pitfalls & Solutions

Pitfall 1: Inaccurate Cost Model

Problem: Estimates don’t match reality Solution:

  • Calibrate with actual workloads
  • Use ML-based refinement
  • Update statistics frequently

Pitfall 2: Stale Statistics

Problem: Optimizer uses outdated data Solution:

  • Automatic stats refresh (5-minute TTL)
  • Timestamp tracking
  • Invalidation on schema changes

Pitfall 3: Network Instability

Problem: Topology changes during query Solution:

  • Fault-tolerant execution
  • Retry logic with exponential backoff
  • Partial result handling

Pitfall 4: Skew Misdetection

Problem: Miss or over-detect data skew Solution:

  • Conservative thresholds
  • Multiple detection methods
  • Fallback strategies

Pitfall 5: Memory Pressure

Problem: Large broadcasts exceed memory Solution:

  • Spilling to disk
  • Memory limits per operator
  • Backpressure mechanism

Files & Locations

Architecture Documents

  • /docs/architecture/F3_5_DISTRIBUTED_QUERY_OPTIMIZATION_ARCHITECTURE.md
  • /docs/architecture/F3_5_ALGORITHMS_PSEUDOCODE.md
  • /docs/architecture/F3_5_QUICK_REFERENCE.md (this file)

Implementation

  • /heliosdb-distributed-optimizer/src/cost_model.rs
  • /heliosdb-distributed-optimizer/src/enhanced_cost_model.rs
  • /heliosdb-distributed-optimizer/src/optimizer.rs
  • /heliosdb-distributed-optimizer/src/planner.rs
  • /heliosdb-distributed-optimizer/src/executor.rs

New Files to Create

  • /heliosdb-distributed-optimizer/src/network_topology.rs
  • /heliosdb-distributed-optimizer/src/join/strategy_selector.rs
  • /heliosdb-distributed-optimizer/src/join/skew_handler.rs
  • /heliosdb-distributed-optimizer/src/streaming/executor.rs
  • /heliosdb-distributed-optimizer/src/adaptive/reoptimizer.rs

Tests

  • /heliosdb-distributed-optimizer/tests/integration_tests.rs
  • /heliosdb-distributed-optimizer/tests/performance_tests.rs
  • /heliosdb-distributed-optimizer/tests/tpch_validation.rs

Patent Disclosures

  • /docs/ip/invention-disclosures/F3_5_NETWORK_AWARE_QUERY_OPT_DISCLOSURE.md

Resources & References

Research Papers

  • “Orca: A Modular Query Optimizer Architecture” (Microsoft)
  • “The Volcano Optimizer Generator” (Goetz Graefe)
  • “Adaptive Query Processing” (Ron Avnur, Joseph M. Hellerstein)
  • “Access Path Selection in a RDBMS” (Selinger et al.)

Competitive Systems

  • Google Spanner: Static multi-region cost model
  • CockroachDB: Basic region awareness
  • Amazon Aurora: Single-region focus
  • Snowflake: Micro-partitions with metadata
  • Databricks: Adaptive query execution

Internal Documents

  • /docs/roadmap/V7_0_COMPLETE_ROADMAP.md
  • /docs/FEATURE_DEVELOPMENT_PROTOCOL.md
  • /docs/USER_GUIDE_INDEX.md

Team & Contacts

Technical Leads

  • Optimizer Lead: [TBD] - Architecture and cost model
  • Join Optimization: [TBD] - Join strategies and skew handling
  • Streaming: [TBD] - Streaming execution and online aggregation
  • Adaptive Execution: [TBD] - Runtime stats and re-optimization

Stakeholders

  • Product: Feature prioritization, user requirements
  • Engineering: Implementation, code review
  • QA: Testing strategy, benchmark validation
  • Legal: Patent filing, IP protection

Quick Commands

Run Tests

Terminal window
# Unit tests
cargo test -p heliosdb-distributed-optimizer


# Integration tests
cargo test -p heliosdb-distributed-optimizer --test integration_tests


# Performance benchmarks
cargo bench -p heliosdb-distributed-optimizer


# TPC-H validation
cargo test -p heliosdb-distributed-optimizer --test tpch_validation

Build & Deploy

Terminal window
# Development build
cargo build -p heliosdb-distributed-optimizer


# Release build
cargo build -p heliosdb-distributed-optimizer --release


# Run with profiling
cargo flamegraph -p heliosdb-distributed-optimizer

Documentation

Terminal window
# Generate docs
cargo doc -p heliosdb-distributed-optimizer --open


# Check documentation
cargo test --doc -p heliosdb-distributed-optimizer

Last Updated: November 9, 2025 Status: Architecture Complete, Ready for Implementation Next Review: Start of Phase 1 (Week 1)