百姓网公开笔试题:查询条件的子集判断

这是发布在百姓网官方blog上的一道公开笔试题。转发到这里,我知道我的blog读者有很多优秀的程序员,还有我敬仰的一些技术大牛,热切希望能够得到你的来信,并且有机会一起解决一个又一个这样有趣的技术挑战。也欢迎转载,多谢!

=====================================

百姓网需要最聪明,最有潜力的技术牛人来帮助我们给世界惊奇。为了让我们互相找到的过程变得更加直接了当,我这里有一个公开的笔试题目。这是我们日常的工作中遇到的一个典型问题。如果你有答案,请直接寄到 geeks @ baixing.com而不需要使用 shhr @ baixing.com。

题目

请写一个算法,判断一个查询表达式是不是另外一个查询表达式的子集。

稍微加一点解释

就拿SQL语句为例,如果查询A是

age > 21

查询B是

age > 20

我们知道,A所代表的集合是B所代表的集合的子集。凡是满足A的条件的记录,也一定满足B的条件。我需要一个算法,在给出任意两个表达式以后,判断一个是不是另外一个的子集。

if($queryA->isSubSet($queryB)) { echo(“A is subset of B”);}

为了简单起见,只需要实现最简单的AND, OR逻辑操作,大于,等于,小于三种比较操作就好。最好用PHP,其他语言,比如Java也没问题。

这有什么用呢?

这是个我们不到10人的技术团队日常典型需要解决的问题。给个例子:百姓网为了应付更大的搜索数据量,把搜索分布在多个城市的多台服务器上。系统管理员可以根据数据的使用频度等规律,配置几个不同的数据库(MySQL的,和Solr的)。这样,当有一个新的广告出来后,子集算法根据搜索库的配置查询就可以决定,它更新到哪一个或多个库里面。

查询的时候,如果确认给定的查询条件是以前配置的一个库的子集,就可以只从那个库里查询了。这可以让我们轻松地配置几十个搜索库,而不用改一行代码。

热切期待优秀的你和我们联系。重复一遍:邮件请发到:geeks @ baixing.com

这里是百姓网的职位

