Lucene 的范围查询详解

本贴最后更新于 2994 天前,其中的信息可能已经沧海桑田

Lucene 的范围查询是怎样实现的呢

粗略来说,是两种方式:

  1. 根据 docId 获取 field 的值,和设定的范围进行比较过滤,得到满足范围条件的 docList。

  2. 根据范围条件从 term 列表过滤出满足条件的 term,把 term 组成 BooleanQuery,查询倒排列表,得到满足范围条件的 docList。

第一种方式,从 docId 获取 value,需要用到 fieldCache,比较占内存,如果候选的 doc 数量非常大(满足其他查询条件的 doc 非常多或没有其他查询条件),则要过滤的计算比较多,性能不会很好。

第二种方式,如果过滤的范围比较大,则过滤出来的 term 非常多,要查的 term 很多,性能会很差。

从源代码看,Lucene 的实现是这两种方式的组合,但第二种方式经过了优化,过滤出来的 term 的数量会非常少,性能非常好。

如果 field 没有索引,且有 docValues,则采取第一种方式(没有索引,是无法用第二种方式的,因为没有对应的 term)

如果 field 有索引,则采取第二种方式,TrieField 的范围过滤

TrieField 实现原理

数值类型 TrieXXXField(XXX 可为 Long、Int、Float、Double、Date 等),如果需要范围查询,一般要设置一个参数 precisionStep。这个参数的用途是,在索引阶段,会把一个数值,根据 precisionStep 进行精度截取,分为多个不同精度的 term 来存储。我们以一个 int 为例,一个 int 共 32 位,如果 precisionStep 为 8,则每根据不同的精度,可以得到 4 个 term

term&11111111111111111111111111111111

term&11111111111111111111111100000000

term&11111111111111110000000000000000

term&11111111000000000000000000000000

这样,每个 term 都会变为 4 个 term,存储会增加很多,低精度的 term 重复率比较高,因此,主要是倒排列表占用的空间会多很多。

查询时,范围的上界和下界也按照这种规则,划分为 4 段,间隔的两个段之间有 256 个 term,

这样范围内的 term,就先取高低精度的,再取高精度的。最多一共有

256+2562+2562+256*2=1280 个 term,这些 term 再用 ConstantScoreQuery 来查询,比较打分计算。

下面举个例子来说明一个范围内的 term 是怎样得到的。

比如,范围[232420561,1399563675],

232420561 的二进制是 00001101110110100111010011010001

1399563675 的二进制是 01010011011010111010010110011011

命中的 term 为

下界高精度

00001101110110100111010011010001

00001101110110100111010011111111

共 48 个 term

下界去掉 8 位精度

00001101110110100111010100000000

00001101110110101111111100000000

共 139 个 term

下界去掉 16 位精度

00001101110110110000000000000000

00001101111111110000000000000000

共 37 个 term

去掉 24 位精度

00001110000000000000000000000000

01010010000000000000000000000000

共 69 个 term

上界去掉 16 位精度

01010011000000000000000000000000

01010011011010100000000000000000

共 107 个 term

上界去掉 8 位精度

01010011011010110000000000000000

01010011011010111010010000000000

共 165 个 term

上界最高精度

01010011011010111010010100000000

01010011011010111010010110011011

共 156 个 term

总共要查询 721 个 term,使用 ConstantScoreQuery 来查询还是很快的。

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • someone

    范围查询部分很赞

