linkrs_query/optimizer/cost/
config.rs

1//! Cost Model Configuration Module
2//!
3//! Provide configurable cost parameters, referring to the design of the cost model in PostgreSQL.
4//!
5//! ## Usage Examples
6//!
7//! ```rust
8//! use linkrs_query::optimizer::cost::CostModelConfig;
9//!
10//! // Use the default configuration
11//! let config = CostModelConfig::default();
12//!
13//! // Optimizations for SSDs
14//! let ssd_config = CostModelConfig::for_ssd();
15//!
16//! // Custom configuration
17//! let custom_config = CostModelConfig {
18//!     seq_page_cost: 0.5,
19//!     random_page_cost: 1.0,
20//!     ..Default::default()
21//! };
22//! ```
23
24/// Cost Model Configuration
25///
26/// Define the cost parameters for various operations, which are used to calculate the execution cost of the query plan.
27/// Refer to the design of the PostgreSQL cost model and extend it to take into account the characteristics of graph databases.
28/// These parameters can be adjusted according to the hardware environment.
29///
30/// Unit notes: `effective_cache_pages` counts pages (`ROWS_PER_PAGE` rows
31/// per page); `memory_sort_threshold` counts rows. The two must not be
32/// compared directly without converting via `ROWS_PER_PAGE`.
33#[derive(Debug, Clone, Copy, PartialEq)]
34pub struct CostModelConfig {
35    // ==================== Basic I/O Cost Parameters (Consistent with PostgreSQL) ====================
36    /// Alternative to reading pages in order
37    ///
38    /// The cost of sequentially reading a disk page. Default value 1.0
39    /// In an SSD environment, the requirements can be appropriately reduced.
40    pub seq_page_cost: f64,
41
42    /// Alternative to reading a random page:
43    ///
44    /// The cost of reading a random disk page. Default value 4.0
45    /// On traditional mechanical hard drives, random access is much slower than sequential access.
46    /// In an SSD environment, the value of `seq_page_cost` can be approached.
47    pub random_page_cost: f64,
48
49    /// Cost of CPU processing per row
50    ///
51    /// CPU cost to process each row of data. Default value 0.01
52    pub cpu_tuple_cost: f64,
53
54    /// Cost of processing index rows
55    ///
56    /// CPU cost to process each index entry. Default value 0.005
57    /// It is usually lower than `cpu_tuple_cost` because the index entries are smaller.
58    pub cpu_index_tuple_cost: f64,
59
60    /// The cost of operator calculations
61    ///
62    /// The CPU cost of executing each operator or function. Default value 0.0025
63    pub cpu_operator_cost: f64,
64
65    // ==================== Algorithm-related parameters ====================
66    /// Hash construction overhead coefficient
67    ///
68    /// Extra overhead factor for building the hash table. Default value 0.1
69    pub hash_build_overhead: f64,
70
71    /// Sorting and comparing cost coefficients
72    ///
73    /// The cost factor for each comparison operation. Default value 1.0
74    pub sort_comparison_cost: f64,
75
76    /// Memory sorting threshold (number of rows)
77    ///
78    /// If this threshold is exceeded, external sorting will be used. The default value is 10000.
79    pub memory_sort_threshold: u64,
80
81    /// Cost of external sorting pages
82    ///
83    /// The cost of reading and writing temporary files while externally sorting. Default value 2.0
84    pub external_sort_page_cost: f64,
85
86    // ==================== Parameters specific to graph databases ====================
87    /// Edge traversal cost
88    ///
89    /// The cost of traversing an edge, which is more complex than vertex processing. Default value 0.02
90    pub edge_traversal_cost: f64,
91
92    /// Multi-hop traversal with an incrementing coefficient at each step
93    ///
94    /// The factor by which the cost is incremented for each additional hop. Default value 1.2
95    pub multi_hop_penalty: f64,
96
97    /// Cost of neighbor node lookup
98    ///
99    /// The cost of finding a neighbor node. Default value 0.015
100    pub neighbor_lookup_cost: f64,
101
102    /// Effective cache size (number of pages)
103    ///
104    /// Used for cost calculation in cache-aware scenarios. Default value: 10000
105    pub effective_cache_pages: u64,
106
107    /// Cache Hit Cost Coefficient
108    ///
109    /// The cost factor for when the data is in the cache. Default value 0.1
110    pub cache_hit_cost_factor: f64,
111
112    /// Fundamentals of the cost in shortest path algorithms
113    ///
114    /// Fixed overhead for the shortest path algorithm. Default value 10.0
115    pub shortest_path_base_cost: f64,
116
117    /// Path enumeration exponent coefficient
118    ///
119    /// The complexity factor when enumerating all paths. Default value 2.0
120    pub path_enumeration_factor: f64,
121
122    /// Super Node Threshold (Degree)
123    ///
124    /// Nodes that exceed this degree are considered super nodes. The default value is 10000.
125    pub super_node_threshold: u64,
126
127    /// Super Node Additional Cost Coefficient
128    ///
129    /// Additional cost when super nodes are involved. Default value 2.0
130    pub super_node_penalty: f64,
131
132    // ==================== Default parameters for control flow ====================
133    /// The default list size for “Unwind”.
134    ///
135    /// Default value used when the list size cannot be inferred from an expression. Default value 3.0
136    pub default_unwind_list_size: f64,
137
138    /// The default number of iterations for the Loop function
139    ///
140    /// The default value used when the number of iterations cannot be determined from the conditions. The default value is 3.
141    pub default_loop_iterations: u32,
142
143    /// Select the default number of branches.
144    ///
145    /// The default value used when the number of branches cannot be determined. The default value is 2.
146    pub default_select_branches: usize,
147
148    // ==================== Memory and expression cost parameters ====================
149    /// Cost per byte of memory usage
150    ///
151    /// Cost per byte of memory usage (used to estimate memory pressure). Default value 0.0001
152    pub memory_byte_cost: f64,
153
154    /// Memory pressure threshold (bytes)
155    ///
156    /// Memory pressure threshold (exceeding this value increases the cost penalty). Default value 100MB
157    pub memory_pressure_threshold: usize,
158
159    /// Memory pressure penalty factor
160    ///
161    /// Memory pressure penalty factor. Default value 2.0
162    pub memory_pressure_penalty: f64,
163
164    /// Simple expression (leaf node) cost
165    ///
166    /// Simple expression (leaf node) cost. Default value 0.001
167    pub simple_expression_cost: f64,
168
169    /// Function call base cost
170    ///
171    /// The function call base cost. Default value 0.01
172    pub function_call_base_cost: f64,
173
174    /// Expression nesting cost per level
175    ///
176    /// Nesting cost per level for complex expressions. Default value 0.005
177    pub expression_nesting_cost: f64,
178
179    /// Fixed-size type cost factor
180    ///
181    /// Fixed size type processing cost factor. Default value 1.0
182    pub fixed_type_cost_factor: f64,
183
184    /// Variable-length type cost factor
185    ///
186    /// Variable length type processing cost factor. Default value 1.5
187    pub variable_type_cost_factor: f64,
188
189    /// Complex type cost factor
190    ///
191    /// Complex type processing cost factor. Default value 2.0
192    pub complex_type_cost_factor: f64,
193
194    /// Graph type cost factor
195    ///
196    /// Chart type processing cost factor. Default value 3.0
197    pub graph_type_cost_factor: f64,
198
199    /// Average row width in bytes for memory estimates.
200    ///
201    /// Stack size of one `Value` (`ESTIMATED_ROW_WIDTH_BYTES`); heap
202    /// payloads of variable-length values are not included, so wide rows
203    /// are systematically underestimated. All memory estimates (sort,
204    /// hash join, aggregation, budget allocation) share this single
205    /// source instead of private copies; per-space overrides flow through
206    /// the existing cost-config mechanism.
207    pub row_width_bytes: usize,
208
209    // ==================== Strategy Threshold Parameters ====================
210    /// Strategy threshold configuration
211    ///
212    /// Policy threshold configuration for controlling the behavior of various optimization policies
213    pub strategy_thresholds: StrategyThresholds,
214}
215
216/// Single source for estimation fallbacks shared by cost and planning layers.
217///
218/// `UNKNOWN_SCAN_ROWS` (1000) is the only no-statistics scan default;
219/// `DEFAULT_FANOUT` (10) is the only neighborhood fanout default;
220/// `DEFAULT_DEGREE_FALLBACK` (2.0) is the only per-edge average-degree
221/// fallback; `ROWS_PER_PAGE` (100) is the only page/row conversion;
222/// `SUPER_NODE_THRESHOLD` (10000) is the only super-node degree threshold;
223/// `TOPN_RATIO` (10) with `TOPN_MIN_ROWS` is the only sort-to-TopN rule.
224/// Point lookups use `GET_VERTICES_DEFAULT_ROWS` (1) and
225/// `GET_EDGES_DEFAULT_ROWS` (10); dedup uses `DEDUP_SELECTIVITY` (0.8).
226/// Skew judgments use the `SKEW_*` thresholds so edge statistics and
227/// traversal estimation share one definition.
228/// Row width is derived from the real `Value` layout so memory estimates
229/// track column types instead of a hardcoded 64.
230pub const UNKNOWN_SCAN_ROWS: u64 = 1_000;
231pub const DEFAULT_FANOUT: u64 = 10;
232pub const DEFAULT_DEGREE_FALLBACK: f64 = 2.0;
233pub const ROWS_PER_PAGE: u64 = 100;
234pub const SUPER_NODE_THRESHOLD: u64 = 10_000;
235pub const TOPN_RATIO: u64 = 10;
236pub const TOPN_MIN_ROWS: u64 = 10_000;
237pub const GET_VERTICES_DEFAULT_ROWS: u64 = 1;
238pub const GET_EDGES_DEFAULT_ROWS: u64 = 10;
239pub const DEDUP_SELECTIVITY: f64 = 0.8;
240pub const SKEW_SEVERE_GINI: f64 = 0.7;
241pub const SKEW_MODERATE_GINI: f64 = 0.5;
242pub const SKEW_MILD_GINI: f64 = 0.3;
243pub const SKEW_MAX_DEGREE_RATIO: f64 = 10.0;
244pub const SKEW_DIRECTION_RATIO: f64 = 5.0;
245pub const SKEW_SEVERE_PENALTY: f64 = 2.0;
246pub const SKEW_MODERATE_PENALTY: f64 = 1.5;
247pub const SKEW_MILD_PENALTY: f64 = 1.2;
248pub const SKEW_SEVERE_ROW_FACTOR: f64 = 1.5;
249pub const SKEW_MODERATE_ROW_FACTOR: f64 = 1.3;
250pub const SKEW_MILD_ROW_FACTOR: f64 = 1.1;
251/// Row width derived from the real value layout.
252///
253/// Default for `CostModelConfig::row_width_bytes`; stack size only, heap
254/// payloads excluded.
255pub const ESTIMATED_ROW_WIDTH_BYTES: usize = std::mem::size_of::<linkrs_core::Value>();
256
257/// Strategy Threshold Configuration
258///
259/// Define threshold parameters for various optimization strategies that are used to control the strategy selection behavior.
260/// These parameters can be adjusted according to the workload characteristics.
261#[derive(Debug, Clone, Copy, PartialEq)]
262pub struct StrategyThresholds {
263    // ==================== Aggregate Strategy ====================
264    /// Small dataset threshold for aggregate strategy
265    ///
266    /// Small dataset threshold (number of rows) below which the simple aggregation strategy is used. Default value 1000
267    pub small_dataset_threshold: u64,
268
269    /// Low cardinality threshold for aggregate strategy
270    ///
271    /// Low base threshold below which sorted aggregation is used. Default value 100
272    pub low_cardinality_threshold: u64,
273
274    /// High cardinality ratio threshold
275    ///
276    /// High base scale threshold (relative to the number of input lines) above which streaming aggregation is used. Default value 0.1
277    pub high_cardinality_ratio: f64,
278
279    // ==================== Traversal Strategy ====================
280    // Super-node threshold is the single `CostModelConfig::super_node_threshold`
281    // (`SUPER_NODE_THRESHOLD`); no separate traversal copy is kept.
282    /// Bidirectional traversal savings threshold
283    ///
284    /// Bidirectional traversal savings threshold above which bidirectional traversal is used. Default value 0.3
285    pub bidirectional_savings_threshold: f64,
286
287    /// Default branching factor for traversal
288    ///
289    /// Traverses the default branching factor for cost estimation. Default value 2.0
290    pub default_branching_factor: f64,
291
292    // ==================== TopN Strategy ====================
293    /// TopN selectivity threshold
294    ///
295    /// TopN selectivity threshold below which TopN optimization is used. Default value 0.1
296    pub topn_threshold: f64,
297    /// TopN default limit
298    ///
299    /// TopN defaults to limiting the number of rows. Default value 100
300    pub topn_default_limit: u64,
301
302    // ==================== Join reorder review ====================
303    /// Minimum relative improvement for the join-order reviewer.
304    ///
305    /// The reviewer rewrites a join chain only when the proposed order
306    /// costs less than `current * (1 - this)`. Zero keeps model authority
307    /// (any strict improvement wins, exact ties keep the current order so
308    /// plans never flap between equal-cost shapes); raise it to calm
309    /// replanning churn when statistics wobble. Clamped to `[0, 1)`.
310    pub join_reorder_min_improvement: f64,
311
312    // ==================== Materialization Strategy ====================
313    /// Maximum result rows for CTE materialization
314    ///
315    /// Maximum number of result rows for CTE materialization. Default value 10000
316    pub max_result_rows: u64,
317
318    /// Minimum reference count for CTE materialization
319    ///
320    /// Minimum number of references for CTE materialization. Default value 2
321    pub min_reference_count: usize,
322
323    /// Minimum complexity score for CTE materialization
324    ///
325    /// Minimum complexity score for CTE materialization. Default value 5.0
326    pub min_complexity_score: f64,
327}
328
329impl Default for StrategyThresholds {
330    fn default() -> Self {
331        Self {
332            // Aggregate strategy
333            small_dataset_threshold: 1000,
334            low_cardinality_threshold: 100,
335            high_cardinality_ratio: 0.1,
336            // Traversal strategy: super-node uses CostModelConfig::super_node_threshold.
337            bidirectional_savings_threshold: 0.3,
338            default_branching_factor: DEFAULT_DEGREE_FALLBACK,
339            // TopN strategy: threshold derives from the sort-to-TopN ratio so
340            // the two spellings cannot drift apart.
341            topn_threshold: 1.0 / TOPN_RATIO as f64,
342            topn_default_limit: 100,
343            // Join reorder review: any strict improvement wins by default.
344            join_reorder_min_improvement: 0.0,
345            // Materialization strategy
346            max_result_rows: 10000,
347            min_reference_count: 2,
348            min_complexity_score: 5.0,
349        }
350    }
351}
352
353impl Default for CostModelConfig {
354    fn default() -> Self {
355        Self {
356            // Basic I/O cost parameters (consistent with PostgreSQL)
357            seq_page_cost: 1.0,
358            random_page_cost: 4.0,
359            cpu_tuple_cost: 0.01,
360            cpu_index_tuple_cost: 0.005,
361            cpu_operator_cost: 0.0025,
362            // Algorithm-related parameters: row-count threshold.
363            hash_build_overhead: 0.1,
364            sort_comparison_cost: 1.0,
365            memory_sort_threshold: TOPN_MIN_ROWS,
366            external_sort_page_cost: 2.0,
367            // Parameter specific to graph databases
368            edge_traversal_cost: 0.02,
369            multi_hop_penalty: 1.2,
370            neighbor_lookup_cost: 0.015,
371            effective_cache_pages: 10000,
372            cache_hit_cost_factor: 0.1,
373            shortest_path_base_cost: 10.0,
374            path_enumeration_factor: 2.0,
375            super_node_threshold: SUPER_NODE_THRESHOLD,
376            super_node_penalty: 2.0,
377            // Default parameters for control flow
378            default_unwind_list_size: 3.0,
379            default_loop_iterations: 3,
380            default_select_branches: 2,
381            // Memory and expression cost parameters
382            memory_byte_cost: 0.0001,
383            memory_pressure_threshold: 100 * 1024 * 1024, // 100MB
384            memory_pressure_penalty: 2.0,
385            simple_expression_cost: 0.001,
386            function_call_base_cost: 0.01,
387            expression_nesting_cost: 0.005,
388            fixed_type_cost_factor: 1.0,
389            variable_type_cost_factor: 1.5,
390            complex_type_cost_factor: 2.0,
391            graph_type_cost_factor: 3.0,
392            row_width_bytes: ESTIMATED_ROW_WIDTH_BYTES,
393            // Strategy thresholds
394            strategy_thresholds: StrategyThresholds::default(),
395        }
396    }
397}
398
399impl CostModelConfig {
400    /// Create the default configuration.
401    pub fn new() -> Self {
402        Self::default()
403    }
404
405    /// Optimizations for SSD storage
406    ///
407    /// The random access performance of SSDs is close to that of sequential access; therefore, reducing the value of `random_page_cost` has a positive impact on overall system performance.
408    pub fn for_ssd() -> Self {
409        Self {
410            random_page_cost: 1.1, // Random access to SSDs is similar to sequential access.
411            ..Default::default()
412        }
413    }
414
415    /// Optimizations for in-memory databases
416    ///
417    /// There are no disk I/O overheads in memory; the main consideration is the cost associated with the CPU.
418    pub fn for_in_memory() -> Self {
419        Self {
420            seq_page_cost: 0.1,
421            random_page_cost: 0.1,
422            cache_hit_cost_factor: 0.01, // A cache hit incurs almost no cost.
423            ..Default::default()
424        }
425    }
426
427    /// Optimizations for mechanical hard drives (conservative configuration)
428    ///
429    /// Traditional mechanical hard drives have poor random access performance.
430    pub fn for_hdd() -> Self {
431        Self {
432            seq_page_cost: 1.0,
433            random_page_cost: 4.0,
434            ..Default::default()
435        }
436    }
437
438    /// Set the order for reading pages as an alternative option.
439    pub fn with_seq_page_cost(mut self, cost: f64) -> Self {
440        self.seq_page_cost = cost;
441        self
442    }
443
444    /// Set a substitute price for random page reading.
445    pub fn with_random_page_cost(mut self, cost: f64) -> Self {
446        self.random_page_cost = cost;
447        self
448    }
449
450    /// Setting the CPU cost for line processing
451    pub fn with_cpu_tuple_cost(mut self, cost: f64) -> Self {
452        self.cpu_tuple_cost = cost;
453        self
454    }
455
456    /// Setting the cost of processing index rows
457    pub fn with_cpu_index_tuple_cost(mut self, cost: f64) -> Self {
458        self.cpu_index_tuple_cost = cost;
459        self
460    }
461
462    /// Setting the cost of operator calculations
463    pub fn with_cpu_operator_cost(mut self, cost: f64) -> Self {
464        self.cpu_operator_cost = cost;
465        self
466    }
467}
468
469#[cfg(test)]
470mod tests {
471    use super::*;
472
473    #[test]
474    fn test_default_config() {
475        let config = CostModelConfig::default();
476        // Basic I/O Cost Parameters
477        assert_eq!(config.seq_page_cost, 1.0);
478        assert_eq!(config.random_page_cost, 4.0);
479        assert_eq!(config.cpu_tuple_cost, 0.01);
480        assert_eq!(config.cpu_index_tuple_cost, 0.005);
481        assert_eq!(config.cpu_operator_cost, 0.0025);
482        // Algorithm-related parameters
483        assert_eq!(config.hash_build_overhead, 0.1);
484        assert_eq!(config.sort_comparison_cost, 1.0);
485        assert_eq!(config.memory_sort_threshold, 10000);
486        assert_eq!(config.external_sort_page_cost, 2.0);
487        // Unique parameters specific to graph databases
488        assert_eq!(config.edge_traversal_cost, 0.02);
489        assert_eq!(config.multi_hop_penalty, 1.2);
490        assert_eq!(config.neighbor_lookup_cost, 0.015);
491        assert_eq!(config.effective_cache_pages, 10000);
492        assert_eq!(config.cache_hit_cost_factor, 0.1);
493        assert_eq!(config.shortest_path_base_cost, 10.0);
494        assert_eq!(config.path_enumeration_factor, 2.0);
495        assert_eq!(config.super_node_threshold, 10000);
496        assert_eq!(config.super_node_penalty, 2.0);
497        // Default parameters for control flow
498        assert_eq!(config.default_unwind_list_size, 3.0);
499        assert_eq!(config.default_loop_iterations, 3);
500        assert_eq!(config.default_select_branches, 2);
501    }
502
503    #[test]
504    fn test_ssd_config() {
505        let config = CostModelConfig::for_ssd();
506        assert_eq!(config.random_page_cost, 1.1);
507        assert_eq!(config.seq_page_cost, 1.0); // The rest should remain as default.
508    }
509
510    #[test]
511    fn test_in_memory_config() {
512        let config = CostModelConfig::for_in_memory();
513        assert_eq!(config.seq_page_cost, 0.1);
514        assert_eq!(config.random_page_cost, 0.1);
515    }
516
517    #[test]
518    fn test_builder_pattern() {
519        let config = CostModelConfig::new()
520            .with_seq_page_cost(0.5)
521            .with_random_page_cost(2.0)
522            .with_cpu_tuple_cost(0.02);
523
524        assert_eq!(config.seq_page_cost, 0.5);
525        assert_eq!(config.random_page_cost, 2.0);
526        assert_eq!(config.cpu_tuple_cost, 0.02);
527        assert_eq!(config.cpu_index_tuple_cost, 0.005); // “Default”
528    }
529
530    #[test]
531    fn test_join_reorder_min_improvement_defaults_to_zero() {
532        let config = CostModelConfig::default();
533        assert_eq!(config.strategy_thresholds.join_reorder_min_improvement, 0.0);
534    }
535}
linkrs_query/optimizer/cost/config.rs

linkrs_query/optimizer/cost/
config.rs
