Cost Analysis

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// Simple Nested Loop Join Cost
// Tuple-at-a-time processing
 
I/O Cost:
  C_io_snl = b_R + (n_R × b_S)
           = b_R + (b_R × f_R × b_S)
 
// Intuition: Read R once, scan S for every tuple in R
 
CPU Cost:
  C_cpu_snl = n_R × n_S × t_cpu
 
// Intuition: Compare every pair of tuples
 
Total Time:
  T_snl = (b_R × t_seq) + (n_R × b_S × t_seq) + (n_R × n_S × t_cpu)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// Block Nested Loop Join Cost
// Block-at-a-time processing with M memory blocks
 
I/O Cost:
  C_io_bnlj = b_R + ⌈b_R / (M - 1)⌉ × b_S
 
// Intuition: Read R once, scan S for every block-chunk of R
 
Best Case (R fits in memory, M > b_R):
  C_io_bnlj_best = b_R + b_S
 
CPU Cost:
  C_cpu_bnlj = n_R × n_S × t_cpu  // Same as SNL
 
// With hash optimization on outer buffer:
  C_cpu_bnlj_hash = n_R + n_S × (hash_probe_cost)
                  ≈ O(n_R + n_S)
 
Total Time:
  T_bnlj = (b_R × t_seq) + (⌈b_R/(M-1)⌉ × b_S × t_seq) + CPU_cost

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Index Nested Loop Join Cost
// Index probe for each outer tuple
 
I/O Cost:
  C_io_inlj = b_R + n_R × C_probe
 
Where C_probe (cost per index probe):
  // B-tree, unclustered, unique key:
  C_probe = H_I + 1  // Height + 1 data page
  
  // B-tree, clustered:
  C_probe = H_I      // No separate data page
  
  // With matches_per_key > 1:
  C_probe = H_I + ⌈matches_per_key / f_S⌉
 
// Adjusting for random I/O:
  T_io_inlj = (b_R × t_seq) + (n_R × C_probe × t_rand)
 
CPU Cost:
  C_cpu_inlj = n_R × (index_compare_cost + matches_per_key × t_cpu)
 
// Typically much lower than scan-based joins

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// BNLJ vs INLJ Break-Even Analysis
 
BNLJ I/O Cost = b_R + ⌈b_R/(M-1)⌉ × b_S
INLJ I/O Cost = b_R + n_R × C_probe
 
// Set equal (ignoring ceiling):
⌈b_R/(M-1)⌉ × b_S = n_R × C_probe
(b_R / (M-1)) × b_S = n_R × C_probe
 
// Solving for n_R (outer cardinality where INLJ breaks even):
n_R_break = (b_R × b_S) / ((M-1) × C_probe)
 
// Example: b_R=1000, b_S=200, M=52, C_probe=4
n_R_break = (1000 × 200) / (51 × 4) = 980 tuples
 
// If effective n_R < 980, INLJ wins (before random I/O penalty)
 
// Adjusting for random vs sequential I/O:
// INLJ effective cost = n_R × C_probe × (t_rand / t_seq)
// On HDD (ratio = 10): n_R_break = 980 / 10 = 98 tuples
// On SSD (ratio = 2):  n_R_break = 980 / 2 = 490 tuples

1
2
3
4
5
6
7
8
9
10
11
12
13

// Memory threshold for optimal BNLJ
 
Optimal when: M - 1 >= b_R
Therefore: M >= b_R + 1
 
// For our example: M >= 1001 blocks
 
// Cost when outer fits:
C_io_bnlj_optimal = b_R + b_S
                  = 1000 + 200 = 1200 I/Os (1.2 seconds on SSD)
 
// This is the theoretical minimum for any nested loop variant
// (Must read both relations at least once)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// PostgreSQL-style combined cost
 
Total_Cost = (seq_page_cost × sequential_reads) 
           + (random_page_cost × random_reads)
           + (cpu_tuple_cost × tuples_processed)
           + (cpu_index_tuple_cost × index_entries)
           + (cpu_operator_cost × operator_evaluations)
 
// Default PostgreSQL values:
seq_page_cost = 1.0
random_page_cost = 4.0
cpu_tuple_cost = 0.01
cpu_index_tuple_cost = 0.005
cpu_operator_cost = 0.0025
 
// Example: INLJ with 100,000 outer tuples, 4 I/Os per probe
Cost_INLJ = (1.0 × 1,000)           // Sequential read of outer
          + (4.0 × 400,000)         // Random index probes
          + (0.01 × 100,000)        // Outer tuple processing
          + (0.005 × 400,000)       // Index entries examined
          = 1,000 + 1,600,000 + 1,000 + 2,000
          = 1,604,000 cost units

1
2
3
4
5
6
7
8
9
10
11
12
13

// Output cardinality estimation
output_rows = n_R × n_S × selectivity
 
// For equality joins on keys:
selectivity ≈ 1 / max(distinct_R, distinct_S)
 
// Example: R has 100K tuples, 10K distinct join keys
//          S has 10K tuples, 10K distinct join keys (all unique)
selectivity = 1 / 10,000 = 0.0001
output_rows = 100,000 × 10,000 × 0.0001 = 100,000
 
// Output materialization cost (if needed):
output_cost = output_rows × tuple_size / page_size × write_cost

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

-- View current cost settings
SHOW seq_page_cost;        -- Default: 1.0
SHOW random_page_cost;     -- Default: 4.0
SHOW cpu_tuple_cost;       -- Default: 0.01
SHOW effective_cache_size; -- Expected OS cache size
 
-- Tune for SSD storage (random approaches sequential)
SET random_page_cost = 1.1;  -- Much closer to sequential
 
-- Tune for battery-backed cache with fast writes
SET seq_page_cost = 0.5;
SET random_page_cost = 0.5;
 
-- Tune for large memory systems
SET effective_cache_size = '64GB';  -- More optimistic caching assumptions
 
-- Per-query cost adjustment (testing)
SET LOCAL random_page_cost = 1.0;
EXPLAIN (ANALYZE, BUFFERS) SELECT ...;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

-- MySQL cost model server configuration
SET GLOBAL optimizer_switch = 'index_merge=on,block_nested_loop=on';
 
-- Join buffer size (affects BNLJ block size)
SET SESSION join_buffer_size = 4 * 1024 * 1024;  -- 4MB
 
-- View cost constants (MySQL 8.0+)
SELECT * FROM mysql.server_cost;
SELECT * FROM mysql.engine_cost;
 
-- Adjust disk I/O cost for SSD
UPDATE mysql.engine_cost 
SET cost_value = 0.25 
WHERE cost_name = 'io_block_read_cost';
 
FLUSH OPTIMIZER_COSTS;