Lucene 如何实现高性能 GroupBy <一>

我就是我 2022-02-26 16:18 212阅读 0赞

转载：[http://www.cnblogs.com/zengen/archive/2010/11/24/1886244.html][http_www.cnblogs.com_zengen_archive_2010_11_24_1886244.html]

注：以下讲解代码均以Lucene.net 2.9.2为例。GroupBy效果应用（[http://www.tradetuber.com/search?key=led][http_www.tradetuber.com_search_key_led]）

Lucene如果实现高性能的GroupBy、SortBy效果，我想这个应该是Lucener（Lucene使用者简称Lucener）遇到的最头大的问题。

Lucene各个方面表现都很优异，唯独在GroupBy及SortBy方面显得蹩脚，那么接下来的文章中我将为Lucener讲解如何更好的解决这两大问题。

1.GroupBy

要实现GroupBy，我们应该从哪下手？ 如何下手？

从哪下手：从Collector类下手，Collector类相当于一个收集器，它收集的结果集是一个 ScoreDoc集合，ScoreDoc是DocID（文档ID）与Score（该文档得分）的一个对应关系，然后Lucene会使用移位运算等算法比较所有DocID的得分，并得到前多少条（pageSize\*pageIndex）记录。

如何下手：当然是在逐个比较DocID的得分时注入相应的代码。

public override void Collect(int doc)
                {
                    float score = scorer.Score();
    
                    // This collector cannot handle these scores:
                    System.Diagnostics.Debug.Assert(score != float.NegativeInfinity);
                    System.Diagnostics.Debug.Assert(!float.IsNaN(score));
    
                    totalHits++;
                    if (score <= pqTop.score)
                    {
                        // Since docs are returned in-order (i.e., increasing doc Id), a document
                        // with equal score to pqTop.score cannot compete since HitQueue favors
                        // documents with lower doc Ids. Therefore reject those docs too.
                        return;
                    }
                    pqTop.doc = doc + docBase;
                    pqTop.score = score;
                    pqTop = (ScoreDoc)pq.UpdateTop();
                }

上面的方法是Lucene中用来逐个比较DocID得分的方法，我们在此段中加入我们的方法来实现GroupBy。

public override void Collect(int doc)
                {
                    float score = scorer.Score();
    
                    //根据DocID获取Document
                    Document doc  = _IndexReader.Document(doc);
                    //取出分组字段值
                    string strGroupByFieldValue = doc.Get("GroupByFieldName");
                    //判断分组字段值是否已经存在，存在则返回，不存在继续，这样便保证了被分组字段对应的值有且仅出现一次。
                    if(_Dictionary.ContainsKey(strGroupByFieldValue ))
                        return;
    
                    // This collector cannot handle these scores:
                    System.Diagnostics.Debug.Assert(score != float.NegativeInfinity);
                    System.Diagnostics.Debug.Assert(!float.IsNaN(score));
    
                    totalHits++;
                    if (score <= pqTop.score)
                    {
                        // Since docs are returned in-order (i.e., increasing doc Id), a document
                        // with equal score to pqTop.score cannot compete since HitQueue favors
                        // documents with lower doc Ids. Therefore reject those docs too.
                        return;
                    }
                    pqTop.doc = doc + docBase;
                    pqTop.score = score;
                    pqTop = (ScoreDoc)pq.UpdateTop();
                }

通过上面的代码，我们可以保证被GroupBy的字段值一旦曾经出现过，便不再往下走了，同时我们可以此处过滤时保存被过滤的次数，这样GroupBy的初级效果便出现在了我们眼前了，但是，上面的方法存在的最大问题便是性能问题。

e.g. string strGroupByFieldValue = doc.Get("strGroupByFieldName");

这句代码是获取分组字段的值，这种取值方式是直接从磁盘中读取的，当搜索时被标中的记录越多，磁盘的IO操作也就越多，自然而然就成为了性能的瓶颈之所在。

那么如何可以快速的进行读取呢？ 当然是从内存中读取分组字段的值。

那么如何来读取并将其存放在内存中呢？ It's Term，Term即Lucene中的词。

创建索引时，我们会对某些字段进行分词索引或不分词索引，然后这些词会生成一个字典，然后会对字典中的词按字母顺序排列，再然后会合并相同的词生成文档倒排链表（Posting List）。

这个倒排链表实际上就是词与文档ID的对应关系，这个里面还包含了词频（词在文档中出现的频率）等重要的属性。正是因为有了这个由Term以及其它要素组成的Posting List，所以才可以进行快速搜索。

这个过程类似于咱们很小的时候查新华字典一样，那么厚一本字典中想要找到自己想要的字，最快速的办法就是根据这个字的拼音或部首去找，然后定位到这个字所在的页数，这样我们就找到了我们想要的字。新华字典的拼音检字表或部首检字表就相当于是Posting List。

由此可知，我们需要从这个倒排链表中将分组字段的值全部读出来，存放在内存中，供Collect方法中使用。

注意：需要分组的字段不能被分词索引

Term startTerm = new Term("GroupByFieldName");
                    TermEnum te = _IndexReader.Terms(startTerm);
                    if (te != null)
                    {
                        Term currTerm = te.Term();
    
                        while ((currTerm != null) && (currTerm.Field() == startTerm.Field())) 
                        //term fieldnames are interned
                        {
                            TermDocs td = _IndexReader.TermDocs(currTerm);
                            while (td.Next())
                            {
                                dict.Add(td.Doc(), currTerm.Text());
                            }
                            if (!te.Next())
                            {
                                break;
                            }
                            currTerm = te.Term();
                        }
                    }

通过上面的代码，我们便得到了我们所需要的分组字段值，它是一个DocID（文档ID）与分组字段值对应关系的Dictionary<int, string>。

现在我们把分组字段值缓存到了一个Dictionary中，这时出现了一个新的问题，索引库的更新一般都是实时更新的，一旦缓存起来了，当有新的记录加入到索引库时，缓存却无法更新。怎么办？ 请看下面的代码：

int oldMaxDoc = MaxDoc;//缓存上次更新时的MaxDoc
                int newMaxDoc = _IndexReader.MaxDoc();
                if (oldMaxDoc < newMaxDoc)
                {
                    Term startTerm = new Term("GroupByFieldName");
                    TermEnum te = _IndexReader.Terms(startTerm);
                    if (te != null)
                    {
                        Term currTerm = te.Term();
                        while ((currTerm != null) && (currTerm.Field() == startTerm.Field())) 
                        //term fieldnames are interned
                        {
                            TermDocs td = _IndexReader.TermDocs(currTerm);
                            if (td.SkipTo(oldMaxDoc))
                            {
                                do
                                {
                                    dict.Add(td.Doc(), currTerm.Text());
                                }
                                while (td.Next());
                            }
                            if (!te.Next())
                            {
                                break;
                            }
                            currTerm = te.Term();
                        }
                    }
                    MaxDoc = newMaxDoc;
                }

通过上面的代码，我们不难明白如何更新分组字段缓存。

Lucene中文档的添加都会伴随有一个DocID的生成，DocID的生成如同关系性数据库的自动增长字段，MaxDoc = Max（DocID），所以我们根据MaxDoc值的变化来判断是否有新的文档产生，如果有则skipTo到OldMaxDoc位置，将新增长的文档ID对应的分组字段值加入到Dictionary中。

注意：从Posting List中读取对应的Term值性能上也是个问题（60万条记录大概需要2S左右），建议使用其它线程来更新该Dictionary的值；或者使用另外的进程来缓存。

这样，我们便可以在Collect方法中根据传入的DocID从Dictionary<int, string>取出对应的分组字段的值进行过滤，这种速度可想而知，代码如下：

public override void Collect(int doc)
                {
                    float score = scorer.Score();
    
                    //判断分组字段值是否已经存在，存在则返回，不存在继续，这样便保证了被分组字段对应的值有且仅出现一次。
                    if(_Dictionary.ContainsKey(dict[doc]))
                        return;
    
                    // This collector cannot handle these scores:
                    System.Diagnostics.Debug.Assert(score != float.NegativeInfinity);
                    System.Diagnostics.Debug.Assert(!float.IsNaN(score));
    
                    totalHits++;
                    if (score <= pqTop.score)
                    {
                        // Since docs are returned in-order (i.e., increasing doc Id), a document
                        // with equal score to pqTop.score cannot compete since HitQueue favors
                        // documents with lower doc Ids. Therefore reject those docs too.
                        return;
                    }
                    pqTop.doc = doc + docBase;
                    pqTop.score = score;
                    pqTop = (ScoreDoc)pq.UpdateTop();
                }

写到这里，新的问题又产生了！

从上面的代码我们不难看出，虽然实现了GroupBy（假设我们按照公司ID来进行分组，每个公司只能出现一个产品），但是无法保证该产品是该公司得分最高的产品，这样也就影响了公司对应的产品排名。

e.g.

A公司（2个产品），得分依次为 0.12、0.33

B公司（2个产品），得分依次为 0.23、0.31

按照理论上，A公司一定排在B公司前面，因为A公司产品最高得分为0.33，B公司产品最高得分0.31分，按照上面的代码，有可能B公司就排在A公司前面了，当得分为0.12的产品先出现，那么A公司对应的最大产品分数就是0.12了，A公司就排在B公司之后了。

针对上述问题，我们仅仅在Collect方法注入代码是无法实现的，我们还需要结合 “结果集得分排序” 来解决上述问题，这时我们需要看看这个类（Lucene--Util--PriorityQueue.cs）。

PriorityQueue这个类是用来干什么的呢？它是用来对搜索结果按照得分高低进行顺序排列，并返回你需要的记录数的 ScoreDoc = ｛Doc, Score｝。那接下来我们就一起研究研究它。

[http_www.cnblogs.com_zengen_archive_2010_11_24_1886244.html]: http://www.cnblogs.com/zengen/archive/2010/11/24/1886244.html
[http_www.tradetuber.com_search_key_led]: http://www.tradetuber.com/search?key=led