基数估计

工作原理

对于简单的等值谓词，优化器根据最常见值列表或直方图估计选择性；对于范围谓词，它对直方图积分。对于连接，它结合输入基数和连接键推导的选择性，通常假设分布均匀且列之间独立。对于 AND 条件，它相乘选择性；对于 OR，相加后减去重叠部分。

这些假设正是弱点。城市和邮编相关，但独立相乘会低估或高估组合。倾斜的外键会让连接估计出错，例如一个客户拥有大多数订单。lower(email) 或类型转换等表达式可能遮蔽统计信息，除非有表达式索引或扩展统计。

诊断估计

在每个节点比较 EXPLAIN 的估算行数与 EXPLAIN ANALYZE 的实际行数。第一个大的偏差通常就是根因。检查统计信息上次收集时间、列是否有直方图、谓词是否可下推。在 PostgreSQL 中，pg_stats 显示直方图和去重估计；扩展统计可以捕获列间相关性。

何时使用

这在多连接分析查询、严重倾斜以及计划随参数值变化时最重要。唯一键上的点查估计很简单；对多年数据的报表查询，估计偏差 100 倍可能导致错误的连接策略并溢出到磁盘。

权衡与示例

更多统计信息改善估计，但增加分析时间和目录大小。采样更便宜，但对稀有值噪声更大。提示可以覆盖糟糕的估计，却冻结了一个可能随数据变化而错误的决定。

示例：WHERE city = 'Seattle' AND postal_code = '98101'。如果每个谓词估计为 1% 并相乘，规划器预期 0.01% 的行，而真实组合可能是 2%。嵌套循环看起来便宜，实际运行却远慢于哈希连接。扩展统计或改写查询可以恢复正常估计。

代码示例

export class SegmentTree {
  private readonly size: number;
  private readonly tree: number[];

  constructor(values: readonly number[]) {
    if (!Array.isArray(values)) throw new TypeError("values must be an array");
    for (const value of values) {
      if (typeof value !== "number" || !Number.isFinite(value)) {
        throw new TypeError("values must contain finite numbers");
      }
    }
    this.size = values.length;
    this.tree = new Array<number>(Math.max(4, this.size * 4)).fill(0);
    if (this.size > 0) this.build(values, 1, 0, this.size - 1);
  }

  sum(left: number, right: number): number {
    if (!Number.isInteger(left) || !Number.isInteger(right)) {
      throw new TypeError("range bounds must be integers");
    }
    if (left < 0 || right >= this.size || left > right) throw new RangeError("invalid range");
    return this.query(1, 0, this.size - 1, left, right);
  }

  update(index: number, value: number): void {
    if (!Number.isInteger(index) || index < 0 || index >= this.size) {
      throw new RangeError("index out of range");
    }
    if (typeof value !== "number" || !Number.isFinite(value)) {
      throw new TypeError("value must be a finite number");
    }
    this.assign(1, 0, this.size - 1, index, value);
  }

  private build(values: readonly number[], node: number, start: number, end: number): void {
    if (start === end) {
      this.tree[node] = values[start] ?? 0;
      return;
    }
    const middle = (start + end) >> 1;
    this.build(values, node * 2, start, middle);
    this.build(values, node * 2 + 1, middle + 1, end);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
  }

  private query(node: number, start: number, end: number, left: number, right: number): number {
    if (left <= start && end <= right) return this.tree[node];
    const middle = (start + end) >> 1;
    let total = 0;
    if (left <= middle) total += this.query(node * 2, start, middle, left, right);
    if (right > middle) total += this.query(node * 2 + 1, middle + 1, end, left, right);
    return total;
  }

  private assign(node: number, start: number, end: number, index: number, value: number): void {
    if (start === end) {
      this.tree[node] = value;
      return;
    }
    const middle = (start + end) >> 1;
    if (index <= middle) this.assign(node * 2, start, middle, index, value);
    else this.assign(node * 2 + 1, middle + 1, end, index, value);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
  }
}

const tree = new SegmentTree([2, 4, 6, 8, 10]);
console.log(tree.sum(1, 3));
tree.update(2, 0);
console.log(tree.sum(0, 4));
console.log(tree.sum(2, 2));

export interface Point {
  x: number;
  y: number;
}

export interface RegressionResult {
  slope: number;
  intercept: number;
  rSquared: number;
  predict: (x: number) => number;
}

export function linearRegression(points: readonly Point[]): RegressionResult {
  if (!Array.isArray(points) || points.length < 2) {
    throw new RangeError("points must contain at least two items");
  }
  for (const point of points) {
    if (!Number.isFinite(point.x) || !Number.isFinite(point.y)) {
      throw new TypeError("points must contain finite coordinates");
    }
  }
  const count = points.length;
  const meanX = points.reduce((total, point) => total + point.x, 0) / count;
  const meanY = points.reduce((total, point) => total + point.y, 0) / count;
  let numerator = 0;
  let denominator = 0;
  let total = 0;
  for (const point of points) {
    const dx = point.x - meanX;
    const dy = point.y - meanY;
    numerator += dx * dy;
    denominator += dx * dx;
    total += dy * dy;
  }
  if (denominator === 0) throw new RangeError("x values must not all be equal");
  const slope = numerator / denominator;
  const intercept = meanY - slope * meanX;
  const rSquared = total === 0 ? 1 : (numerator * numerator) / (denominator * total);
  return { slope, intercept, rSquared, predict: (x) => intercept + slope * x };
}