优化类别过滤器

Question

This recent question让我考虑优化类别过滤器。

假设我们希望创建一个引用大量音频轨道的数据库，以及它们的发行日期和音频轨道可下载的世界位置列表。

我们希望优化的要求是：

• 给我最近的10个轨道位置，从下载的A.
• 给我最近的10个轨道位置从A或B.
可下载
• 给我从地点A和B下载的10个最新曲目。

如何构建数据库？我有一个很难拿出一个简单的解决方案，不需要通过所有轨道至少一个位置阅读...

Answer 1

要优化这些查询，您需要稍微取消规范化数据。

例如，你可能有一个track表包含轨道的id，name和release date，并描述了这些曲目可以是向下加载map_location_to_track表。要回答“10个最近的位置的轨道”你需要得到所有曲目用于定位在从map_location_to_track，然后将其加入track表由release date命令他们，并挑选前10名

相反，如果所有的数据都在一个表中，订购步骤可以避免。例如...

CREATE TABLE map_location_to_track (
    location_id INT, 
    track_id  INT, 
    release_date DATETIME, 
    PRIMARY KEY (location_id, release_date, track_id) 
) 

SELECT * FROM map_location_to_track 
WHERE location_id = A 
ORDER BY release_date DESC LIMIT 10 

将location_id作为主键中的第一个条目可确保WHERE子句仅仅是索引查找。那么不需要重新排序数据，它已经通过主键为我们订购了，而是在最后选择了10条记录。

您确实仍然可以加入track表以获取名称，价格等，但您现在只需为10条记录执行此操作，而不是在该位置执行所有操作。

为了解决同一查询“位置A 或 B”，有一对夫妇的，可以执行不同取决于你使用的RDBMS选项。

首先是简单的，但一些RDBMS不玩在尼斯...

SELECT track_id, release_date FROM map_location_to_track 
WHERE location_id IN (A, B) 
GROUP BY track_id, release_date 
ORDER BY release_date DESC LIMIT 10 

下一个选项是几乎相同的，但还是有些RDBMS不玩漂亮或被应用逻辑到INDEXes。

SELECT track_id, release_date FROM map_location_to_track 
WHERE location_id = A or location_id = B 
GROUP BY track_id, release_date 
ORDER BY release_date DESC LIMIT 10 

在任何一种情况下，用于将记录列表合理化为10的算法对您都是隐藏的。这是一个尝试和看到的问题;索引仍然可用，因此可以执行此操作。

另一种方法是明确地确定你的SQL语句的方法的一部分......

SELECT 
    * 
FROM 
(
    SELECT track_id, release_date FROM map_location_to_track 
    WHERE location_id = A 
    ORDER BY release_date DESC LIMIT 10 

    UNION 

    SELECT track_id, release_date FROM map_location_to_track 
    WHERE location_id = B 
    ORDER BY release_date DESC LIMIT 10 
) 
    AS data 
ORDER BY 
    release_date DESC 
LIMIT 10 

-- NOTE: This is a UNION and not a UNION ALL 
--  The same track can be available in both locations, but should only count once 
--  It's in place of the GROUP BY in the previous 2 examples 

这是仍有可能为优化器来实现，这两个联合在一起的数据集是有序的，所以通过非常快速的外部订单。然而，即使没有，订购20件产品也很快。更重要的是，它是一个固定的开销：如果您在每个位置上十亿的轨道，我们只是合并的10

最难的两个列表优化不要紧的AND条件，但即使如此，“十大”限制的存在也可以帮助创造奇迹。

向基于IN或OR的方法添加HAVING子句可以解决此问题，但同样取决于您的RDBMS，可能运行得并不理想。

SELECT track_id, release_date FROM map_location_to_track 
WHERE location_id = A or location_id = B 
GROUP BY track_id, release_date 
HAVING COUNT(*) = 2 
ORDER BY release_date DESC LIMIT 10 

另一种方法是尝试 “两个查询” 的方式...

SELECT 
    location_a.* 
FROM 
(
    SELECT track_id, release_date FROM map_location_to_track 
    WHERE location_id = A 
) 
    AS location_a 
INNER JOIN 
(
    SELECT track_id, release_date FROM map_location_to_track 
    WHERE location_id = B 
) 
    AS location_b 
    ON location_a.release_date = location_b.release_date 
    AND location_a.track_id  = location_b.track_id 
ORDER BY 
    location_a.release_date DESC 
LIMIT 10 

这个时候我们无法限制两个子查询仅10记录;对于我们所知的最近的10个位置a不出现在位置b 的所有。不过，主要关键在于拯救我们。这两个数据集由发布日期组织，RDBMS只是从每个集合的最高记录开始，合并两个记录直到它有10个记录，然后停止。

注：由于release_date是在主键和track_id之前，应该确保它在连接使用。

根据RDBMS，您甚至不需要子查询。您可以可能能够在不改变RDBMS计划的情况下自行加入表格...

SELECT 
    location_a.* 
FROM 
    map_location_to_track AS location_a 
INNER JOIN 
    map_location_to_track AS location_b 
    ON location_a.release_date = location_b.release_date 
    AND location_a.track_id  = location_b.track_id 
WHERE 
     location_a.location_id = A 
    AND location_b.location_id = B 
ORDER BY 
    location_a.release_date DESC 
LIMIT 10 

总而言之，三样东西的组合使这相当有效：
- 部分去标准化数据，以确保它是在一个友好的订单我们需要
- 了解我们只有永远都需要的前10个结果
- 知道我们永远只用2个地点处理在最

有些变化可以优化任何数量的记录和任意数量的位置，但这些性能远低于此问题中所述的问题。

Answer 2

在一个典型的关系模式中你将有一个多一对多的关系以避免冗余：

CREATE TABLE tracks (
    id INT, 
    ... 
    release_date DATETIME, 
    PRIMARY KEY (id) 
) 

CREATE TABLE locations (
    id INT, 
    ... 
    PRIMARY KEY (id) 
) 

CREATE TABLE tracks_locations (
    location_id INT, 
    track_id  INT, 
    ... 
    PRIMARY KEY (location_id, track_id) 
) 

SELECT tracks.* FROM tracks_locations LEFT JOIN tracks ON tracks.id = tracks_locations.location_id 
WHERE tracks_locations.location_id = A 
ORDER BY tracks.release_date DESC LIMIT 10 

您可以使用表分区按位置修改该模式。问题在于它取决于实施问题或使用限制。例如，MySQL中的AFAIK不能在分区表中有外键。为了解决这个问题，你也可以有一组表格（称之为“手工分区”），如tracks_by_location_#，其中#是已知位置的ID。这些表格可以存储过滤的结果，并使用触发器创建/更新/删除。