第五章-统计信息与选择率

1
-- 高选择率，采用顺序扫描
2
EXPLAIN SELECT * FROM STUDENT WHERE sno > 2;
3
-- 结果：Seq Scan on student (cost=0.00..224.00 rows=9999 width=10)
4

5
-- 低选择率，采用索引扫描
6
EXPLAIN SELECT * FROM STUDENT WHERE sno < 2;
7
-- 结果：Index Scan using student_pkey on student (cost=0.29..8.30 rows=1 width=10)

1
#define DEFAULT_SEQ_PAGE_COST 1.0    // 顺序读的单页代价
2
#define DEFAULT_RANDOM_PAGE_COST 4.0 // 随机读的单页代价

1
-- 基本字段
2
starelid    -- 对应表的OID（来自PG_CLASS）
3
staattnum   -- 列的编号（来自PG_ATTRIBUTES）
4
stanullfrac -- NULL值率，NULL值所占比例
5
stawidth    -- 列的平均宽度
6
stadistinct -- 消重之后的数据个数或比例

1
-- STUDENT表统计信息
2
starelid | staattnum | stanullfrac | stawidth | stadistinct
3
---------+-----------+-------------+----------+-------------
4
24582    | 1         | 0           | 4        | -1          -- sno列
5
24582    | 2         | 0.142857    | 3        | -0.571429   -- sname列
6
24582    | 3         | 0.142857    | 4        | -0.285714   -- ssex列

1
-- 第一个槽位
2
starelid | staattnum | stakind1 | staop1 | stanumbers1          | stavalues1
3
---------+-----------+----------+--------+----------------------+------------------
4
24582    | 1         | 2        | 97     |                      | {1,2,3,4,5,6,7}  -- sno直方图
5
24582    | 2         | 1        | 98     | {0.285714,0.285714}  | {ls,zs}           -- sname MCV
6
24582    | 3         | 1        | 96     | {0.571429,0.285714}  | {1,2}             -- ssex MCV

1
CREATE STATISTICS STATEXT_STUDENT ON sno, sname, ssex FROM STUDENT;

1
CREATE STATISTICS STATEXT_STUDENT ON sno, sname, ssex FROM STUDENT;
2
ANALYZE STUDENT(sno, sname, ssex);
3

4
-- 查看统计信息
5
SELECT * FROM pg_statistic_ext WHERE stxname='statext_student';
6
-- 结果包含NDISTINCT和DEPENDENCIES信息

1
从N个记录中随机选取n个记录（0 < n <= N）
2
S1. [初始化] K = N - t, k = n - m
3
S2. [生成随机数] 0 <= V <= 1
4
S3. [生成跳过条件] p = 1 - k/K
5
S4. [检测] 如果 V < p，跳转至S6
6
S5. [纳入样本] m++, t++, 如果 m < n 跳转至S2
7
S6. [跳过] t++, K--, p *= 1 - k/K, 跳转至S4

1
old_density = old_rel_tuples / old_rel_pages;
2
new_density = scanned_tuples / scanned_pages;
3
multiplier = (double) scanned_pages / (double) total_pages;
4
updated_density = old_density + (new_density - old_density) * multiplier;
5
reltuples = floor(updated_density * total_pages + 0.5);

1
if (OidIsValid(eqopr) && OidIsValid(ltopr)) {
2
    stats->compute_stats = compute_scalar_stats;  // 有等值和不等值操作符
3
} else if (OidIsValid(eqopr)) {
4
    stats->compute_stats = compute_distinct_stats; // 只有等值操作符
5
} else {
6
    stats->compute_stats = compute_trivial_stats;  // 其他情况
7
}

1
初始状态：
2
samplerows = 7    -- 样本容量
3
null_cnt = 1      -- NULL值个数
4
nonnull_cnt = 6   -- 非NULL值个数
5
toowide_cnt = 0   -- 超长值的个数
6
total_width = 18  -- 非NULL值的长度总和
7

8
排序后：
9
ndistinct = 4     -- 去掉重复值和NULL值之后的个数
10
stanullfrac = 1/7 -- NULL值比例
11
stdwidth = 3      -- 平均宽度
12
stadistinct = 4/7 -- 去重比例

1
// 排序前编号：0, 1, 2, 3, 4, 5
2
// 排序后编号：1, 5, 2, 3, 0, 4
3
// 相关系数公式：ρ = (n * ∑xd - ∑x * ∑d) / (√(n * ∑x² - (∑x)²) * √(n * ∑d² - (∑d)²))

1
for (k = 2; k <= numattrs; k++) {
2
    generator = generator_init(numattrs, k);
3
    while ((combination = generator_next(generator))) {
4
        item->ndistinct = ndistinct_for_combination(...);
5
    }
6
}

1
// MVDependencies：记录整个多列统计信息的函数依赖关系
2
typedef struct MVDependencies {
3
    uint32 magic;
4
    uint32 type;
5
    uint32 ndeps;
6
    MVDependency *deps[FLEXIBLE_ARRAY_MEMBER];
7
} MVDependencies;
8

9
// MVDependency：记录每个单独的函数依赖关系
10
typedef struct MVDependency {
11
    double degree;           // 函数依赖度
12
    AttrNumber nattributes;  // 涉及的属性数量
13
    AttrNumber attributes[FLEXIBLE_ARRAY_MEMBER];
14
} MVDependency;

1
-- 约束条件：A = 1 AND B = 1
2
-- 统计信息键值：{A, B}, {A, B, C}, {B, C, D}
3
-- 最适合使用：{A, B}（交集=2，键值数=2）

1
P(A = Const, B = Const) = P(A = Const) * (d + (1-d) * P(B = Const))
2
其中d是{A -> B}的函数依赖度

1
while (true) {
2
    dependency = find_strongest_dependency(stat, dependencies, clauses_attnums);
3
    s2 = clause_selectivity(root, clause, ...);
4
    s1 *= (dependency->degree + (1 - dependency->degree) * s2);
5
}

1
typedef struct RangeQueryClause {
2
    struct RangeQueryClause *next;
3
    Node *var;              // 属性（列）
4
    bool have_lobound;      // 是否有下界
5
    bool have_hibound;      // 是否有上界
6
    Selectivity lobound;    // 下界选择率
7
    Selectivity hibound;    // 上界选择率
8
} RangeQueryClause;

1
if (上界和下界同时存在) {
2
    s2 = hibound + lobound - 1.0;  // P(A > x) + P(A < y) = 1 - P(A > x AND A < y)
3
    s2 += nulltestsel(IS_NULL);     // 考虑NULL值
4
    s1 *= s2;
5
} else {
6
    if (只有下界) s1 *= lobound;
7
    if (只有上界) s1 *= hibound;
8
}

1
eqsel/neqsel
2
    ↓
3
eqsel_internal(negate)
4
    ↓
5
const? → var_eq_const
6
nonconst? → var_eq_non_const

1
selec = S(x2)×S(y2) + S(x3)×S(y4) + S(x4)×S(y3) + S(x4)×S(y4)
2
       ─────────────────────────────────────────────────────────
3
                          N × N

1
for (i = 0; i < sslot1.nvalues; i++) {
2
    for (j = 0; j < sslot2.nvalues; j++) {
3
        if (值相等) {
4
            matchprodfreq += sslot1.numbers[i] * sslot2.numbers[j];
5
            hasmatch1[i] = hasmatch2[j] = true;
6
            nmatches++;
7
            break;
8
        }
9
    }
10
}