union索引合并算法

逃离我推掉我的手 2022-05-01 13:48 186阅读 0赞

/*
      Get best plan for a SEL_IMERGE disjunctive expression.
      SYNOPSIS
        get_best_disjunct_quick()
          param     Parameter from check_quick_select function
          imerge    Expression to use
          cost_est  Don't create scans with cost > cost_est NOTES index_merge cost is calculated as follows: index_merge_cost = cost(index_reads) + (see #1) cost(rowid_to_row_scan) + (see #2) cost(unique_use) (see #3) 1. cost(index_reads) =SUM_i(cost(index_read_i)) For non-CPK scans, cost(index_read_i) = {cost of ordinary 'index only' scan} For CPK scan, cost(index_read_i) = {cost of non-'index only' scan} 2. cost(rowid_to_row_scan) If table PK is clustered then cost(rowid_to_row_scan) = {cost of ordinary clustered PK scan with n_ranges=n_rows} Otherwise, we use the following model to calculate costs: We need to retrieve n_rows rows from file that occupies n_blocks blocks. We assume that offsets of rows we need are independent variates with uniform distribution in [0..max_file_offset] range. We'll denote block as "busy" if it contains row(s) we need to retrieve
          and "empty" if doesn't contain rows we need. Probability that a block is empty is (1 - 1/n_blocks)^n_rows (this applies to any block in file). Let x_i be a variate taking value 1 if block #i is empty and 0 otherwise. Then E(x_i) = (1 - 1/n_blocks)^n_rows; E(n_empty_blocks) = E(sum(x_i)) = sum(E(x_i)) = = n_blocks * ((1 - 1/n_blocks)^n_rows) = ~= n_blocks * exp(-n_rows/n_blocks). E(n_busy_blocks) = n_blocks*(1 - (1 - 1/n_blocks)^n_rows) = ~= n_blocks * (1 - exp(-n_rows/n_blocks)). Average size of "hole" between neighbor non-empty blocks is E(hole_size) = n_blocks/E(n_busy_blocks). The total cost of reading all needed blocks in one "sweep" is: E(n_busy_blocks) * disk_seek_cost(n_blocks/E(n_busy_blocks)) This cost estimate is calculated in get_sweep_read_cost(). 3. Cost of Unique use is calculated in Unique::get_use_cost function. ROR-union cost is calculated in the same way index_merge, but instead of Unique a priority queue is used. RETURN Created read plan NULL - Out of memory or no read scan could be built. */ 复制代码

转载于:https://juejin.im/post/5c2e0888518825444612f06d