sql - 优化类别过滤器

Question

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

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

我们希望优化的请求是:

给我可以从 A 位置下载的 10 首最新轨道。

提供可从位置 A 或 B 下载的 10 首最新轨道。

提供可从位置 A 和 B 下载的 10 首最新轨道。

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

Answer 1

要优化这些查询，您需要稍微对数据进行非规范化。

例如，您可能有一个 track包含轨道 id 的表, name和 release date , 和 map_location_to_track描述可以从何处下载这些轨道的表格。要回答“位置 A 的 10 个最新轨道”，您需要从 map_location_to_track 获取位置 A 的所有轨道。 ，然后将它们加入 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 条记录执行此操作，而不是该位置的所有记录。

要解决对“locations A OR B”的相同查询，有几个选项可以根据您使用的 RDBMS 执行不同的操作。

第一个很简单，尽管有些 RDBMS 不能很好地与 IN 配合使用……

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 在将 OR 逻辑应用于 INDEX 时表现不佳。

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 亿首轨道并不重要，我们只是合并了两个 10 首轨道。

最难优化的是 AND 条件，但即便如此，“TOP 10”约束的存在也有助于创造奇迹。

将 HAVING 子句添加到 IN或 OR基于方法可以解决这个问题，但是，同样，根据您的 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 条记录；据我们所知，位置 a 中最近的 10 个根本不会出现在位置 b 中。不过，主键再次拯救了我们。这两个数据集是按发布日期组织的，RDBMScan 只是从每个数据集的顶部记录开始并将两者合并，直到它有 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 个地点

存在可以针对任意数量的记录和任意数量的位置进行优化的变体，但这些变体的性能明显低于此问题中所述的问题。