推荐标签 标签

  • C

    C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。

    86 引用 • 165 回帖
  • frp

    frp 是一个可用于内网穿透的高性能的反向代理应用,支持 TCP、UDP、 HTTP 和 HTTPS 协议。

    17 引用 • 7 回帖 • 3 关注
  • 一些有用的避坑指南。

    69 引用 • 93 回帖 • 1 关注
  • 又拍云

    又拍云是国内领先的 CDN 服务提供商,国家工信部认证通过的“可信云”,乌云众测平台认证的“安全云”,为移动时代的创业者提供新一代的 CDN 加速服务。

    20 引用 • 37 回帖 • 573 关注
  • 反馈

    Communication channel for makers and users.

    120 引用 • 906 回帖 • 280 关注
  • Logseq

    Logseq 是一个隐私优先、开源的知识库工具。

    Logseq is a joyful, open-source outliner that works on top of local plain-text Markdown and Org-mode files. Use it to write, organize and share your thoughts, keep your to-do list, and build your own digital garden.

    7 引用 • 69 回帖 • 5 关注
  • 架构

    我们平时所说的“架构”主要是指软件架构,这是有关软件整体结构与组件的抽象描述,用于指导软件系统各个方面的设计。另外还有“业务架构”、“网络架构”、“硬件架构”等细分领域。

    142 引用 • 442 回帖 • 1 关注
  • Pipe

    Pipe 是一款小而美的开源博客平台。Pipe 有着非常活跃的社区,可将文章作为帖子推送到社区,来自社区的回帖将作为博客评论进行联动(具体细节请浏览 B3log 构思 - 分布式社区网络)。

    这是一种全新的网络社区体验,让热爱记录和分享的你不再感到孤单!

    134 引用 • 1127 回帖 • 109 关注
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 562 关注
  • Sublime

    Sublime Text 是一款可以用来写代码、写文章的文本编辑器。支持代码高亮、自动完成,还支持通过插件进行扩展。

    10 引用 • 5 回帖
  • 代码片段

    代码片段分为 CSS 与 JS 两种代码,添加在 [设置 - 外观 - 代码片段] 中,这些代码会在思源笔记加载时自动执行,用于改善笔记的样式或功能。

    用户在该标签下分享代码片段时需在帖子标题前添加 [css] [js] 用于区分代码片段类型。

    203 引用 • 1472 回帖
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务,可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 109 关注
  • 游戏

    沉迷游戏伤身,强撸灰飞烟灭。

    187 引用 • 832 回帖
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    59 引用 • 25 回帖 • 3 关注
  • Hexo

    Hexo 是一款快速、简洁且高效的博客框架,使用 Node.js 编写。

    22 引用 • 148 回帖 • 9 关注
  • CSS

    CSS(Cascading Style Sheet)“层叠样式表”是用于控制网页样式并允许将样式信息与网页内容分离的一种标记性语言。

    198 引用 • 543 回帖 • 1 关注
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 2 关注
  • GitBook

    GitBook 使您的团队可以轻松编写和维护高质量的文档。 分享知识,提高团队的工作效率,让用户满意。

    3 引用 • 8 回帖 • 1 关注
  • 分享

    有什么新发现就分享给大家吧!

    248 引用 • 1794 回帖
  • IBM

    IBM(国际商业机器公司)或万国商业机器公司,简称 IBM(International Business Machines Corporation),总公司在纽约州阿蒙克市。1911 年托马斯·沃森创立于美国,是全球最大的信息技术和业务解决方案公司,拥有全球雇员 30 多万人,业务遍及 160 多个国家和地区。

    17 引用 • 53 回帖 • 143 关注
  • Electron

    Electron 基于 Chromium 和 Node.js,让你可以使用 HTML、CSS 和 JavaScript 构建应用。它是一个由 GitHub 及众多贡献者组成的活跃社区共同维护的开源项目,兼容 Mac、Windows 和 Linux,它构建的应用可在这三个操作系统上面运行。

    15 引用 • 136 回帖
  • Quicker

    Quicker 您的指尖工具箱!操作更少,收获更多!

    37 引用 • 157 回帖 • 1 关注
  • iOS

    iOS 是由苹果公司开发的移动操作系统,最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统,最初是设计给 iPhone 使用的,后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样,属于类 Unix 的商业操作系统。

    89 引用 • 150 回帖 • 4 关注
  • 生活

    生活是指人类生存过程中的各项活动的总和,范畴较广,一般指为幸福的意义而存在。生活实际上是对人生的一种诠释。生活包括人类在社会中与自己息息相关的日常活动和心理影射。

    230 引用 • 1432 回帖
  • 人工智能

    人工智能(Artificial Intelligence)是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门技术科学。

    115 引用 • 319 回帖
  • 知乎

    知乎是网络问答社区,连接各行各业的用户。用户分享着彼此的知识、经验和见解,为中文互联网源源不断地提供多种多样的信息。

    10 引用 • 66 回帖
  • 以太坊

    以太坊(Ethereum)并不是一个机构,而是一款能够在区块链上实现智能合约、开源的底层系统。以太坊是一个平台和一种编程语言 Solidity,使开发人员能够建立和发布下一代去中心化应用。 以太坊可以用来编程、分散、担保和交易任何事物:投票、域名、金融交易所、众筹、公司管理、合同和知识产权等等。

    34 引用 • 367 回帖 • 1 关注