IT技术博客大学习 共学习 共进步
全部 移动开发 后端 数据库 AI 算法 安全 DevOps 前端 设计 开发者

关于大区间过滤优化内存设计

淘宝网综合业务平台团队博客 2012-12-11 13:36:09 累计浏览 2,698 次
本机暂存

主要对一般docId为下标对应域值的结构做了改造,如果大家有更好的建议,欢迎大家提议和拍砖。

主要思路:

生成一个下标为
Term 遍历的Postion 且值为域值的数组:

A[p]=field value

因为域值并不会像docId一样为唯一键递增,所以在创建的时候

初始化:

Int [] A = new Int[reader.maxDoc()]

结束的时候如果 p<A.length(因为肯定有多个DocId对应相同域值)

则释放那些空闲空间


整个内存使用率取决于该值的重复率,重复越多则内存越节省,从我们接入绝大多数业务的类型需要进行大区间过滤的使用场景看都是最近几年的时间类型,类似于20101202,所以这样的数据重复率还是很高的。

第二个Int数组是以DocId为数组下标,域的遍历Postion为值的数组列表。


这样做的好处是将原来如果域为Long型的数组转变成了Int数组,节省了一倍的内存开销。

另外这里不是一次性初始化开辟reader.maxDoc()大小的数组,而是通过懒加载逐步将这个数组列表填满。

实现方式:

数组个数:N = reader.maxDoc()/K K为可配置大小,主要是将一个大数组分隔成多个小数组的关键因子,设置的小理论上会更节省内存),如下所示:


每次查询例如 l_t:[ 20101202 TO 20111202],查询这个区间内的DocId分布在那几个数组内,然后将DocId减去归属第N个数组的起始偏移量做为数组下标,域值的遍历Postion做为值填充数组。

如果下一个区间查询
例如是l_t:[20091202 TO 20101203],如果恰巧归属的数组已经创建过了,那么只需要填充20091202 To 20101201的归属数组,否则创建数组列表中还没有创建过的数组,并填充相应域的遍历Postion值。

接下来的查询如果是在已填充的区间内的区间查询则不需要再填充,其他查询情况以此类推。

最坏情况是查询条件导致这个数组列表的所有数组全部生成并填充完毕。

大小为Int[maxDoc]

查询过滤:

根据查询区间的最小值和最大值,查询出2值对应Term遍历的postion, Low=minPostion,

High=maxPostion

在根据query后得到的docList 进行过滤,通过docId 定位到数组列表的对应数组单元的域值Term postion 值,如果满足
minPostion<=currentPostion<=maxPostion
则代表满足区间。(因为sortable的域在构建索引已经是按照大小排序好存储)


将获取到的pn 跟之前的minPostionmaxPostion比较,发现只有p2<p3<p5,那么满足条件的docdoc3,doc4,doc5,doc7,doc8 doc9,其他的将其过滤。

最后附上获取域Termpostion代码

Java代码
  1. TermDocs termDocs = reader.termDocs();  

  2.      TermEnum termEnum = reader.terms (new Term (field));  

  3.      long[] mterms = newlong [reader.maxDoc()];  

  4. try {  

  5.        do {  

  6.          Term term = termEnum.term();  

  7.          if (term==null || term.field() != field || t >= mterms.length) break;  

  8.          // store term text  

  9.          mterms[p] = NumberUtils  

  10.                                .SortableStr2long(term.text());  

  11.          termDocs.seek (termEnum);  

  12.          while (termDocs.next()) {  

  13.            retArray(termDocs.doc(),p);//填充以(docId-offset)为下标,postion为值的数组列表。  

  14.          }  

  15.          p++;  

  16.        } while (termEnum.next());  

  17.      } finally {  

  18.        termDocs.close();  

  19.        termEnum.close();  

  20.      }  

  21. if (p < mterms.length) {  

  22.        // //terms 在docment中有大量重复,那么p肯定远小于maxdoc,那么截断多余出来的内存空间  

  23.        long [] terms = newlong [p];  

  24.        System.arraycopy (mterms, 0, terms, 0, p);  

  25.        mterms = terms;  

  26.      }  

同分类推荐文章

  1. 对基本有序的序列排序算法 (2026-06-11 17:46:49)
  2. Four Levels Of Customer Understanding (2026-05-22 21:00:00)
  3. 除法的意义 (2026-04-12 20:52:17)

查看更多 算法 文章 →

建议继续学习

  1. SmartSprites - 命令行形式的CSS Sprites生成器 (累计阅读 123,894)
  2. Java开发岗位面试题归类汇总 (累计阅读 22,155)
  3. 红黑树并没有我们想象的那么难(上) (累计阅读 21,494)
  4. android 开发入门 (累计阅读 19,527)
  5. 我的PHP,Python和Ruby之路 (累计阅读 13,146)
  6. HashMap解决hash冲突的方法 (累计阅读 12,652)
  7. 为什么算法这么难? (累计阅读 12,397)
  8. 浅谈MySQL索引背后的数据结构及算法 (累计阅读 11,902)
  9. 加州求职记 (累计阅读 11,561)
  10. 海量数据面试题举例 (累计阅读 11,114)