Lucene数值型区间查询的优化方案

NumericField和NumericRangeQuery是Lucene

针对数值型区间查询的优化方案。在展开阐述

NumericField

和NumbericRanageQuery

的实现原理之前，对于Lucene范围查询的实现和概念可以参考博文《TermRangeQuery源码解析》一文。

从Lucene 2.9 开始，提供对数字范围的支持，然而欲使用此查询，必须使用NumericField 添加域，使用Lucene原生API：

Java代码

1. document.add(new NumericField(name).setIntValue(value));

 

或者使用NumericTokenStream添加域：

Java代码

1. Field field = new Field(name, new NumericTokenStream(precisionStep).setIntValue(value));
2. field.setOmitNorms(true);
3. field.setOmitTermFreqAndPositions(true);
4. document.add(field);

 

如果要在Solr框架上使用需要定义schema.xml:

Java代码

2. mitNorms=“true” positionIncrementGap=“0″/>
4. mitNorms=“true” positionIncrementGap=“0″/>

 

 solr在构建索引的时候将会会根据定义在schema.xml中的filedType来构造field,

所以如果定义为trieField则在构造field的时候调用TrieField类的createField()方法：

Java代码

1. public Fieldable createField(SchemaField field, String externalVal, float boost) {
2. boolean indexed = field.indexed();
3. boolean stored = field.stored();
4.  
5. if (!indexed && !stored) {
6. if (log.isTraceEnabled())
7. log.trace(“Ignoring unindexed/unstored field: ” + field);
8. return null;
9. }
10. //构建NumericField
11. final NumericField f = new NumericField(field.getName(), precisionStep, stored ? Field.Store.YES :
12. Field.Store.NO, indexed);
13. switch (type) {//根据具体field类型来set具体类型值
14. case INTEGER:
15. f.setIntValue(Integer.parseInt(externalVal));
16. break;
17. case FLOAT:
18. f.setFloatValue(Float.parseFloat(externalVal));
19. break;
20. case LONG:
21. f.setLongValue(Long.parseLong(externalVal));
22. break;
23. case DOUBLE:
24. f.setDoubleValue(Double.parseDouble(externalVal));
25. break;
26. case DATE:
27. f.setLongValue(dateField.parseMath(null, externalVal).getTime());
28. break;
29. default:
30. throw new SolrException(SolrException.ErrorCode.SERVER_ERROR, “Unknown type for trie field: ” + type);
31. }
32.  
33. f.setOmitNorms(field.omitNorms());
34. f.setIndexOptions(getIndexOptions(field, externalVal));
35. f.setBoost(boost);
36. return f;
37. }

 

构造Field后经过docment.add()后再经Wirter.updateDocument()，会经过Lucene构造索引流程来将Doc

转变成索引。在其中DocInverterPerField.processFields()的过程就是将该域所制定的分词规则将其域值

切分为term后通过CharTermAttribute提交给其consumer对象进行下一步的构建索引流程，

而这个其中最重要的部分就是NumericField.tokenStreamValue()方法：

Java代码

1. public TokenStream tokenStreamValue() {
2. if (!isIndexed())
3. return null;
4. if (numericTS == null) {
5. // lazy init the TokenStream as it is heavy to instantiate (attributes,…),
6. // if not needed (stored field loading)
7. numericTS = new NumericTokenStream(precisionStep);
8. // initialize value in TokenStream
9. if (fieldsData != null) {
10. assert type != null;
11. final Number val = (Number) fieldsData;
12. switch (type) {
13. case INT:
14. numericTS.setIntValue(val.intValue()); break;
15. case LONG:
16. numericTS.setLongValue(val.longValue()); break;
17. case FLOAT:
18. numericTS.setFloatValue(val.floatValue()); break;
19. case DOUBLE:
20. numericTS.setDoubleValue(val.doubleValue()); break;
21. default:
22. assert false : “Should never get here”;
23. }
24. }
25. }
26. return numericTS;
27. }

 

NumericTokenStream stream = field.tokenStreamValue(); 执行完毕后返回TokenStream,

TokenStream在Lucene中是决定如何进行对域值进行分词的核心类，而其中的incrementToken()

方法就是实现分词关键方法，在回过头来看NumericTokenStream的这个方法：

Java代码

