在具有特定基数的映射(联结)表之间加入

Question

关于执行特定连接的最有效方法,我有一个简单的问题.

拿这三张桌子,改名实名来保护无辜者:

表:动物

animal_id   name   ...
======================
1           bunny
2           bear
3           cat
4           mouse

表:标签

tag_id     tag
==================
1          fluffy
2          brown
3          cute
4          small

映射表:animal_tag

animal_id   tag_id
==================
1           1
1           2
1           3
2           2
3           4
4           2

我想找到所有被标记为" 蓬松 "," 棕色 "和" 可爱 "的动物.也就是说,必须用这三种动物标记动物.实际上,所需标签的数量可能会有所不同,但与此讨论无关.这是我提出的查询:

SELECT * FROM animal
JOIN (
      SELECT at.animal_id FROM animal_tag at
      WHERE at.tag_id IN (
                          SELECT tg.tag_id FROM tag tg
                          WHERE tg.tag='fluffy' OR tg.tag='brown' OR tg.tag='cute'
                          )
      GROUP BY at.animal_id HAVING COUNT(at.tag_id)=3
      ) AS jt
ON animal.animal_id=jt.animal_id

在包含数千个"动物"和数百个"标签"的桌子上,此查询的表现相当于...... 10毫秒.但是,当我查看查询计划(Apache Derby是数据库)时,优化程序的估计成本相当高(9945.12),计划相当广泛.对于查询这个"简单"我通常会尝试获得具有单个或两个数字的估计成本的查询计划.

所以我的问题是,是否有更好的方法来执行此查询？看起来像一个简单的查询,但我已经难过提出更好的东西了.

Answer 1

首先，非常感谢所有参与其中的人。正如一些评论者所提到的，最终的答案是关系划分。

虽然我很久以前就参加过 Codd 的关系数据模型课程，但与许多课程一样，该课程并没有真正涵盖关系划分。不知不觉中，我原来的查询实际上是关系除法的应用。

参考本演示文稿中有关关系除法的幻灯片 26-27，我的查询应用了比较集合基数的技术。我尝试了一些提到的应用关系除法的其他方法，但至少在我的例子中，计数方法提供了最快的运行时间。我鼓励对此问题感兴趣的任何人阅读上述幻灯片以及 Mikael Eriksson 在本页引用的文章。再次感谢大家。