sql - 使用像素检测正方形

Question

这是一个有趣的问题。假设我在 sql 数据库上有一个表，其中填充了 x、y 坐标(正象限)并且每个表都有一个颜色值，即模式看起来像 <x , y, color> .任务是检测具有相同颜色的最大可能正方形。几个小时以来，我一直在尝试解决这个问题，但似乎无法解决这个问题。

我不是在寻找解决方案，而是在寻找提示。

请注意，这一切都必须在 SQL 中发生，主要使用各种连接、分组和聚合操作。一些示例代码会很好。

Answer 1

如果你只要求角的颜色相同，你可以这样做

top left corner
join top right corner on equal x and color and greater y
join bottom left corner on equal y and color and greater x
join bottom right on equal x, y and color
order by (x1-x2)*(y1-x2) descending
limit 1

当然，限制 1 不会对性能产生太大影响，因为无论如何它都必须生成所有正方形。

您可以通过添加 (color,x,y) 和 (color,y,x) 索引(大大)提高速度。执行计划很可能会结束:

(1) full scan for all top left corners
(2) dependent index scan for all top right corners
(3) dependent index scan for all bottom left corners
(4) dependent index scan for the bottom right corner expecting at most one match
(5) (partial) table sort of the entire set of squares (cannot use indexes)