Lucene 的范围查询详解

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

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

    范围查询部分很赞

推荐标签 标签

  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 728 关注
  • JVM

    JVM(Java Virtual Machine)Java 虚拟机是一个微型操作系统,有自己的硬件构架体系,还有相应的指令系统。能够识别 Java 独特的 .class 文件(字节码),能够将这些文件中的信息读取出来,使得 Java 程序只需要生成 Java 虚拟机上的字节码后就能在不同操作系统平台上进行运行。

    180 引用 • 120 回帖 • 3 关注
  • HTML

    HTML5 是 HTML 下一个的主要修订版本,现在仍处于发展阶段。广义论及 HTML5 时,实际指的是包括 HTML、CSS 和 JavaScript 在内的一套技术组合。

    108 引用 • 295 回帖 • 2 关注
  • 浅吟主题

    Jeffrey Chen 制作的思源笔记主题,项目仓库:https://github.com/TCOTC/Whisper

    1 引用 • 28 回帖 • 1 关注
  • App

    App(应用程序,Application 的缩写)一般指手机软件。

    91 引用 • 384 回帖
  • Sandbox

    如果帖子标签含有 Sandbox ,则该帖子会被视为“测试帖”,主要用于测试社区功能,排查 bug 等,该标签下内容不定期进行清理。

    438 引用 • 1238 回帖 • 588 关注
  • 一些有用的避坑指南。

    69 引用 • 93 回帖
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    554 引用 • 675 回帖
  • Anytype
    3 引用 • 31 回帖 • 27 关注
  • HHKB

    HHKB 是富士通的 Happy Hacking 系列电容键盘。电容键盘即无接点静电电容式键盘(Capacitive Keyboard)。

    5 引用 • 74 回帖 • 521 关注
  • VirtualBox

    VirtualBox 是一款开源虚拟机软件,最早由德国 Innotek 公司开发,由 Sun Microsystems 公司出品的软件,使用 Qt 编写,在 Sun 被 Oracle 收购后正式更名成 Oracle VM VirtualBox。

    10 引用 • 2 回帖 • 18 关注
  • BND

    BND(Baidu Netdisk Downloader)是一款图形界面的百度网盘不限速下载器,支持 Windows、Linux 和 Mac,详细介绍请看这里

    107 引用 • 1281 回帖 • 36 关注
  • WebSocket

    WebSocket 是 HTML5 中定义的一种新协议,它实现了浏览器与服务器之间的全双工通信(full-duplex)。

    48 引用 • 206 回帖 • 285 关注
  • QQ

    1999 年 2 月腾讯正式推出“腾讯 QQ”,在线用户由 1999 年的 2 人(马化腾和张志东)到现在已经发展到上亿用户了,在线人数超过一亿,是目前使用最广泛的聊天软件之一。

    45 引用 • 557 回帖
  • frp

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

    17 引用 • 7 回帖
  • 域名

    域名(Domain Name),简称域名、网域,是由一串用点分隔的名字组成的 Internet 上某一台计算机或计算机组的名称,用于在数据传输时标识计算机的电子方位(有时也指地理位置)。

    44 引用 • 208 回帖
  • GraphQL

    GraphQL 是一个用于 API 的查询语言,是一个使用基于类型系统来执行查询的服务端运行时(类型系统由你的数据定义)。GraphQL 并没有和任何特定数据库或者存储引擎绑定,而是依靠你现有的代码和数据支撑。

    4 引用 • 3 回帖 • 12 关注
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • JavaScript

    JavaScript 一种动态类型、弱类型、基于原型的直译式脚本语言,内置支持类型。它的解释器被称为 JavaScript 引擎,为浏览器的一部分,广泛用于客户端的脚本语言,最早是在 HTML 网页上使用,用来给 HTML 网页增加动态功能。

    730 引用 • 1282 回帖
  • Visio
    1 引用 • 2 回帖 • 2 关注
  • 安全

    安全永远都不是一个小问题。

    199 引用 • 818 回帖 • 1 关注
  • 酷鸟浏览器

    安全 · 稳定 · 快速
    为跨境从业人员提供专业的跨境浏览器

    3 引用 • 59 回帖 • 49 关注
  • 职场

    找到自己的位置,萌新烦恼少。

    127 引用 • 1708 回帖 • 2 关注
  • 强迫症

    强迫症(OCD)属于焦虑障碍的一种类型,是一组以强迫思维和强迫行为为主要临床表现的神经精神疾病,其特点为有意识的强迫和反强迫并存,一些毫无意义、甚至违背自己意愿的想法或冲动反反复复侵入患者的日常生活。

    15 引用 • 161 回帖 • 1 关注
  • 招聘

    哪里都缺人,哪里都不缺人。

    188 引用 • 1057 回帖
  • Linux

    Linux 是一套免费使用和自由传播的类 Unix 操作系统,是一个基于 POSIX 和 Unix 的多用户、多任务、支持多线程和多 CPU 的操作系统。它能运行主要的 Unix 工具软件、应用程序和网络协议,并支持 32 位和 64 位硬件。Linux 继承了 Unix 以网络为核心的设计思想,是一个性能稳定的多用户网络操作系统。

    954 引用 • 944 回帖
  • 爬虫

    网络爬虫(Spider、Crawler),是一种按照一定的规则,自动地抓取万维网信息的程序。

    106 引用 • 275 回帖