高性能分层文本搜索

Question

我现在正处于升级主要交易系统中层次结构设计的最后阶段,我一直在这150行查询中盯着看(我将免除你阅读的所有单调)并认为那里必须是一个更好的方式.

该问题的快速摘要如下:

您将如何实现与层次结构中不同级别的多个搜索项匹配的分层搜索,并针对最快的搜索时间进行优化？

我发现了一个有点相关的问题,但它实际上只有我实际需要的答案的20%左右.这是完整的场景/规范:

• 最终目标是在层次结构中的任意位置找到一个或多个任意项.
• 完整的层次结构大约有80,000个节点,预计在几年内会增长到1M.
• 层次结构中整个路径的全文是唯一且具有描述性的; 但是,单个节点的文本可能不是.这是一个商业现实,而不是一个轻率的决定.
• 示例:一个节点可能有一个像"门"这样的名字,这本身就没有意义,但完整的背景,"Aaron> House> Living Room> Liquor Cabinet> Door",具有明确的含义,它描述了一个具体的特定门地点.(请注意,这只是一个例子,真正的设计远没那么简单)
• 为了找到这个特定的门,用户可能会输入"aaron酒门",这可能只会产生一个结果.查询被翻译为序列:包含文本"door"的项目,在包含文本"liquor"的项目下,在包含文本"aaron"的另一项下.
• 或者,用户可能只需键入"家酒"就可以列出人们家里的所有酒柜(不会那么好).我明确提到这个例子,表明搜索不需要匹配任何特定的根或叶级别.这个用户确切地知道他正在寻找哪个门,但不记得是谁拥有它,并且会记住这个名字是否出现在他面前.
• 所有术语必须按指定的顺序匹配,但正如上面的示例所示,层次结构中的级别可以"跳过".术语"阿龙酒内阁"将不会匹配这个节点.
• 该平台是SQL Server 2008,但我认为这是一个独立于平台的问题,并且不希望限制该平台的答案.
• 层次结构本身基于hierarchyid(物化路径),索引广度优先和深度优先.每个层次结构节点/记录都有一个Name要查询的列.基于节点的层次结构查询非常快,所以不要担心这些.
• 没有严格的层次结构 - 根可能根本不包含任何节点,或者可能包含扇出到10,000个叶节点的30个子树.
• 最大嵌套是任意的,但实际上它往往不超过4-8级.
• 虽然不经常,但层次结构可以而且确实会发生变化.任何节点都可以移动到任何其他节点,但有明显的例外(父节点不能移动到自己的子节点等)
• 如果还没有暗示:我确实可以控制设计,并可以添加索引,字段,表格,以及获得最佳结果所需的一切.

我的"梦想"是向用户提供即时反馈,如渐进式搜索/过滤器,但我知道这可能是不可能的或非常困难的.我对当前方法的任何重大改进感到满意,通常需要0.5s到1s,具体取决于结果的数量.

为了完整起见,现有查询(存储过程)首先收集包含最终项的所有叶节点,然后向上连接并排除其路径与先前项不匹配的任何路径.如果这对任何人来说都是落后的,那么请放心,它比从根源开始并散开更有效率.这是"旧的"方式,每次搜索可能需要几秒钟.

那么我的问题是: 是否有更好(更有效)的方式来执行此搜索？

我不一定在寻找代码,只是方法.我考虑了一些可能性,但它们似乎都有一些问题:

• 创建一个分隔的"路径文本"列,并使用全文搜索对其进行索引.麻烦的是,对此列的搜索也将返回所有子节点; "aaron house"也与"aaron house kitchen"和"aaron house basement"相匹配.
• 创建一个NamePath实际上是嵌套字符串序列的列,使用CLR类型,类似于hierarchyid它自己.问题是,我不知道微软如何能够将这种类型的查询"转换"为索引操作,我甚至不确定是否可以在UDT上进行.如果最终结果只是一个完整的索引扫描,我通过这种方法得不到任何结果.

如果我不能做得比现有的更好,那真的不是世界末日; 搜索"非常快",没有人抱怨它.但我愿意打赌有人之前已经解决了这个问题,并且有一些想法.请分享!

Answer 1

看看 Apache Lucene。您可以使用 Lucene 实现非常灵活且高效的搜索。它可能有用。

另请查看搜索模式 - 您所描述的内容可能适合分面搜索模式。

实现一个简单的“Aaron House Living Door”算法非常容易，但不确定基于常规 SVM/分类/熵的算法是否可以扩展到大型数据集。您可能还想了解 Motwani 和 Raghavan 的“近似搜索”概念。

如果可能的话，请发回您发现的内容:-)