1. public boolean incrementToken() {
2. if (valSize == 0)
3. throw new IllegalStateException(“call set???Value() before usage”);
4. if (shift >= valSize)
5. return false;
6.  
7. clearAttributes();//置空termAttr
8. /**
9. *NumericTokenStream的value虽然是数字型，
10. *但是Lucene的Token只能保持字符串
11. *所以接下的动作是将数字编码成字符串，
12. *然后才作为某个域的域值存入索引
13. */
14. final char[] buffer;
15. switch (valSize) {
16. case 64:// 首先分配TermBuffer，然后将数字编码为字符串
17. //重置ternAtt’s buffer的大小
18. buffer = termAtt.resizeTermBuffer(NumericUtils.BUF_SIZE_LONG);
19. //longToPrefixCoded 方法变是将Long型的value值编码成字符串并放入到termAtt.buffer中
20. termAtt.setTermLength(NumericUtils.longToPrefixCoded(value, shift, buffer));
21. break;
22.  
23. case 32:
24. buffer = termAtt.resizeTermBuffer(NumericUtils.BUF_SIZE_INT);
25. termAtt.setTermLength(NumericUtils.intToPrefixCoded((int) value, shift, buffer));
26. break;
27.  
28. default:
29. // should not happen
30. throw new IllegalArgumentException(“valSize must be 32 or 64″);
31. }
32.  
33. typeAtt.setType((shift == 0) ? TOKEN_TYPE_FULL_PREC : TOKEN_TYPE_LOWER_PREC);
34. posIncrAtt.setPositionIncrement((shift == 0) ? 1 : 0);
35. shift += precisionStep;
36. return true;
37. }

 

接下来看看NumericUtils是如何将数值型转成字符串的：

Java代码

1. public static int longToPrefixCoded(final long val, final int shift, final char[] buffer) {
2. if (shift>63 || shift<0)
3. throw new IllegalArgumentException(“Illegal shift value, must be 0..63″);
4. //shift初始为0; valSize = 64; 根据(63 - shift) / 7 + 1计算出当前Token的buffer的长度
5. int nChars = (63-shift)/7 + 1, len = nChars+1;
6. //buffer[0] = 0×20+0;
7. buffer[0] = (char)(SHIFT_START_LONG + shift);
8. long sortableBits = val ^ 0x8000000000000000L;
9. sortableBits >>>= shift;
10. while (nChars>=1) {
11. // Store 7 bits per character for good efficiency when UTF-8 encoding.
12. // The whole number is right-justified so that lucene can prefix-encode
13. // the terms more efficiently.
14. //每七位组成一个uft-8的编码
15. buffer[nChars--] = (char)(sortableBits & 0x7f);
16. sortableBits >>>= 7;
17. }
18. return len;
19. }

 

将incrementToken和NumericUtils.longToPrefixCoded()结合来看将按照如下流程进行处理：

（1） 进入longToPrefixCoded(),如果shift初始为0; valSize = 64; 根据(63 – shift) / 7 + 1计算出当前Token的buffer的长度

（2）buffer[0]存放的是32+shift

（3）sortableBits = value ^ 0x8000000000000000L，sortableBits >>>= shift （右移shift位）

（4）迭代buffer[buffer.size-1 -> 1]各个值为buffer[n] = (char) (sortableBits & 0x7f)，

sortableBits >>>= 7 ，再将sortableBits左移7位

（5） 出longToPrefixCoded(),设置TermAttribute的termBuffer为buffer，以及bufferLength等属性

（6） shift += precisionStep 如果shift >= valSize(64,以long为例)了并返回false将会退出切分char过程，否则进入仍然进入步骤（1）

所以我们以value=2048,precisionStep =8为例经过编码后的TOKENSTREAM流为：

Java代码

1. [ 32 1 0 0 0 0 0 0 0 16 0 ]
2. [ 40 64 0 0 0 0 0 0 8 ]
3. [ 48 32 0 0 0 0 0 0 ]
4. [ 56 16 0 0 0 0 0 ]
5. [ 64 8 0 0 0 0 ]
6. [ 72 4 0 0 0 ]
7. [ 80 2 0 0 ]
8. [ 88 1 0 ]

 

也就是一个2048的Long型数值被 NumericTokenStream“切” 成了8个length不相同的字符串。为了显示precisionStep的作用，我们在使用value=2048,precisionStep=4来看看会出现什么情况：

