如何降低 Mysql 中第 N 位最高的薪资查询复杂度?

Question

我认为在desc中对工资表数据进行排序并放入limit和offset，如下所示的查询会给你结果，但对数千条记录进行排序也会影响性能。

select salary from employee order by salary desc limit (n-1), 1;

所以我的问题是我怎样才能降低这里的复杂性？请帮忙。

Answer 1

ORDER BY意味着排序。 但是，根据查询的其余部分和可用索引，优化程序可能会跳过排序。 (当排序很重要时，请使用ORDER BY，并让优化器尽可能消除它。

OFFSET(LIMIT中具有两个数字的第一个数字)是通过获取所有这些行并抛出它们来实现的。 之后，获取LIMIT行(在您的例子中为"1")以实际交付给您。 也就是说，OFFSET并不便宜，也没有指数的帮助。

如果需要列表的第 100 行(基于某种排序顺序)，则查询是最佳查询。 对"数千"行进行排序通常不是问题。 ("数十亿"将是一个问题。

一个常见的错误是使用以下OFFSET"分页"：

SELECT ... ORDER BY .. LIMIT  0, 10  -- page 1
SELECT ... ORDER BY .. LIMIT 10, 10  -- page 2
SELECT ... ORDER BY .. LIMIT 20, 10  -- page 3
(etc)

这是"二次"性能。 也就是说，不好。

如果无法避免排序，则每个查询都将读取整个数据集。

如果优化器可以使用索引来避免排序，则第一个查询读取 10 行;第二个查询读取 20 行，然后读取 30 行，依此类推。 注意它是如何变得越来越慢的。

(分页的优化涉及"记住你离开的地方"。

您的查询真的是关于薪水并且只获取第 n 个并且只做一次吗？ 或者这是对实际用例的过度简化？ 如果您向我们展示"真实"查询，可能会有其他技巧。

大O：

对 N 行进行排序： O(N*log N)
偏移量 n： O(N)
限制 n： O(N)
选择 N 行： O(N)

使用 偏移量对所有页面进行分页(每页 P 项)，最坏情况： O((N/P)N logN)
带有"left off"的分页：O(N)