TopN是常见的运算,用SQL写出来是这样(以Oracle为例): select * from (select * from T order by x desc) where rownum<=N 这个SQL的运算逻辑从其语句上看,要先做排序(Order by),然后再取出前N条。我们知道,排序是个非常慢的动作,复杂度很高(n*logn),如果涉及数...【阅读全文】
一、 问题背景与适用场景在以前的文章中我们介绍过,关系数据库在进行表间关联时是使用HASH分段技术。设两个关联表的规模(记录数)分别是 N 和 M,则 HASH 分段技术的计算复杂度(关联字段的比较次数)大概是 SUM(Ni*Mi),其中 Ni 和 Mi 分别是 HASH 值为 i 的两表记录数,满足 N=SUM(Ni) 和 M=SUM(...【阅读全文】
问题描述 多维分析(OLAP)系统的汇总和切片,实际上是在计算分组汇总和条件过滤。切片过滤条件的情况多种多样,其中比较多的是枚举维度切片和二值维度切片。 枚举维度切片是指过滤条件中的in计算,例如:D5 in (valueB,valueC),也就是过滤条件字段在一个枚举范围内取值的情况。在实际应用中,...【阅读全文】