优化类别过滤器

Question

这个最近的问题让我考虑优化类别过滤器.

假设我们希望创建一个引用大量音轨的数据库,其发布日期和可从中下载音轨的世界位置列表.

我们希望优化的请求是:

• 给我从位置A下载的10条最新曲目.
• 给我一些可从A或B位置下载的最新曲目.
• 给我一些可从A和B位置下载的最新曲目.

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

Answer 1

要优化这些查询,您需要对数据进行轻微的规范化.

例如,你可能有一个track包含轨道的表id,name并release date和map_location_to_track描述表,其中这些曲目可以从下加载.要回答"位置A的10个最近的曲目",您需要获取位置A的所有曲目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不适合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逻辑应用于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条件,但即使这样,"TOP 10"约束的存在也可以帮助创造奇迹.

向基于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次没有出现在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个地点

有些变体可以针对任意数量的记录和任意数量的位置进行优化,但这些变量的性能远低于此问题中所述的问题.