Java代码

1. [ 32 1 0 0 0 0 0 0 0 16 0 ]
2. [ 36 8 0 0 0 0 0 0 1 0 ]
3. [ 40 64 0 0 0 0 0 0 8 ]
4. [ 44 4 0 0 0 0 0 0 0 ]
5. [ 48 32 0 0 0 0 0 0 ]
6. [ 52 2 0 0 0 0 0 0 ]
7. [ 56 16 0 0 0 0 0 ]
8. [ 60 1 0 0 0 0 0 ]
9. [ 64 8 0 0 0 0 ]
10. [ 68 64 0 0 0 ]
11. [ 72 4 0 0 0 ]
12. [ 76 32 0 0 ]
13. [ 80 2 0 0 ]
14. [ 84 16 0 ]
15. [ 88 1 0 ]
16. [ 92 8 ]

 

很明显，precisionStep 越小那么被“切”成的的字符串就会多。precisionStep 越小则value被“切”成的term就越多，也就是说索引体积将会增大。被“切”分的term越多则可能在NumericRangeQuery中被细分的小区间中存在的可能性也就越高，那么查询遍历的次数也就越少，性能也就越好。但这不是绝对的，一般而言，搜索速度被降低是因为很多的在index中搜索term的列举，因此，理想的precisionStep只能依据自己的测试而获取。同时请注意如果只是对其进行sort而不需要范围查询可以将precisionStep=Integer.MAX_VALUE。这样只会生成一个term，从而不会增大索引体积。

NumericRangeQuery是MultiTermQuery，所以也是遵循Lucene的搜索流程：

Query树->rewrite->weight
树
->Scorer
树,这块的详细流程请看笔者的另一篇Blog
《TermRangeQuery源码解析》文章将会详细这块内容，所以这里不在复述。

query rewrite过程：

Java代码

1. Query result = new ConstantScoreQuery(new MultiTermQueryWrapperFilter(query));
2. result.setBoost(query.getBoost());
3. return result;

 

构建weight树：

Java代码

1. public Weight createWeight(Searcher searcher) {
2. return new ConstantScoreQuery.ConstantWeight(searcher);
3. }

 

构建scorer树：

Java代码

1. public Scorer scorer(IndexReader reader, boolean scoreDocsInOrder, boolean topScorer) throws IOException {
2. return new ConstantScorer(similarity, reader, this);
3. }

 

上述过程后，整个区间过滤DocIdSet将交由MultiTermQueryWrapperFilter的getDocIdSet方法进行区间查询过滤：

Java代码

1. public DocIdSet getDocIdSet(IndexReader reader) throws IOException {
2. final TermEnum enumerator = query.getEnum(reader);////得到NumericRangeQuery的Term枚举器
3. try {
4. // if current term in enum is null, the enum is empty -> shortcut
5. if (enumerator.term() == null)
6. return DocIdSet.EMPTY_DOCIDSET;
7. // else fill into a OpenBitSet
8. final OpenBitSet bitSet = new OpenBitSet(reader.maxDoc());//创建包含多个Term的文档号集合
9. new TermGenerator() {
10. public void handleDoc(int doc) {
11. bitSet.set(doc);
12. }
13. }.generate(reader, enumerator);
14. return bitSet;
15. } finally {
16. enumerator.close();
17. }
18. }

 

 终终满足区间查询条件的docId都将填入OpenBitSet中，而可以看到整个最关键的部分还是在NumericRangeQuery如何获取满足条件的Term枚举，即如上的代码    final TermEnum enumerator = query.getEnum(reader)部分：

Java代码

1. protected FilteredTermEnum getEnum(final IndexReader reader) throws IOException {
2. return new NumericRangeTermEnum(reader);
3. }

 

继续看NumericRangeTermEnum的构造函数的关键代码部分：

Java代码

