我无法理解等深度直方图在查询优化中的作用.有人可以给我一些指向良好资源的指示或任何人都可以解释.我已经阅读了一些研究论文,但仍然无法说服我需要和使用等深度直方图.那么,有人可以用一个例子解释等深度直方图.
我们也可以合并直方图的桶,以便直方图变得足够小并且适合磁盘上的1页？
同等深度直方图中的桶边界是什么？
警告:我不是数据库内部的专家,所以这是一般性的,而不是具体的答案.
查询编译器将查询(通常在SQL中给出)转换为计划以获取结果.计划包括数据库引擎的低级"指令":扫描表T在列C中查找值V; 使用表T上的索引X来定位值V; 等等
查询优化是关于编译器决定哪个(可能很大的)备选查询计划具有最低成本.成本包括挂钟时间,IO带宽,中间结果存储空间,CPU时间等.从概念上讲,优化器正在搜索备用计划空间,评估每个成本以指导搜索,最终选择最便宜的搜索.
上面提到的成本取决于将读取和/或写入多少记录的估计,是否可以通过索引定位记录,将使用这些记录的哪些列,以及数据的大小和/或多少磁盘页面他们占据了.
反过来,这些数量通常取决于表中存储的确切数据值.例如select * from data where pay > 100,考虑pay索引列的位置.如果支付列没有超过100的值,那么查询非常便宜.索引的单个探测器会回答它.相反,结果集可以包含整个表.
这是直方图有用的地方.(等深度直方图只是保持直方图的一种方法.)在前面的查询中,直方图将在O(1)时间内提供查询将生成的行分数的估计值,而不确切知道这些行将包含哪些行.
实际上,优化器正在对数据的抽象"执行"查询.直方图就是抽象.(其他是可能的.)直方图可用于估计查询计划操作的成本和结果大小:例如,在批量插入和删除期间(可能导致生成临时索引)时连接结果大小和页面命中.
对于一个简单的内连接示例,假设我们知道如何分布两个表的整数值连接列:
Bins (25% each)
Table A Table B
0-100 151-300
101-150 301-500
151-175 601-700
176-300 1001-1100
很容易看出,表A的50%和表B的25%反映了可能的参与.如果这些是唯一值列,则有用的连接大小估计值为max(.5*| A |,.25*| B |).这是一个非常简单的例子.在许多(大多数？)案例中,分析需要更多的数学复杂性.对于连接,通常通过"连接"操作数的直方图来计算结果的估计直方图.这就是文学如此多样化,复杂化和有趣的原因.
博士论文经常进行调查,以简明的形式涵盖这样的大型技术文献,这些文献并不难阅读.(毕竟,候选人试图说服委员会他/她知道如何进行文献检索.) 这是一个这样的例子.