《百姓网公开笔试题:查询条件的子集判断》上的44个想法

  1. 说明用的例题可能有误哦。age=22, height=159 这个样本满足A但不满足B,所以A不是B的子集。把例子中 AND 改成 OR 的话就可以了。

  2. @gx,对的。一个笔误,原来的A比较复杂,改了改,改错了。该打。看了你的blog制造回忆,很有意思,悠闲、唯美。

  3. 1、$queryA和$queryB是字符串吗?还是已经处理好的逻辑树?
    2、比较操作的右端都是常量,还是有可能是变量?例如是否需要考虑 “A>B AND B>C”->isSubSet(“A>C”) 的情形?

  4. 感觉很难找到一个通用的方法,具体问题具体分析,一共又多少种查询语句列一下,通常只有少数语句会占用很大量的资源。不追求完美,not that perfect but doable and feasible

  5. @qmigh: 为了简化起见,$queryA 和 $queryB 可以是一个Query构造器 (QueryBuilder),大家可以自己写,比从字符串分析简单一点。我们的Builder是这样子的:
    $queryA = new AndQuery(
      new RangeQuery(‘age’, 20),
      new NotQuery(‘status’, true)
    );
    大家可以自己写一个自己顺手的builder。
    比较操作只要考虑左边是field名,右边是常量就好了,这是最简单,也是到现在需要用得到的部分。

    @tyler durden,我同意这个“感觉起来很难”。也同意“not that perfect but doable and feasible”,我们最需要的就是就是实用主义的解决方案,但无论什么“主义”,首先要有一个解决方案。

    谢谢大家参与,有什么问题可以问我。

  6. 谢谢你的回复,如果能分享一下更多的具体场景,也许大家可以帮忙。如果只是单纯的判断mysql查询条件的判断,个人感觉范围大一些,也许不能最好的得到解决。提几点,mysql proxy似乎有SQL parser的功能,用lua可以操作。另外,有一个用二进制位求所有子集的方法,不知是否能有启发

  7. 路过的 :) SQL语句本来就是用来处理 Set和Bag所优化出来的语言 是不是更应该和把所有条件放到表内去搜比用算法更合理?

  8. 路过,提供一种纯理论的思路:

    【1】将原问题[判断1个复杂范围是否是另1个复杂范围的子集]降解为[判断1个数是否为1个简单范围的子集]
    【2】1个简单范围可以降解为2个数(或1个,当等于时);比如age>30,即取 31,999999(根据场景定义)
    【3】 AND/OR的处理就比较简单了,不说了

    不知道会不会有bug,具体实现就不说了,大家都懂得~

  9. @tyler durden,具体的场景在上文里面简单描述了。再详细一点,就是说我们可能有非常多为不同的场景优化的数据库,切割的维度可能都不一样。比如:
    – 为实时优化的实时库(小但是快),是按照时间维度切的;
    – 为了地域优化的地域库(比如上海库),是按照地域维度切的
    – 为了查询优化的active广告库,是按照状态维度切的
    – 为了最全的数据优化的大数据库(全却慢),可能把5年的数据都放进去

    还有合并了各种维度为每种特殊情况优化的库。手工判断一个广告进哪个库,从哪个库查已经越来越复杂,会因为一个小调整而产生大调整。所有这些问题,在数据量不大或者对速度要求不高的情况下都是没有的。我要解决的是大数据量的分布式查询问题。

    我们实际的应用中对于基于Solr的搜索库的切分的需求大于对MySQL的切分。MySQL其实内部的Partition等方案已经大概的解决了类似的问题。

    而且这个算法是一个比较通用的算法,MySQL和SQL Server里的Query Optimizer在优化Execution Plan的时候就是类似的算法,只是懒得去看源代码,而是用一个很简单的算法来完成。对于SQL Parser和lua,愿闻其详。

    @AvergerMoJo,抱歉,可否更详细一点?多谢

  10. 谢谢你的回复。根据你提供的场景,我想说一点针对这个场景的其他想法,不知可否?从我的理解来看,solr搜索和MySQL都存在数据量过大,或者数据热点问题,而且搜索方面的瓶颈可能更为突出一些。

    第一种方法是加缓存,memcache或者redis都可,而且最好是主动缓存(只有数据更新的时候才去更新缓存)。被动缓存比较常见,而且实现也比较简单,尚不赘述,只是被动缓存会对网站的实时性造成影响。主动缓存有几个实施的难点,针对MySQL,通过日志分析得到影响资源最大的几个SQL语句类型,对这几种语句进行优化,一个可能的办法是利用mysql proxy对这些语句进行一些调整,使得一些记录通过ID调用memcache得缓存;并在web前端得程序种加入对缓存得更新处理(如果对mysql log进行分析得到更新也可,类似与log同步机制,不用修改前端程序,只是实施代价稍大);针对solr搜索,同样是先通过日志分析热点,对于这样得搜索加入缓存,对于搜索结果得主动更新缓存,更为麻烦一些,可能需要对一条信息所有可能得搜索条件求子集,然后批量进行更新。

    个人感觉缓存是可以用并且应该用好,只是需要很精心得设计。(不知到你们已经在用?)

    另一个思路是采用分布式的处理方式。这个思路可以从Cassandra展开,C*的bigtable的数据模型似乎更适合baixing.com的半结构化信息(结构很多,对应到MySQL可能要分很多表,或者采用entity-attribute-value模式存储),同时C*的分布式处理模型能减少mysql partition/sharding带来的维护成本。分布式的搜索可以参考一下lucandra,一个结合了lucene/solr和Cassandra 的东西(可能还不适合用于生产环境,但是个不错的思路)。分布式的东西很多,个人感觉C*相对来说更简单实用一些

    以上只是一些浅见,而且很多地方也非这几个字能描述的清楚。各位看了,见笑见谅:)

  11. 随手写了个实现,因为命题规定简单的逻辑操作,所以逆波兰计算最简表达式之后展开成为若干个与子式的或操作,因为是&&操作,所以对每个token的区间操作可以做简单的删减,再将各个&&子式的离散区间进行合并。最后再遍历A查询的各个token的区间是否都落在B查询的该token的区间上。考虑到查询语句的长度,子式应该不多,所以离散化检查区间应该更具效率,但是编程比较烦,用线段树实现比较简单。实现的很丑陋…..

  12. 是说要支持无限括号么?

    写了一下午,发现写错了

    如果我没理解错的话,这题狂难

    不是抢答吧?

    建议有答对的的就公布一下,超过三个我就放弃挣扎了……

  13. @tyler durden,你说的应用系统其他层的解决方案,比如memcached,的确都在使用,不过我们非常开心的看到,随着数据量的增大,原有的解决方案还是捉襟见肘(多兴奋的一件事情呀!技术人员最幸福的就是有足够挑战的问题需要解决)。比如说,很多的方案在跨服务器或者cluster没有问题,跨数据中心的时候就有问题。而且考虑到系统的延续性,也不能今天MySQL,明天Cassandra这样的折腾,所以才有了这道题目。这是我们在去年面临的一个实际问题。谢谢你的建议。

    @mikster,想法相当不错,只是以我愚见,逆波兰表达式在这个帮不了忙,但是想法和我是一致的。

    @Platinum,别放弃,不是抢答,长期有效。在百姓网,经常遇到的技术问题都是没有现成答案的。虽然实际使用中大概支持个五、六级括号就好了,但是这道题是应该支持无限括号和所有And,OR,Not及括号组成的表达式的 – 都是一个算法。这道题难倒也不是特别难,就是比较耗费体力。选这个题,倒也不是因为难,而是的确这就是一个典型的应用。

    现在已经收到大家的邮件了。非常感谢大家的热情。如果在寄过来算法的时候一并有简历就最好了。

  14. 实际上是高维空间里的覆盖问题,离散化后逐个检查是朴素做法,复杂度取决于每次排除后的分裂速度。逆波兰是将空间立方体化的手段而已。如果高维线段树空间和速度都不好,所以朴素做法还是最好的,但是看起来还是不能满足要求
    我比较怀疑这个问题的下限。

  15. 如果是处理QueryBuilder的话,那简单很多哦。其实这里面最繁琐的一步就是解析字符串格式的Query。其实就算是字符串形式的,如果每个AND和OR都有括号括起来的话,处理也不复杂。

    我不认为tyler durden的“很难找到一个通用的方法”的想法是对的。这应该有通用解决办法的。

    初步思路就是把queryA和queryB分别规整为一系列的原子条件的AND集合的OR集合。例如,将
    (A20) AND (B20)
    变换成为:
    (A20) OR (A>20 AND B20 AND B>20)

    为方便叙述,我们将A20等称为“原子条件”,将原子条件的AND集合,称为“条件集”。将条件集的OR集合,称为“查询”。

    要判断查询A是否为查询B的子集,需要将A的所有条件集都为B的子集。

    要判断一个条件集A’是否为查询B的子集,只需要A’为B的任意一个条件集的子集。

    要判断一个条件集A’是否为条件集B’的子集,需要A’的所有原子条件A”:或者在B’中没有相应的条目,或者B’中的相应条目的条件已经涵盖了A”,我相信这一步已经很容易做了。

    ————————————-

    写完了之后,发现已经有mikster的留言把上面这个过程用很数学的术语给描述过了。苍天作证,我是写完之后才看到那个留言的,绝对没有抄袭。 :-D

  16. 贴出来怎么变这样了。
    中间的那一段是:

    (A20) AND (B20)
    变换成为:
    (A20) OR (A>20 AND B20 AND B>20)

  17. 呃~~

    (A<10 OR A>20) AND (B<10 OR B>20)
    变换成为:
    (A<10 AND B<10) OR (A<10 AND B>20) OR (A>20 AND B<10) OR (A>20 AND B>20)

    这样总该行了吧

  18. 我写了一个比较简单的,处理QueryBuilder的方法,发到邮箱里了!很惭愧限制条件比较多!

  19. to gmigh,我写了把查询字符串 parse 成语法树的代码,但对于复合查询如何判断子集关系,从你的回复里得到启发了。thx。

  20. 早上好。

    @gmigh,相当清晰的算法。
    @Raidenxu,抱歉,还需要考虑一下,并不是那么简单。再试试?

    欢迎大家继续寄写好的代码(PHP或者Java的)到geeks@baixing.com来。如果能注明希望在百姓网工作还是仅仅是有兴趣切磋一下会最好(否则我们有点迷茫,不知道接下来怎么处理)。最好同时有简历。谢谢。

  21. 基本上如qmigh所说的,可以解决and,or的逻辑运算问题,可以称之为规范化。
    正确流程我认为是
    1.预处理,主要是去除所有的not,如not(a > 3 or b > 5)改为a b and b > c 与 a > c ,后者是前者的子集

  22. 是我的问题。MTCommentBody忘了encode_html,以前没有觉得,现在大于号小于号满天飞的代码就出问题了。现在应该好了。

  23. 嗯,写了一份自己的答案,自己测试了一些情况,发现没有问题,写了个具体点的方案描述文字,已连代码给博主发去。
    解题关键字:语法树,与或树
    以下是用来测试的一些用例
    t2 = Query(‘age > 18 and weight 18 or weight 40’) # 中年人
    t1 = Query(‘age > 18’) # 成年人
    t0 = Query(‘(age 30’)
    t1 = Query(‘age < 7’)
    t2 = Query(‘age < 18’)

  24. 翻了下离散数学,觉得可以这样做。

    设有两集合
    I. A > 30 | A >5 & B > 20
    II. A > 20 & B =30

    做一下alias, 保证
    Q = A > 30
    W = A > 5
    R = B > 20
    T = A > 20
    Y = B=30

    I. = Q | W & R
    II. = T & Y

    如果II是I的子集,则I 交 II应该等于II。
    I & II = T & Y & ( Q | W & R )

    简单地,用真值表法求出唯一主析取范式。这个程序应该能比较容易实现。

    Q W R T Y IsFits
    1. 0 0 0 0 0 F
    2. 0 0 0 0 1 F
    3. 0 0 0 1 0 F
    4. 0 0 0 1 1 F
    5. 0 0 1 0 0 F
    6. 0 0 1 0 1 F
    7. 0 0 1 1 0 F
    8. 0 0 1 1 1 F
    9. 0 1 0 0 0 F
    10. 0 1 0 0 1 F
    11. 0 1 0 1 0 F
    12. 0 1 0 1 1 F
    13. 0 1 1 0 0 F
    14. 0 1 1 0 1 F
    15. 0 1 1 1 0 F
    16. 0 1 1 1 1 T
    17. 1 0 0 0 0 F
    18. 1 0 0 0 1 F
    19. 1 0 0 1 0 F
    20. 1 0 0 1 1 T
    21. 1 0 1 0 0 F
    22. 1 0 1 0 1 F
    23. 1 0 1 1 0 F
    24. 1 0 1 1 1 T
    25. 1 1 0 0 0 F
    26. 1 1 0 0 1 F
    27. 1 1 0 1 0 F
    28. 1 1 0 1 1 T
    29. 1 1 1 0 0 F
    30. 1 1 1 0 1 F
    31. 1 1 1 1 0 F
    32. 1 1 1 1 1 T

    则主析取范式为:
    (!Q & W & R & T & Y) | (Q & !W & !R & T & Y) | (Q & !W & R &T & Y) | (Q & W & !R & T & Y) | (Q &W &R & T &Y)

    代入替换,因为是简单一元的与关系,可以比较容易合并:
    B=30, A 20 | NULL | NULL | NULL | A > 30 & B=30

    =
    B=30 & A 20 | A > 30 & B=30

    做到这里就不是很确定了。对于这次,我们可以用反分配律, 得出 B = 30 & ( 2030),
    B=30 & A>20。可能还有一些其他情况无法用分配律可以化简的。

    化简后和II一样,得证。

  25. 对了,集合II也需要化为 主析取范式才好比较。这里不需要化。

  26. 用离散数学的知识肯定能解决
    但有点像用微积分求灯泡的容积一样 有点大才小用
    其实把灯泡里倒满水 量一下就行了么

    A:(age>21)and(level>1)
    B:(age>20)or(level>0)

    首先 把每个字段分段
    age :分成 [0 ,20 ,21] 三段
    level :分成 [0, 1] 两端
    这很容易实现
    然后 每段取中点 作为测试值
    age: [10,20.5,22]
    level: [0.5,2]
    然后 age*level 产生测试用例
    放到A和B里测试
    如果存在一个值属于A却不属于B……

    怎么样 暴力吧
    这叫乱拳打死老师傅
    想想看 效率反而可能是最高的

    不过 我写这样 求职您要么

  27. 楼上的,可以用蒙特卡洛的,如果tolerance高的话,但是你这样做出错的几率肯定是不能容忍的。

  28. 额…貌似我理解错楼上的意思了.
    等于的情况也要考虑的。
    的确这样做复杂度最低,而且是可以证明的,那就是取所有的端点,以及端点的中点,联合产生检查点。
    我想得太复杂了….

  29. 对哦 如果是>=就不取中点 直接取端点
    分段那一步 应该可以剪枝
    如果一个字段在AB里分段一样的话 一定条件下可以忽略该字段

    大家可以想想这里应该怎么写

    今天要做6个小时的车 可能没精力写一个完整的程序出来了

  30. “而且这个算法是一个比较通用的算法,MySQL和SQL Server里的Query Optimizer在优化Execution Plan的时候就是类似的算法,只是懒得去看源代码,而是用一个很简单的算法来完成。对于SQL Parser和lua,愿闻其详。”

    我认为SQL Server做查询计划优化的时候主要还是根据统计信息来决定使用什么索引,如何使用索引,而非王建硕认为的那样归并查询条件的。例如最简单的一个例子:
    SELECT *
    FROM [Order]
    WHERE [sOrderID]=’R10000510000000001′
    AND [sOrderID]<>’R10000510000000001′
    这样一个查询式,我想人一眼就可以看出最高效的查询计划就是返回空集合,因为不可能存在这样的记录。而SQL Server的查询计划还真是去查找这条id的记录,然后在当中筛选出id不等于的记录,也就是说,SQL Server没能认出这其实是一个空集。
    根据阅微堂(http://zhiqiang.org/blog/science/computer-science/database-query-is-np-hard.html)中给出的证明来看,要证明一个查询是空集都是一个NP问题,那么判定是否是子集一定是一个NP问题,所以这个问题我赞同阅微堂的答案,没有什么多项式算法。
    但是我认为可以参照SQL Server一样,为各种数据源建立统计信息,在查询时可以参考一下统计信息来得到一个近似的最优查询计划。一个问题往往在数学上没有答案时,用概率统计方法可以得到很近似最优解的解。

  31. 能否多加加上一些测试,比如4-5层括号的典型例子,
    问题更有针对性?
    比较各种方案,也有依据。

    讨论一般意义的query subset 过于理论化了。

  32. 感谢大家的参与。我们收到了很多种不同的答案。这是一道有趣却也很实用的问题。大家的结局方案从Java,到C++,到PHP,到Python都有。技术的世界就是好,技术人员看到有挑战性的问题,撸起袖子就开始写代码,写好调好就心满意足。已经寄过来的朋友当然欢迎把答案发到自己的blog上面,晚些我会把链接给大家。

  33. 重新写了个算法,已经发给博主,献丑了!
    只能处理QueryBuilder,不能处理NOT,可以处理多层括号,
    关于把查询字符串 parse 成语法树,很有兴趣了解!

  34. 两个 OR 之间怎么比较是否是子集?
    如 age > 15 OR height == 0 与 age > 20 OR gender == 1

  35. To: freddu,
    要判断第一个OR是否第二个OR的子集,只要第一个OR中的所有分子是第二个OR中任意一个分子的子集即可。

  36. 前面的表达有点问题,应该是:
    要确定第一个OR是第二个OR的子集,只要第一个OR中的所有分子是第二个OR中任意一个分子的子集即可。

  37. r= age > 15 OR height == 0 与 age > 20 OR gender == 1
    ==> use f1 or f2 f3 or f4 replace four exp
    ==> r= f1 in f3 or f1 in f4 or f2 in f3 or f2 in f4
    ==> r= 0 or 0 or 0 or 0
    r is 0

发表回复

您的电子邮箱地址不会被公开。