1. switch (valSize) {
2. case 64: {
3. // lower
4. long minBound = Long.MIN_VALUE;
5. if (min instanceof Long) {
6. minBound = min.longValue();
7. } else if (min instanceof Double) {
8. minBound = NumericUtils.doubleToSortableLong(min.doubleValue());
9. }
10. if (!minInclusive && min != null) {
11. if (minBound == Long.MAX_VALUE) break;
12. minBound++;
13. }
14.  
15. // upper
16. long maxBound = Long.MAX_VALUE;
17. if (max instanceof Long) {
18. maxBound = max.longValue();
19. } else if (max instanceof Double) {
20. maxBound = NumericUtils.doubleToSortableLong(max.doubleValue());
21. }
22. if (!maxInclusive && max != null) {
23. if (maxBound == Long.MIN_VALUE) break;
24. maxBound–;
25. }
26. //将查询区间分解成若干个小的查询区间
27. NumericUtils.splitLongRange(new NumericUtils.LongRangeBuilder() {
28. //@Override
29. public final void addRange(String minPrefixCoded, String maxPrefixCoded) {
30. rangeBounds.add(minPrefixCoded);
31. rangeBounds.add(maxPrefixCoded);
32. }
33. }, precisionStep, minBound, maxBound);
34. break;
35. }

 

这部分关键代码就是将一个查询范围区间分解成若干个小的查询区间，如区间[1，12340]将终终被分解成:

Java代码

1. (1) low [ 32 1 0 0 0 0 0 0 0 0 1 ] high [ 32 1 0 0 0 0 0 0 0 0 15 ]
2. (2) low [ 32 1 0 0 0 0 0 0 0 96 48 ] high [ 32 1 0 0 0 0 0 0 0 96 52 ]
3. (3) low [ 36 8 0 0 0 0 0 0 0 1 ] high [ 36 8 0 0 0 0 0 0 0 15 ]
4. (4) low [ 36 8 0 0 0 0 0 0 6 0 ] high [ 36 8 0 0 0 0 0 0 6 2 ]
5. (5) low [ 40 64 0 0 0 0 0 0 1 ] high [ 40 64 0 0 0 0 0 0 15 ]
6. (6) low [ 44 4 0 0 0 0 0 0 1 ] high [ 44 4 0 0 0 0 0 0 2 ]

 

六个小区间，NumericRangeTermEnum枚举器根据next()方法来判断term是否在这些区间内，如果在则代表可以继续遍历，直到某个currentTerm和currentUpperBound（当前子high区间的值）字符串比较更大，则认为进入下一个子区间进行比较，主要代码逻辑如下所示：

Java代码

1. public boolean next() throws IOException {
2. // if a current term exists, the actual enum is initialized:
3. // try change to next term, if no such term exists, fall-through
4. if (currentTerm != null) {
5. assert actualEnum != null;
6. if (actualEnum.next()) {
7. currentTerm = actualEnum.term();
8. if (termCompare(currentTerm))
9. return true;
10. }
11. }
12.  
13. // if all above fails, we go forward to the next enum,
14. // if one is available
15. currentTerm = null;
16. while (rangeBounds.size() >= 2) {
17. assert rangeBounds.size() % 2 == 0;
18. // close the current enum and read next bounds
19. if (actualEnum != null) {
20. actualEnum.close();
21. actualEnum = null;
22. }
23. final String lowerBound = rangeBounds.removeFirst();
24. this.currentUpperBound = rangeBounds.removeFirst();
25. // create a new enum
26. actualEnum = reader.terms(termTemplate.createTerm(lowerBound));
27. currentTerm = actualEnum.term();
28. if (currentTerm != null && termCompare(currentTerm))
29. return true;
30. // clear the current term for next iteration
31. currentTerm = null;
32. }
33.  
34. // no more sub-range enums available
35. assert rangeBounds.size() == 0 && currentTerm == null;
36. return false;
37. }

 

接下来举例说明区间比较的逻辑顺序，假设目前索引中有1024和12341 2个值，precisionStep=4，查询范围为[1,12340]。

1024在索引中存储中存储结构为：

Java代码

1. 1 [ 32 1 0 0 0 0 0 0 0 8 0 ]
2. 2 [ 36 8 0 0 0 0 0 0 0 64 ]
3. 3 [ 40 64 0 0 0 0 0 0 4 ]
4. 4 [ 44 4 0 0 0 0 0 0 0 ]
5. 5 [ 48 32 0 0 0 0 0 0 ]
6. 6 [ 52 2 0 0 0 0 0 0 ]
7. 7 [ 56 16 0 0 0 0 0 ]
8. 8 [ 60 1 0 0 0 0 0 ]
9. 9 [ 64 8 0 0 0 0 ]
10. 10 [ 68 64 0 0 0 ]
11. 11 [ 72 4 0 0 0 ]
12. 12 [ 76 32 0 0 ]
13. 13 [ 80 2 0 0 ]
14. 14 [ 84 16 0 ]
15. 15 [ 88 1 0 ]
16. 16 [ 92 8 ]li>

 

备注：low[1] (代表：[ 32 1 0 0 0 0 0 0 0 0 1 ])

high[1](代表：[ 32 1 0 0 0 0 0 0 0 0 15 ])

1024[1] (代表：[ 32 1 0 0 0 0 0 0 0 8 0 ] )，其他依次类推

第一次查询low[1]-high[1],发现1024[1]-1024[16]都不在该区间，则进入low[2]–high[2]比较

第二次查询low[2]–high[2],发现1024[1]-1024[16]都不在该区间，则进入low[3]–high[3]比较

第三次查询low[3]–high[3],发现1024[1]-1024[16]都不在该区间，则进入low[4]–high[4]比较

第四次查询low[4]–high[4],发现1024[1]-1024[16]都不在该区间，则进入low[5]–high[5]比较

第五次查询low[5]–high[5],发现1024[3]在该区间，则代表1024该值在[1,12340]区间内，将该term对应的docId放入OpenBitSet中。

接下来看12341在索引中的存储结构：

Java代码

1. 1 [ 32 1 0 0 0 0 0 0 0 96 53 ]
2. 2 [ 36 8 0 0 0 0 0 0 6 3 ]
3. 3 [ 40 64 0 0 0 0 0 0 48 ]
4. 4 [ 44 4 0 0 0 0 0 0 3 ]
5. 5 [ 48 32 0 0 0 0 0 0 ]
6. 6 [ 52 2 0 0 0 0 0 0 ]
7. 7 [ 56 16 0 0 0 0 0 ]
8. 8 [ 60 1 0 0 0 0 0 ]
9. 9 [ 64 8 0 0 0 0 ]
10. 10 [ 68 64 0 0 0 ]
11. 11 [ 72 4 0 0 0 ]
12. 12 [ 76 32 0 0 ]
13. 13 [ 80 2 0 0 ]
14. 14 [ 84 16 0 ]
15. 15 [ 88 1 0 ]
16. 16 [ 92 8 ]

 

根据上面的分析规则：

第一次查询low[1]–high[1],发现12341[1]-12341[16]都不在该区间，则进入low[2]–high[2]比较

第二次查询low[2]–high[2],发现12341[1]-12341[16]都不在该区间，则进入low[3]–high[3]比较

第三次查询low[3]–high[3],发现12341[1]-12341[16]都不在该区间，则进入low[4]–high[4]比较

第四次查询low[4]–high[4],发现12341[1]-12341[16]都不在该区间，则进入low[5]–high[5]比较

第五次查询low[5]–high[5],发现12341[1]-12341[16]都不在该区间，则进入low[6]–high[6]比较

第六次查询low[6]–high[6],发现12341[1]-12341[16]都不在该区间，next()方法返回false;

另外需要了解的是每次子区间查询会重定位新的term枚举：

Java代码

1. actualEnum = reader.terms(termTemplate.createTerm(lowerBound));

 

那么以1024为例，也就是说不需要每次都是从1024[1]开始重新比较，可能是从1024[2-n]的某个最临近子区间的一个term值来进行比较，这样比较次数将大幅减少。

和TermRangeQuery的优势：

（1）支持数值型的范围查询

（2）使用子区间来减少term枚举的遍历次数，极大提高性能

缺点：

（1）数值切分多个term存储，增大索引体积

（2）并不能完全杜绝范围查询的性能损耗，仍然有范围比较，枚举遍历等性能损耗。

总结：

NumericRangeQuery虽然能提高区间查询的性能，但是并不能完全杜绝区间查询带来的性能损耗，如果需要完全消除区间查询带来的性能消耗，只能使用区间过滤的方式：将docId和 rangeUid作为数组在内存中保存起来，然后保证满足其他查询条件的docId同时也在这个区间数组范围内才认为是终终满足条件的docId，否则过滤该docId。只有这样的设计才能完全消耗区间带来的性能损失。所以NumericRangeQuery在数据量不大和查询区间不大的情况下作为范围查询的首xuan方案还是没有问题的。

---