基于代价的查询优化器如何估计不同执行计划的代价并选择最优者？
How does a cost-based query optimizer estimate and choose the best execution plan?
优化器利用统计信息（直方图、基数、选择率）估算每个算子处理的行数与 I/O、CPU 成本，枚举候选计划后选估计总代价最低者。基数估计误差会被连接层层放大，是优化器最常见也最难的误差来源。
The optimizer uses statistics (histograms, cardinality, selectivity) to estimate rows processed and I/O/CPU cost per operator, enumerates candidate plans, and picks the one with the lowest estimated total cost. Cardinality estimation errors are amplified across joins and are the most common, hardest source of optimizer mistakes.
难度 专业 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Selinger et al., Access Path Selection in a Relational Database Management System, IBM CACM 1979 (System R)
Selinger et al., Access Path Selection in a Relational Database Management System, IBM CACM 1979 (System R)
独立核验依据 · Independent verification: 核验依据 1 DOI 10.1145/582095.582099
#查询优化 #代价模型 #基数估计
向量数据库的 HNSW 索引如何在亿级向量上实现亚线性近似最近邻搜索？
How does an HNSW index in vector databases achieve sublinear approximate nearest-neighbor search over hundreds of millions of vectors?
HNSW 把向量组织成多层可导航小世界图，顶层稀疏用于快速远距离跳转、底层稠密保证召回。查询从顶层贪心下行，仅需访问少量节点即可逼近最近邻，其复杂度约为对数级，但需权衡内存占用与召回率。
HNSW organizes vectors into a multi-layer navigable small-world graph: sparse upper layers enable fast long jumps and dense lower layers ensure recall. A query greedily descends from the top, visiting only a few nodes to approximate the nearest neighbor at roughly logarithmic cost, trading memory for recall.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：本题原挂出处与答案内容不符，已撤回；具体书目待补，暂不展示来源。
本题原挂出处与答案内容不符，已撤回；具体书目待补。
Previous citation withdrawn as unsupported for this answer; a specific source is pending.
#向量数据库 #近似最近邻 #HNSW
聚簇索引与非聚簇索引在数据物理排列上有什么不同？
How do clustered and non-clustered indexes differ in physical data arrangement?
聚簇索引的叶子节点直接存放整行数据，表中数据按索引键物理排序，因此一个表只能有一个。非聚簇索引的叶子指向数据行位置，查找需一次额外的书签定位（回表）。
A clustered index's leaf nodes store the whole row and the table is physically sorted by the key, so a table can have only one. A non-clustered index's leaf points to the row location, requiring an extra bookmark lookup (back to table) to fetch data.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
Garcia-Molina, Ullman, Widom, Database Systems: The Complete Book, 2nd ed.
Garcia-Molina, Ullman, Widom, Database Systems: The Complete Book, 2nd ed.
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL32684512W：Database Systems The C
#聚簇索引 #非聚簇索引 #回表
B+树索引为什么比二叉搜索树更适合磁盘上的数据库索引？
Why is a B+ tree index better suited than a binary search tree for on-disk database indexes?
B+树节点宽、出度大，树高通常只有两三层，一次查找只需很少次磁盘 I/O。所有数据集中在叶子层并以链表相连，范围扫描高效，是关系型数据库最常用的索引结构。
B+ trees have wide nodes and high fan-out, so the tree is only two or three levels tall and a lookup needs very few disk I/Os. All data sits in the leaf level linked as a list, enabling efficient range scans, which is why it is the most common relational index.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
Ramakrishnan & Gehrke, Database Management Systems, 3rd ed., McGraw-Hill
Ramakrishnan & Gehrke, Database Management Systems, 3rd ed.
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL16961668W：Database management sy
#B+树 #索引 #磁盘I/O
哈希连接（hash join）在什么条件下比嵌套循环连接更高效？
When is a hash join more efficient than a nested-loop join?
当两表都较大且连接键无现成索引时，哈希连接先对小表建哈希表再以大表探测，复杂度约 O(M+N)。它避免了对大表的逐行嵌套扫描，是分析型查询的常用策略。
When both tables are large and there is no suitable index on the join key, hash join builds a hash table on the smaller table and probes it with the larger one, at about O(M+N) complexity. It avoids row-by-row nested scans of the big table and is common in analytical queries.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Silberschatz 等,《Database System Concepts》第7版,McGraw-Hill,2019
A. Silberschatz et al., Database System Concepts, 7th ed., McGraw-Hill, 2019
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL21198749W：Database System Concep
#哈希连接 #查询执行 #连接算法