类别滤波器的优化

Question

This recent question让我考虑优化类别筛选器。

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

我们希望优化的请求是：

• 给我10首最近可从A位置下载的曲目，
• 给我10首最近可从地点A或B下载的曲目，
• 给我10首最近可从地点A和B.

下载的歌曲。

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

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 或 B“的相同查询，有两个选项可以根据您使用的关系数据库以不同的方式执行。

第一个很简单，尽管一些关系数据库管理系统对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

下一个选项几乎相同，但仍有一些关系数据库管理系统对将OR逻辑应用于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亿首歌曲，我们只是合并两个10首歌的列表。

最难优化的是和条件，但即便如此，“十大”约束的存在也能帮助创造奇迹。

在基于IN或OR的方法中添加HAVING子句可以解决这个问题，但是，同样地，取决于您的关系数据库管理系统，可能运行得不太理想。

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中。但是主钥匙又救了我们一次。这两个数据集是按发布日期组织的，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

总之，三种因素的结合使之变得非常有效率：

部分去规范化数据，以确保它对我们的needs

• Knowing是友好的，我们只需要前10 results

• Knowing，我们只在最多处理

的两个位置处理过

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

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中，不能在分区表中有外键。要解决这个问题，您还可以拥有一个表集合(称为“手工分区”)，如tracks_by_location_#，其中#是已知位置的ID。这些表可以存储筛选的结果，并使用触发器创建/更新/删除。