SpanQuery源码学习总结
原创
总体思路
SpanQuery实现的主要思路:
SpanQuery->SpanWeight->SpanScorer.
SpanScorer中包含一个Spans对象, SpanScorer把iterator()和twoPhraseIterator()方法都委托给了Spans对象. Spans类本身继承了了DocIdSetIterator, 也就是说Spans对象本身就代表了一个文档倒排表, 除了本身是一个倒排表外, Spans类还实现了nextStartPosition() /startPosition() /endPosition(), 当匹配某个文档的时候, 通过这三个接口可以遍历在当前文档的匹配位置, 用于实现短语的匹配.
SpanWeight包含一个getSpans(LeafReaderContext ctx, Postings requiredPostings)的抽象方法, 对于每个段生成一个Spans对象, 这个对象就是在SpanScorer中包含的对象.
SpanNearQuery
ES语法示例
{
"query": {
"span_near": {
"clauses": [
{ "span_term": { "field": "value1" } },
{ "span_term": { "field": "value2" } },
{ "span_term": { "field": "value3" } }
],
"slop": 12,
"in_order": false
}
}
}召回逻辑
召回候选集
通过多个子spans取交集得到的文档作为候选集.
过滤阶段
对多个spans的每一组匹配位置进行位置检测, 根据inOrder参数值确定使用NearSpansOrdered或NearSpansUnordered的算法. 详见后面的Spans类详解中的算法解释.
SpanOrQuery
ES语法示例
{
"query": {
"span_or" : {
"clauses" : [
{ "span_term" : { "field" : "value1" } },
{ "span_term" : { "field" : "value2" } },
{ "span_term" : { "field" : "value3" } }
]
}
}
}召回逻辑
通过多个子spans取并集获得召回文档集. (通过堆).
SpanNotQuery
ES语法示例
{
"query": {
"span_not": {
"include": {
"span_term": { "field1": "hoya" }
},
"exclude": {
"span_near": {
"clauses": [
{ "span_term": { "field1": "la" } },
{ "span_term": { "field1": "hoya" } }
],
"slop": 0,
"in_order": true
}
}
}
}
}要求匹配文档匹配include的SpanQuery, 且不能重叠匹配exclude的SpanQuery.
召回逻辑如下:
召回候选集
使用include的SpanQuery召回全部命中文档作为候选集.
过滤阶段1
使用exclude的SpanQuery对候选集中的文档做过滤, 若候选文档没有命中exclude的SpanQuery, 则直接作为命中文档返回. 若候选文档命中了exclude的SpanQuery, 则进入下一个过滤阶段.
过滤阶段2
对于同时命中了include和exclude的文档, 需要检测include和exclude的命中position是否有重合. 如include命中位置为[0,5], exclude命中位置为[7,8] 则没有重合. include命中位置为[0,5], exclude命中位置为[4,8], 则有重合.对于include和exclude命中位置有重合的文档, 过滤掉.
SpanContainingQuery
ES语法示例
{
"query": {
"span_containing": {
"little": {
"span_term": { "title": "b" }
},
"big": {
"span_near": {
"clauses": [
{ "span_term": { "title": "a" } },
{ "span_term": { "title": "c" } }
],
"slop": 5,
"in_order": true
}
}
}
}
}召回逻辑
召回候选集
通过little和big取交集作为候选集.
过滤阶段
对于阶段1的召回结果, 需要little匹配的position范围在big的匹配范围之内.
对于上面的例子, 即要求通过big匹配了"a"和"c"的同时, little的"b"必须出现在"a"和"c"的中间.
比如:
文档a x x b c可以匹配, 因为b出现在了a和c的中间.
文档a x x c b 则不能匹配, 因为b没有出现在a和c的中间.
匹配位置
需要注意, SpanContainingQuery匹配的位置是big的位置. 什么意思呢? 可以看下面的例子:
假设有如下query:
{
"query": {
"span_near": {
"clauses": [
{
"span_containing": {
"little": {
"span_term": {
"title": "b"
}
},
"big": {
"span_near": {
"clauses": [
{
"span_term": {
"title": "a"
}
},
{
"span_term": {
"title": "c"
}
}
],
"slop": 5,
"in_order": true
}
}
}
},
{
"span_term": {
"title": "d"
}
}
],
"slop": 0,
"in_order": true
}
}
}问是否可以匹配文档a x x b c d?
答案是可以. 最外层的span_near要求同时匹配span_containing和span_term(title=d)且两者无间隔(slop=0), 前面我们已经说过, 这个span_containing的匹配是能匹配上的, span_term(title=d)单独显然也是可以匹配上的, 那么如何计算两者的距离呢? 这时候就要知道span_containing实际匹配的position是多少了.
span_containing规定其匹配的position是big的position, 对应文档中的a x x b c, 因此距离d的距离是0, 因此整个query可以匹配文档.
可以想象, 如果span_containing匹配的position不是big而是little, 那么文档a x x b c d就不能匹配了. 因为如果span_containing匹配的是little的position, 那么相当于匹配文档中的b, 因此距离d的距离是1, slop=0的情况下就不能匹配了. 如果span_containing匹配的position不是big而是little, 那么就变成了另一种SpanQuery: SpanWithinQuery.
SpanWithinQuery
单独使用的时候召回逻辑与SpanContainingQuery完全一致. 只是匹配位置不同, SpanContainingQuery匹配位置用的big的, SpanWithinQuery匹配位置用的little的.
ES语法示例
{
"query": {
"span_within": {
"little": {
"span_term": { "title": "b" }
},
"big": {
"span_near": {
"clauses": [
{ "span_term": { "title": "a" } },
{ "span_term": { "title": "c" } }
],
"slop": 5,
"in_order": true
}
}
}
}
}召回逻辑
召回候选集
通过little和big取交集作为候选集.
过滤阶段
对于阶段1的召回结果, 需要little匹配的position范围在big的匹配范围之内.
对于上面的例子, 即要求通过big匹配了"a"和"c"的同时, little的"b"必须出现在"a"和"c"的中间.
比如:
文档a x x b c可以匹配, 因为b出现在了a和c的中间.
文档a x x c b 则不能匹配, 因为b没有出现在a和c的中间.
匹配位置
与SpanContainingQuery相反, SpanWithinQuery匹配的位置是little的位置. 详细解释可参考SpanContainingQuery中的解释.
SpanFieldMaskingQuery
ES语法示例
{
"query": {
"span_near": {
"clauses": [
{
"span_term": {
"text": "quick brown"
}
},
{
"span_field_masking": {
"query": {
"span_term": {
"text.stems": "fox"
}
},
"field": "text"
}
}
],
"slop": 5,
"in_order": false
}
}
}为了支持在SpanNearQuery/SpanOrQuery中使用多个搜索域的query.
可以把一个正常的SpanQuery用SpanFieldMaskingQuery包裹起来并指定一个自定义字段field_x, 这样被包裹的SpanQuery就可以和其他字段为field_x的SpanQuery混合使用了.
SpanFirstQuery
ES语法示例
{
"query": {
"span_first": {
"match": {
"span_term": { "user.id": "kimchy" }
},
"end": 3
}
}
}包裹一个SpanQuery, 要求匹配位置必须在文档的开头. 具体来说, 要求匹配位置的endPosition<=参数指定的end.
SpanMultiTermQuery
ES语法示例
{
"query": {
"span_multi": {
"match": {
"prefix": { "user.id": { "value": "ki" } }
}
}
}
}把一个MultiTermQuery包裹成SpanQuery, 使其可以作为SpanQuery嵌套使用.
Spans类详解
本身实现了DocIdSetIterator, 用来表示文档的倒排链表, 添加了nextStartPosition()用来遍历某个文档的所有position.
int nextStartPosition()
void collect(SpanCollector collector) // 目前主要用来操作payload.ConjunctionSpans
定义了多个span取交集的操作, 允许子类通过twoPhaseCurrentDocMatches()方法自定义短语的匹配规则.
NearSpansOrdered
有序匹配短语.
核心算法
@Override
boolean twoPhaseCurrentDocMatches() throws IOException {
assert unpositioned();
oneExhaustedInCurrentDoc = false;
while (subSpans[0].nextStartPosition() != NO_MORE_POSITIONS && !oneExhaustedInCurrentDoc) {
if (stretchToOrder() && matchWidth <= allowedSlop) {
return atFirstInCurrentDoc = true;
}
}
return false;
}
@Override
public int nextStartPosition() throws IOException {
if (atFirstInCurrentDoc) {
atFirstInCurrentDoc = false;
return matchStart;
}
oneExhaustedInCurrentDoc = false;
while (subSpans[0].nextStartPosition() != NO_MORE_POSITIONS && !oneExhaustedInCurrentDoc) {
if (stretchToOrder() && matchWidth <= allowedSlop) {
return matchStart;
}
}
return matchStart = matchEnd = NO_MORE_POSITIONS;
}
private boolean stretchToOrder() throws IOException {
Spans prevSpans = subSpans[0];
matchStart = prevSpans.startPosition();
assert prevSpans.startPosition() != NO_MORE_POSITIONS : "prevSpans no start position "+prevSpans;
assert prevSpans.endPosition() != NO_MORE_POSITIONS;
matchWidth = 0;
for (int i = 1; i < subSpans.length; i++) {
Spans spans = subSpans[i];
assert spans.startPosition() != NO_MORE_POSITIONS;
assert spans.endPosition() != NO_MORE_POSITIONS;
if (advancePosition(spans, prevSpans.endPosition()) == NO_MORE_POSITIONS) {
oneExhaustedInCurrentDoc = true;
return false;
}
matchWidth += (spans.startPosition() - prevSpans.endPosition());
prevSpans = spans;
}
matchEnd = subSpans[subSpans.length - 1].endPosition();
return true; // all subSpans ordered and non overlapping
}简单来说, 就是固定头结点, 然后依次检测剩余节点.
matchWidth为需要移动的总距离, 总距离=
(第2个节点位置-第1个节点位置) +
(第3个节点位置-第2个节点位置) +
(第4个节点位置-第3个节点位置) +
...
最后判断总距离matchWidth<=slop即可.
payload check少召回问题
该算法在slop不为0且配合payload check使用的时候会有一个问题:
如果有一个文档为:
china|1 bank|0.5 bank|1我们搜索:
{!payload_check f='TITLE_PAYLOADS' v='china bank' payloads='1 1' operator='phrase' slop=100 inOrder=true}是不能搜到文档的, 因为NearSpansOrdered第一次会给出0,1这组短语的下标, 然后这组短语因为bank的payload=0.5不符合要求, 第二次我们本来预期NearSpansOrdered应该给出0,2这组短语的下标, 然而并不会, 因为NearSpansOrdered每次调用nextStartPosition()的时候是一定会对第一个词调用nextStartPosition()的.
也就是0,1这组下标如果不匹配, 那么china的下标就要往后走. 这在单独的短语查询场景是合理的, 因为一般固定了头结点以后, 如果其他节点取最近的都不能满足slop, 那取更远的就更不可能匹配了, 但是在加入payload check的场景则不然, 近处的可能因为payload check不符合, 但是远处的可能是符合的, 然而NearSpansOrdered并不会给检测机会.
因此, 对指定inOrder=true且slop!=0的场景, 一定要确保文档数据里不能有重复的term, 否则可能会有漏召回的风险.
NearSpansUnordered
无序匹配短语
核心算法
@Override
boolean twoPhaseCurrentDocMatches() throws IOException {
// at doc with all subSpans
spanWindow.startDocument();
while (true) {
if (spanWindow.atMatch()) {
atFirstInCurrentDoc = true;
oneExhaustedInCurrentDoc = false;
return true;
}
if (! spanWindow.nextPosition()) {
return false;
}
}
}
@Override
public int nextStartPosition() throws IOException {
if (atFirstInCurrentDoc) {
atFirstInCurrentDoc = false;
return spanWindow.top().startPosition();
}
assert spanWindow.top().startPosition() != -1;
assert spanWindow.top().startPosition() != NO_MORE_POSITIONS;
while (true) {
if (! spanWindow.nextPosition()) {
oneExhaustedInCurrentDoc = true;
return NO_MORE_POSITIONS;
}
if (spanWindow.atMatch()) {
return spanWindow.top().startPosition();
}
}
}
private class SpanTotalLengthEndPositionWindow extends PriorityQueue<Spans> {
int totalSpanLength;
int maxEndPosition;
public SpanTotalLengthEndPositionWindow() {
super(subSpans.length);
}
@Override
protected final boolean lessThan(Spans spans1, Spans spans2) {
return positionsOrdered(spans1, spans2);
}
void startDocument() throws IOException {
clear();
totalSpanLength = 0;
maxEndPosition = -1;
for (Spans spans : subSpans) {
assert spans.startPosition() == -1;
spans.nextStartPosition();
assert spans.startPosition() != NO_MORE_POSITIONS;
add(spans);
if (spans.endPosition() > maxEndPosition) {
maxEndPosition = spans.endPosition();
}
int spanLength = spans.endPosition() - spans.startPosition();
assert spanLength >= 0;
totalSpanLength += spanLength;
}
}
boolean nextPosition() throws IOException {
Spans topSpans = top();
assert topSpans.startPosition() != NO_MORE_POSITIONS;
int spanLength = topSpans.endPosition() - topSpans.startPosition();
int nextStartPos = topSpans.nextStartPosition();
if (nextStartPos == NO_MORE_POSITIONS) {
return false;
}
totalSpanLength -= spanLength;
spanLength = topSpans.endPosition() - topSpans.startPosition();
totalSpanLength += spanLength;
if (topSpans.endPosition() > maxEndPosition) {
maxEndPosition = topSpans.endPosition();
}
updateTop();
return true;
}
boolean atMatch() {
boolean res = (maxEndPosition - top().startPosition() - totalSpanLength) <= allowedSlop;
return res;
}
}
简单来说, 算法主要思想就是"卡边界"+"找空儿".
这个算法考虑了每个子span的长度, 为了理解思想, 我们先不考虑每个子span的长度, 假设长度都是1, 那么我们可以考虑如下的一个问题:
假设目前索引了以下文档:
"a b c d e f g h i j k"我们用SpanNearQuery来搜这个文档, 参数如下:
- phrase="b c e g h"
- slop=?
- inOrder=false
问在可以匹配文档的情况下, slop最小能够取到多小.
为了回答这个问题, 我们首先画一个图, 把索引文档的term, position, 及我们要查询的phrase的查询term都标记在上面:
索引term | a | b | c | d | e | f | g | h | i | j | k |
|---|---|---|---|---|---|---|---|---|---|---|---|
position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
是否为查询term | x | x | x | x | x |
上面说了, 该算法的主要思想就是"卡边界"+"找空儿":
1. 卡边界
找到查询term最左边的位置和最右边的位置, 卡住这两个边界, 然后求长度:
- 查询term最左边是b, 下标为1.
- 查询term最右边是h, 下标为7.
求从b到h的总长度= 7-1+1=7 (之所以要+1是因为h也要算在内)
2. 找空儿
从b到h, 如果其中的某个term不属于查询term, 则算一个"空儿", 需要找从b到h有几个空儿. 很显然, 有d和f两个"空儿".
我们因为是看图, 可以直观的看出来有2个"空儿", 然而如果要计算出2这个值, 实际上需要用:
从b到h的总长度-查询term数=7-5=2. (查询term数=5是因为有b,c,e,g,h 5个查询term)好了, 最小slop就等于"空儿"的数量=2.
可以看出这个算法的核心思想非常简单直观, 我们最后的"空儿"的计算公式其实就对应了代码里的atMatch()方法:
boolean atMatch() {
boolean res = (maxEndPosition - top().startPosition() - totalSpanLength) <= allowedSlop;
return res;
}
maxEndPosition-top().startPosition()就是卡边界计算总长度.
totalSpanLength就是查询term数. 不过我们的查询term因为长度都是1, 所以计算个数就行了, 对于长度不是1的情况, 实际上要计算总长度, 也就是totalSpanLength."卡边界"+"找空儿"的算法只是针对查询词的一组position的, 然后每个查询词可能有多个position, 因此需要维护一个堆, 每次匹配完一组position, 让堆顶(当前position最小)的查询词advance到下一个位置. 然后对新的一组position继续用"卡边界"+"找空儿"的算法.
payload check少召回问题
在slop不为0且配合payload check使用的时候, inOrder=false的算法也会造成少召回的问题. 原因与inOrder=true的情况类似.
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。