技术领域

本发明涉及计算机应用技术领域， 尤其是一种可实现多属性复合条件査询 的虛拟表索引机制及方法

背景技术

随着 inieraei上应用的数据规模迅速增长，单一数据� ��表往往无法支撑所有 业务数据， 需要将大数据分成若千物理子表分块存储和管 理， 通过数据中;间件 将这些物理子表整合起来形成一张 "容量无限" 的虚拟表。 而随着网络应用处 理和计算变得越来越复杂， 一次针对虚拟表的数据査询计算可能涉及到对 多个 分布数据源 （块） 的即时访问， 这种大量基于分布数据源上的联合査询， 由于 受数据规模、 査询复杂度、 传输带宽等因素的影响， 访问性能常常是这类应用 的瓶颈； 因此， 针对这类应用模式的査询如何在虛拟层构建索 引机制， 快速定 位子表同时避免不必要的子表査询是解决査询 性能问题的关键之一。

从技术方法层面， 主要有两种思路实现针对多个分布数据源 （块） 查询的 索引机制， 来提高访问的性能

思路一是： 针对子表的存储位置紫引， 方便快速定位数据块子表的物理存 储位置 大规模数据的存储与访问需要对数据分片分块 的存储和管理， 此时建 立每个数据块的索引机制能方便请求快速定位 到目标数据源上。

思路二是： 主键键值分段索引， 一张子表会保存一个数据表里面按照主键 键值的某段连续的数据， 从幵始主键到结束主键， 一 ¾宪整的表格是保存在多 个物理子表中 这种机制对支持基于主键的简单逻辑运算的査 询非常有效， 能 确保将查询只施加到满足相应键值条件的数据 子表上。 但是不能支持多属性査 询谓词条件、 相对复杂的运算逻辑的查询

如 Bigtable这种顾序表（Ordered Table)存储模型采用了层次化的 MetaData 模型建立 tablet表的索引， 既支持存储位置索引， 又支持键值分段索引， 但只能 支持基于主键的区间査询， 不能支持多厲性的复合条件査询， 如关系数据库的

发明内容

本发明解决的技术问题之一在于提出构建支持 分布式复合条件査询的虚拟 表紫引机制， 解决当前的存储位置紫引和键値紫引不能支持 多属性条件、 复杂 运算逻辑査询的问题。 本发明引用的虛拟表概念和技术是基于本发明 的发明人 的另 项专利 ZL200810119858.4 (名称 _; 一种网络系统及其管理方法 ; 本发明 所述虛拟表及其管理和使用方式均引用该专利

本发明解决的技术问题之二在于提出构建支持 分布式复合条件查询的虛拟 表索引方法， 解决当前的存储位置索引和键值索引不能支持 多属性条件、 复杂 运算逻辑査询的问题。

本发明解决上述技术问题之一的技术方案是； 所述的机制由三个关键部件 索引管理器、 条件分析器和预执行引擎构成；

所述的索引管理器， 管理虚拟表属性的索引键值， 支持虚拟表多个属性的 所述的条件分析器， 对施加在虑拟表上的査询条件分解并对谓词分 析； 依 次对有紫引的属性按照 SQL语法分析整个查询条件， 用真值 tme替换屏蔽掉含 其他属性的谓词表达式后， 只留下该厲性的査询谓词条件， 以便判断该厲性索 引是否满足此条件； 此时， 如果某属性的索引键值是区间， 条件分析器进一歩 通过该区间值再计算被真值替换后的査询条件 中关于该属性的谓词的真 /假， 并 用布尔结果（tme/&ise)替换该谓词； 如果该步骤无法计算， 则表示直接返回需 要对该虛拟表执行査询的推断结果；

所述的预执行引擎，通过相应属性的索引键值 判断部分被真值表达式（trae) 和布尔结果替换后的查询条件的真 /假，确定相应属性的索弓「是否满足查询条� �; 如果不满足， 画直接返回不对该虚拟表执行査询的推断结果 ； 否则， 继续判断 其他属性索弓 h —些特殊情况， 默认为满足执行条件； 索引键値为区间値时只

本发明解决上述技术问题之.二的技术方案� �： 在虚拟表上构建针对多个属 性的索弓 I键值； 在执行査询时， 计算施加到该虛拟表的査询条件； 依据键値索 引， 预先针对各个属性独立判断是否需要执行该虚 拟表映射的物理实体表， 从 而确保将査询只施加到满足相应键值条件的子 虑拟表上执行。

