表结构
Tag Table:{tag_id, tag_name} #标签表
News Table:{news_id, title,......} #新闻表
NewsTags Table:{tag_id, news_id} #新闻的标签关系表
解释:
一条新闻,有多个tag标签,例如:
新闻a{Tag1,Tag2, Tag3, Tag4}
新闻b{Tag1,Tag6, Tag7, Tag8}
新闻c{Tag8,Tag9, Tag10, Tag1}
新闻...{Tag..., .....}
搜索出 同时有Tag1,Tag8两个标签的记录。
在MySQL中经过优化后的SQL:
SELECT News.title FROM( SELECT news_id FROM ( SELECT tag_id FROM Tag WHERE tag_name IN('Tag1', 'Tag8') )B LEFT JOIN NewsTags C (B.tag_id = C.tag_id) GROUP BY news_id HAVING COUNT(0)=2 )A LEFTJOIN News B ON(A.news_id = B.news_id)
原理:
此为3重嵌套SQL,可最大限度的快速缩小记录集,以最节省内存的方式得到结果集。
1、最内层取出需要比对的tag_id
2、第二层通过Left join联接,找出同时拥有这些tag_id的news_id记录;本处理的重点是对news_id做Group by然后在Having中统计出数量为2的news_id(即:同时存在这两个tag的记录)
3、最外层根据news_id(这个已经是最终的最小记录集),与News表Left Join求出新闻记录的内容
至此可得到 同时符合 多个Tag名称 的记录集的模板,根据查找的tag数量不同,需在最内层的IN(),与第二层的Having做参数修改就可实现对任意数量的Tag交集求解。
此算法并非最优,但是如果想通过模板方式的一条SQL来实现,基本上这个算是最优的算法(本人愚见哈)。
这个算法的缺点是,如果每个tag对应的记录集数量巨大,且给了很多个Tag求交集,那么第二层的LeftJoin运算会消耗大量的内存空间(因为需要对每个tag_id生成一个news_id的集合,实际上会先得到一个笛卡尔集,然后对这个集合做group,再count)。
如果想把效率与搜索内存资源消耗做极致大致,可做如下修改,思路如下。
1、改造Tag表,增加一个被引用的数量字段,例如:Tag Table:{tag_id, tag_name, links} (其实可以把links看成一个人工索引)
2、维护这种Tag表比较麻烦,考虑到效率,一般会定时的对links字段做全表更新(对于频繁插入或删除记录的news表,可每天临晨,对全记录集的tag做被引用的次数统计并更新links字段)
3、构造动态多层嵌套的SQL语句(即根据tag的数量,生成N层嵌套查询)
实现原理(SQL语句就不写了)
1、根据给定的tag_name找出tag_id,并按对links大小,升序排列
2、首先选取第一个tag_id到NewsTags表求NewsTags.tag_id的交集(此为最小基本记录集)得到news_id,然后对此记录集重复执行这个步骤(逐步缩小记录集),完成所有tags的比对时就能在最小的范围内找出所有同时符合这些tag_id的记录集。
这个算法的核心就是第一次要得到最小的记录集(以最大限度的节省后续的比对次数),然后逐步将这个记录集变得更小,直到比对完成。