SQL 查询挑战

Question

我有一个看起来很容易写的查询，这真的让我难住了 - 谁能帮助我？

所以这在纸面上真的很容易，但我无法将其翻译成 SQL。假设您有一些图形数据：

× | 是

1 | 5.5

2 | 8

3 | 2

4 | 3

5 | 1

而且您基本上想在数据顶部画一条向下倾斜的线，至少触及最顶端的 2 个点，就像这样......

找出新数据何时超过这条线——所以我认为这归结为图形 y=A + Bx 的基本公式 所以，如果我们知道 A 和 B，对于给定的 x 值，我们可以预测 y （更重要的是 y 的新值是否高于或低于我们基于这条线预测的 y 值）。

有人可以帮忙吗？

如果它对任何人有帮助，请非常快速地创建和数据声明...

创建表 graph1 (x int, y decimal(4,2));

插入 graph1 值 (1,5.5),(2,8),(3,2),(4,3),(5,1);

我可以做一个最小二乘回归来为线性回归生成一个方程（一条穿过数据中间的线）——但是我如何为数据所在的通道的顶部生成一个方程？

Answer 1

满足问题的整组线被称为帕累托有效前沿（或前沿或集合）或凸包问题。
_{（另请参阅我在 StackOverflow 上的类似问题中的回答：如何编写选择合理权衡的查询？）。}

因此，解决的一种方法是首先识别前面的点，使用如下查询。我假设有一个独特的约束(x)：

CREATE TABLE pareto AS
SELECT a.x
     , a.y
FROM graph1 AS a
WHERE NOT EXISTS
  ( SELECT 1
    FROM graph1 AS b
    WHERE b.x > a.x
      AND b.y >= a.y
  ) ;

SELECT *
FROM pareto ;

这将导致：

+------+------+
| x    | y    |
+------+------+
| 2.00 | 8.00 |
| 4.00 | 3.00 |
| 5.00 | 1.00 |
+------+------+

穿过这些点的线就是我们的候选线。然而，我们必须消除另一条线通过它的点（如（4,3））。使用递归 CTE 会容易得多，但 MySQL 根本没有实现 CTE。

查询不难编写 - 但您确实需要尝试在临时表上添加一些索引（您甚至可以将其设为普通的 InnoDB 表），尤其是在点数很高的情况下：

SELECT p.x
     , p.y
FROM pareto AS p
WHERE NOT EXISTS   
      ( SELECT 1 
        FROM pareto AS st 
          CROSS JOIN pareto AS en
        WHERE st.x < p.x 
          AND p.x < en.x 
          AND (p.x * (en.y-st.y) + p.y * (en.x-st.x) < 0)
      ) ;

结果：

+------+------+
| x    | y    |
+------+------+
| 2.00 | 8.00 |
| 5.00 | 1.00 |
+------+------+

如果此时预期的点数很高（如 1000+），则 MySQL 的 SQL 查询可能效率低下，因为它需要（临时表的）3 路交叉联接。另一种选择是使用 mysql 变量进行查询，并按x坐标顺序运行（临时）表，消除覆盖的点 - 一个或多个批次。

另一种选择是一次性编写整个查询。适合使用小数据进行测试 - 但如果有数百万行，我什至不会尝试：

SELECT a.x
     , a.y
FROM graph1 AS a
WHERE NOT EXISTS
      ( SELECT 1
        FROM graph1 AS b
        WHERE b.x > a.x
          AND b.y >= a.y
      ) 
  AND NOT EXISTS   
      ( SELECT 1 
        FROM graph1 AS st 
          CROSS JOIN graph1 AS en
        WHERE st.x < a.x 
          AND a.x < en.x 
          AND (a.x * (en.y-st.y) + a.y * (en.x-st.x) < 0)
      ) ;

结果：

+------+------+
| x    | y    |
+------+------+
| 2.00 | 8.00 |
| 5.00 | 1.00 |
+------+------+

请注意所有查询。我希望两者x和ywhere 的类型相同（因此将 xdecimal(4,2)设为 y）。

(x,y)两个查询都将使用索引。