所述的预先确定哪些子表含有满足该査询条件 的数据记录是； 在處拟层， 通过在各个子表上基于子表的紫引， 预先判断该子表的数据集合是否满足査询 条件， 只定位到满足条件的子表迸行査询； 而对于无査询过滤条件、 未建立紫 按照某个属性键值建立类似 B+树的子表索引结构， B+树的每个叶子节点代 表一个子表； 在叶子节点对子表建立 1 个或多个 （其他） 属性的索引， 紫引值 可以是单値和区间值

两次对查询条件的替换是通过对 SQL查询条件分析形成的语法树, 针对每 个索引属性， 进行单独分析判断

对区间内的值通过代入区间值将谓词表达式转 化成比较逻辑计算布尔结 果 o

本发明的虛拟表索引机制不同于数据库表的索 引。 数据库表的索引是为了 快速定位数据记录， 而虛拟表的紫弓 ί是为快速确定带有某个条件的査询是否有 必要施加在该虛拟表上， 要是为査询调度， 提高分布式査询效率《 由于一般 数据分表都具有确定的规则性， 常常将满足一定条件数据存储到一个子表中， 比如铁路每年的货运摘要数据是按照月份分开 存储到 12张子表中， 以方便同比 分析。 因此， 虚拟表的索引是从子表的整体角度来确定索引 的， 而不是针对特 定的一条记录建索弓 i， 因此紫引数量相对很少。

本发明通过在虚拟层建立虛拟表多属性的索引 ， 在查询分解时， 通过索引 对查询条件预判断是否成立， 从而确定是否需要定位和査询物理子表 相对于 "键-值"和顺序表模型的数据库系统只支持基于 主键的区间查询， 本发明可以 针对多属性建立索引， 支持对多属性的复合条件査询的判断； 支持多属性査询 谓词条件、 相对复杂的运算逻辑的查询， 如支持关系数据库的 SQL标准。

本发明所述的物理子表概念是从元数据角度抽 象定义的， 不涉及对子表数 据存储和管理的物理系统， 因此也可以不加区别的称为一种虚拟表。

附图说明

下面结合附图对本发明迸一歩说明：

图 1是本发明系统结构图；

图 3是本发明的核心算法图

具体实施方式

本发明是在虚拟表上， 可以构建针对多个属性的紫引键值。 在执行査询时， 计算施加到该處拟表的査询条件； 依据键值索引， 预先针对各个厲性独立判断 是否需要执行 （该虚拟表映射的物理实体表）， 从而确保将查询只施加到满足相 应键值条件的子虛拟表上执行。 相对现有的技术， 本发明支持多属性查询谓词 条件、 相对复杂的运算逻辑的査询， 如支持关系数据库的 SQL标准

为实现上述目的， 本发明一种支持分布式査询的虚拟表索 的机制及方法， 由三个关键部件构成： 索引管理器、 条件分析器、 预执行弓 i擎。

索引管理器： 管理虚拟表属性的索引键值， 支持虚拟表多个属性的单个键

条件分析器： 对施加在處拟表上的査询条件分解并对谓词分 析。 依次对有 索引的属性， 按照 SQL语法分析整个査询条件， 用真值 toe替换屏蔽掉含其他 厲性的谓词表达式后， 只留下该属性的査询谓词条件， 以便判断该厲性索引是 否满足此条件。 此时， 如果某属性的索引键値是区间， 条件分析器还需要通过 该区间值， 再计算被真值替换后的査询条件中关于该属性 的谓词的真 /假， 并用 布尔结果（ ru _e /f¾s _e ) 替换该谓词， 如果该步骤无法计算， 则表示直接返回露要 对该虛拟表执行査询的推断结果。

预执行引擎； 通过相应厲性的索引键值 (区间值只取幵始和结柬值即可） 判断部分被真値表达式（irae )和布尔结果替换后的査询条件的真 /假， 确定相应 属性的紫引是否满足查询条件。 如果不满足， 则直接返回不对该虚拟表执行査 询的推断结果； 否则， 继续判断其他属性紫引。 一些特殊情况， 为筒化判断， 预执行引擎默认为满足执行条件， 比如含多元谓词表达式。

