(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210533848.5 (22)申请日 2022.05.16 (71)申请人 北京奥星贝斯科技有限公司 地址 100020 北京市朝阳区东 三环中路1号 1幢1单元9层901内02号单 元 (72)发明人 杨海涛　 (74)专利代理 机构 北京博思佳知识产权代理有 限公司 1 1415 专利代理师 李威 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/2455(2019.01) (54)发明名称 LSM-Tree架构数据库有序表的查询方法和 装置 (57)摘要 本说明书提供一种LSM ‑Tree架构数据库有 序表的查询方法， 所述查询包括根据查询条件依 次扫描一张到多张有序表， 对某 一张有序表的扫 描包括： 将所述某一张有序表作为当前有序表； 在当前迭代器匹配于当前有序表的类型时， 保留 当前迭代器； 否则获取与当前有序表匹配类型的 迭代器作为 当前迭代器； 由当前迭代器确定本次 扫描的目标数据块； 当本次扫描的目标数据块与 当前缓存数据块是同一个数据块时， 保留当前缓 存数据块； 否则读取本次扫描的目标数据块到缓 存中生成新的当前缓存数据块； 由当前迭代器根 据查询条件扫描当前缓存数据块。 权利要求书2页 说明书8页 附图3页 CN 114969034 A 2022.08.30 CN 114969034 A 1.一种LSM ‑Tree架构数据库有序表的查询方法， 所述查询包括根据查询条件依次扫描 一张到多张有序表， 对某一张有序表的扫描包括： 将所述某一张有序表作为当前有序表； 在当前迭代器匹配于当前有序表的类型时， 保留当前迭代器； 否则获取与当前有序表 匹配类型的迭代器作为当前迭代器； 由当前迭代器确定 本次扫描的目标 数据块； 当本次扫描的目标数据块与当前缓存数据块是同一个数据块时， 保留当前缓存数据 块； 否则读取本次扫描的目标 数据块到缓存中生成新的当前缓存数据块； 由当前迭代器根据查询条件扫描当前缓存数据块。 2.根据权利要求1所述的方法， 所述获取与当前有序表类型匹配的迭代器作为当前迭 代器， 包括： 将当前迭代器返回至迭代器池中， 从迭代器池中申请与当前有序 表类型匹配的 迭代器作为 新的当前迭代器。 3.根据权利要求2所述的方法， 所述方法还包括： 在 当前迭代器不匹配于当前有序表的 类型、 并且迭代器池中不存在与当前有序表类型匹配的迭代器时， 生成与当前有序表类型 匹配的迭代器作为当前迭代器， 读取本次扫描的目标数据块到缓存中生成当前缓存数据 块， 由当前迭代器采用查询条件扫描当前缓存数据块。 4.根据权利要求1所述的方法， 所述目标 数据块为微块， 属于某一个宏块； 所述由当前迭代器确定本次扫描的目标数据块， 包括： 由当前迭代器确定本次扫描的 目标宏块及其内部的目标微 块； 所述当本次扫描的目标数据块与当前缓存数据块是同一个数据块 时， 保留当前缓存数 据块； 否则读取本次扫描的目标数据块到缓存中生成新的当前缓存数据块， 包括： 当本次扫 描的目标微块与上一次扫描的目标微块是同一个微块时， 保留当前缓存数据块； 当本次扫 描的目标微块与上一次扫描的目标微块不是同一个微块并且均属于同一个宏块时， 基于当 前宏块定位本次扫描的目标微块， 读取本次扫描的目标微块到缓存中生成新的当前缓存数 据块； 当本次扫描的目标微块与上一次扫描的目标微块不是同一个微块并且不属于同一个 宏块时， 按照本次扫描的目标微块所属的宏块更新当前宏块， 基于更新后的当前宏块定位 本次扫描的目标微 块， 读取目标微 块到缓存中生成新的当前缓存数据块。 5.根据权利要求1所述的方法， 所述当前迭代器包括 解码器； 所述由当前迭代器根据查询条件扫描当前缓存数据块， 包括： 当本次扫描的目标数据 块与上一次扫描的目标数据块是同一个数据块时， 由解码器根据查询条件对当前缓存数据 块进行解码和扫描； 当本次扫描的目标数据块与上一次扫描的目标数据块不是同一个数据 块时， 根据本次扫描的目标数据块初始化解码器， 由完成初始化后的解码器对当前缓存数 据块进行解码和扫描。 6.根据权利要求1所述的方法， 所述查询包括： 嵌套连接Nestloop  Join、 二级索引回 表、 或跨分区查询。 7.一种LSM ‑Tree架构数据库有序表的查询装置， 所述查询包括根据查询条件依次扫描 一张到多张有序表， 所述装置中用于对某一张有序表进行扫描的部分包括： 当前有序表单 元， 用于将所述某一张有序表作为当前有序表； 当前迭代器单元， 用于在当前迭代器匹配于当前有序表的类型时， 保留当前迭代器； 否权　利　要　求　书 1/2 页 2 CN 114969034 A 2则获取与当前有序表匹配 类型的迭代器作为当前迭代器； 目标数据块单 元， 用于由当前迭代器确定 本次扫描的目标 数据块； 当前缓存数据块单元， 用于当本次扫描的目标数据块与当前缓存数据块是同一个数据 块时， 保留当前缓存数据块； 否则读取本次扫描的目标数据块到缓存中生成新的当前缓存 数据块； 扫描执行单元， 用于由当前迭代器根据查询条件扫描当前缓存数据块。 8.根据权利要求7所述的装置， 所述当前迭代器单元获取与当前有序表类型匹配的迭 代器作为当前迭代器， 包括： 将当前迭代器返回至迭代器池中， 从迭代器池中申请与当前有 序表类型匹配的迭代器作为 新的当前迭代器。 9.根据权利要求8所述的装置， 所述装置还包括： 迭代器新增单元， 用于在当前迭代器 不匹配于当前有序表的类型、 并且迭代器池中不存在与当前有序表类型匹配的迭代器时， 生成与当前有序 表类型匹配的迭代器作为当前迭代器， 读取本次扫描的目标数据块到缓存 中生成当前缓存数据块， 由当前迭代器采用查询条件扫描当前缓存数据块。 10.根据权利要求7 所述的装置， 所述目标 数据块为微块， 属于某一个宏块； 所述目标数据块单元具体用于： 由当前迭代器确定本次扫描的目标宏块及其内部的目 标微块； 所述当前缓存数据块单元具体用于： 当本次扫描的目标微块与 上一次扫描的目标微块 是同一个微块时， 保留当前缓存数据块； 当本次扫描的目标微块与上一次扫描的目标微块 不是同一个微块并且均属于同一个宏块时， 基于当前宏块定位本次扫描的目标微块， 读取 本次扫描的目标微块到缓存中生成新的当前缓存数据块； 当本次扫描的目标微块与上一次 扫描的目标微块不是同一个微块并且不属于同一个宏块时， 按照本次扫描的目标微块所属 的宏块更新当前宏块， 基于更新后的当前宏块定位本次扫描的目标微块， 读取目标微块到 缓存中生成新的当前缓存数据块。 11.根据权利要求7 所述的装置， 所述当前迭代器包括 解码器； 所述扫描执行单元具体用于： 当本次扫描的目标数据块与上一 次扫描的目标数据块是 同一个数据块时， 由解码器根据查询条件对当前缓存数据块进行解码和扫描； 当本次扫描 的目标数据块与上一次扫描的目标数据块不是同一个数据块时， 根据本次扫描的目标数据 块初始化 解码器， 由完成初始化后的解码器对当前缓存数据块进行解码和扫描。 12.根据权利要求7所述的装置， 所述查询包括： 嵌套连接Nestloop  Join、 二级索引回 表、 或跨分区查询。 13.一种计算机设备， 包括： 存储器和 处理器； 所述存储器上存储有可由处理器运行的 计算机程序； 所述处理器运行所述计算机程序时， 执行如权利要求1到6任意一项所述的方 法。 14.一种计算机可读存储介质， 其上存储有计算机程序， 所述计算机程序被处理器运行 时， 执行如权利要求1到 6任意一项所述的方法。权　利　要　求　书 2/2 页 3 CN 114969034 A 3