如图 1 所示， 由于数据规模大导致分的数据子表较多， 一次应用的査询请 求， 不能全部施加到各个子表执行， 需要预先确定哪些子表含有满足该查询条 件的数据记录 （区间结果或者单条记录）。 在虚拟层， 通过在各个子表上 ( Ί^. , ,)基于子表的索引， 预先判断该子表的数据集合是否满足査询条件 ， 只定位到满足条件的子表进行査询 （了,,... ）。 而对于一些特例 （包括无査询过 如图 2所示， 为快速定位子表， ^以按照某个属性键値建立类似 Β+树的子 表索引结构， Β+树的每个叶子节点代表 -个子表 在叶子节点对子表建立 1个 或多个 （其他） 属性的索引， 索引值可以是单值和区间 1 厲性索引值是从子 表的整体角度定义的值区间， 索引值 间范围越小 （少）， 越容易判断。 所¾在 虛拟层适合建立索引的列是基数高、 选择度低的列， 而在数据库眉的索引为便 于定俊某条具体记录正好相反 （基数定义； 行数 /唯一值数； 选择度定义； ：1 /唯 一值数）。 考虑到不同应用场景中， 索引值会随着数据增力 /修改 /删除、 子表的 拆分 /合并等情况而变化， 这种变化的频度和复杂度在各种场景中不一致 ， 本发 明不强调紫引值的一致性同歩方法 可以通过人工建立索引、 也可以在数据操 由于在 GAV (Global As View ) /LAV (Local As View)这类传统的数据集成 应用中， 虛拟视图的 schema与物理数据源的 schema不尽相同， 是通过映射机 制来确定。 因此， 针对每个子表都需要对査询条件进行重新分析 ， 以将应翔的 查询映射到子表的查询。 而对于一般的"键-值"、顺序表数据模型， 由于各子表 的厲性是一致的， 不需要针对每个子表分别做条件分析 因此本发明的方法可 以同时应用到 "键 1"、 顺序表、 传统关系数据库集成领域。

图 3 表示了本发明的核心算法； 核心算法中两次对査询条件的替换 ( Step2 Step3 ) 是关键歩骤 通过对 SQL査询条件分析形成的语法树， 算法针 对每个索引属性， 进行单独分析判断 假设铁路货运明细表中， 数据分表是按 照月份（Mcrath)和线路（Line)编号来分若千子表 管理的（其紫引如下表所述。 当子表太多时， 也可以按照国 2以 Une值建立索引树）。

隱 ith >20 I2 ! 008 and month < 2012.1014 and line = 0005,

对 T,表， 首先判断 Mont 索引。 执行 Step2结果是： month > -20121008 and month < 20121014 and ime。 执行 Step3时， 对于 month >- 20121008谓词， 首先 替换 index 中的通配符号 index 成 2100卜 2012腦, 通过转化谓词成计算 2012100! <: 20121008 and 2012 j 008 <= 2012】03 的成果为 true。同样处理 m mil < 20121014環词后条件为： true and true and true, Step4计算 trap^resuli结果为 true, 从而

继续判断 TV表的 Line索引， 此时执行 Step2后条件为： true and true and !i e-0005 , 直接跳过 Step3执行 Step4通过 0005値判断该条件是否成立 预执 行引擎是通过向内存数据库引擎发送 -个査询 "sekct line from (select 0005 as line) IT where ime and true and line-0005 "获得非空结果集从而判断条件成立， 这样确保含有 Lme属性的任意 SQL标准的复杂査询条件都能判断出结果 其实 对于多个单值索引， 可以将他们合并在一起， 只执行一次 Step4即可判断是否有 键值满足条件 最终判断结果是需要执行 表。

而对 表， 在 Month索引判断 Step3后条件成 fidse and false and true, 计算 tmp resu it结果 false，■ 从而 result e， 不 1 !f T; :表.

这里的难点在 Stq>3, 由于不可能对区间内的值迸行穷举的办法来判 断谓词 的真假 （实际数据库中是通过代入具体记录列的值判 断真假）， 只能通过代入区 间值将谓词表达忒转化成比较逻辑计算布尔结 果， 相当于解一元方程式， 考虑 到复杂性目前只实现了相对简单的一阶谓词公 司的求解， 其他的均. 作无法替 换处理。