如何优化这个棘手的 SQL 自连接？

Question

我想对表执行复杂的自联接。我知道理论上这可以非常有效地完成（见下文），但我无法让 SQL（在 Microsoft SQL Server 上）这样做。

我的问题是：

我怎样才能让 SQL 有效地做到这一点？我需要提供哪些信息才能推断出最佳解决方案或类似的快速解决方案？

输入：

我有一个事件表。每个事件都属于某个项目，并且具有两种类型之一。我可以随意使用这个表，并创建我想要的任何索引，因为它是一个中间表。它也仅用于离线处理，因此以后不会添加新数据。

该表有数亿行。type=0 的条目和 type=1 的条目大致以相同的频率出现，并且它们或多或少是公平的分布，因为输入数据是按照某些规则创建的，因此可以假设以下情况为真对于数据：每次type=0发生事件时，涉及的项目的计数器增加，每次type=1发生事件时，它再次减少。计数器将始终介于 0 和 3（含）之间。

该表目前看起来像这样，但您可以随时提出更改建议：

select
    a.item
    ,case when a.<some_condition> then 1 else 0 end as event_type
    ,row_number() over(partition by a.item order by a.date asc) as sequence_id -- this makes the order clearer and deals with duplicate dates in a manner that is acceptable for these purposes
    ,<...> as counter_after_event -- this lies in [1;3] if event_type=0, and in [0;2] if event_type=1
from <original_source_table> a;

我已经尝试了几种类型的索引和这些索引中列的几种顺序，但下面的任务不会变得更快：

任务：

“对于 type=0 的每个事件，找到涉及相同项目的 type=1 的下一个事件。获取 ( item, sequence_id_for_type_0, sequence_id_for_type_1) 的元组。”

获取此信息的查询可能如下所示：

select
    a.item
    ,a.sequence_id as sequence_id_for_type_0
    ,min(b.sequence_id) as sequence_id_for_type_1
from <input_table> a
inner join <input_table> b
    on a.item = b.item
    and a.sequence_id < b.sequence_id
    and a.event_type = 0
    and b.event_type = 1
group by a.item, a.sequence_id;

例子

每个项目都可以单独考虑。对于单个项目， input_table 中按其 sequence_id 排序的条目可能如下所示。条目后的计数器值在括号中给出：

sequence_id=1，类型=0 (1)

sequence_id=2，类型=1 (0)

sequence_id=3, type=0 (2) -- 一次可以将计数器增加/减少一个以上的 sequence_id=1

sequence_id=4，类型=0 (3)

sequence_id=5, type=1 (1) -- 这个条目必须是type=1，因为计数器已经达到最大值

sequence_id=6，类型=1 (0)

sequence_id=7，类型=0 (1)

在此示例中，我们希望此项目具有以下输出对：

sequence_id_for_type_0=1, sequence_id_for_type_1=2

sequence_id_for_type_0=3, sequence_id_for_type_1=5

sequence_id_for_type_0=4，sequence_id_for_type_1=5

理论解决方案：

理论上，这个问题可以很快解决：在 上创建 B 树索引input_table(item, sequence_id, event_type)。遍历树。对于您遇到的每个具有 的节点event_type=0，向前看直到找到带有 的下一个节点event_type=1，但如果项目发生变化，则取消向前看。

如果前瞻找到匹配项，您可以从中构造一个 ( item, sequence_id_for_type_0, sequence_id_for_type_1) 元组。这给出了 的理论运行时间O(n*log(n)*k)，其中k是所需的最大前瞻次数，由于上面对计数器的解释，这是非常有限的（在下一个类型之前，一个项目最多只能有 4 个连续的 type=0 事件=1 必须出现）。

不幸的是，我不知道如何告诉 SQL 后一个事实，它k非常小，因此这是最佳解决方案。

此外，如果索引在几台机器之间进行分区，则所需的最大通信将是每对相邻机器的一个条目：告诉相邻机器一个前瞻超过了索引的自己部分。

SQL 的作用是：

无论我如何设置索引，基本的解决方法都是一样的：

input_table 被并行扫描两次。根据索引，我可以让 SQL 执行一个 index_scan 和一个 index_seek，但我无法让它意识到它可以只对索引的树结构使用前瞻（或者至少如果 SQL 确实意识到了这一点）可以这样做，Microsoft SQL Server 生成的查询计划没有表明这一点）。

在group by以相同的幼稚的方式进行处理如通过任何其它基团：一个哈希表被创建（与（a.item，a.sequence_id）作为密钥）。这给查询增加了不可接受的开销。有没有办法加快速度？

额外学分：

此任务的高级版本不是必需的，但也会有所帮助：使上述计数器明确。我们现在想知道 ( item, sequence_id_for_type_0, sequence_id_for_type_1, counter_value_at_type_1_entry) 的元组。

这理论上将任务难度增加至多 3 倍（因为计数器只能减少到 0、1 或 2）。理论解决方案根本没有太大变化。但是，SQL 查询现在在group by子句中有来自表 b 的条目：

select
    a.item
    ,a.sequence_id as sequence_id_for_type_0
    ,min(b.sequence_id) as sequence_id_for_type_1
    ,b.counter_after_event as counter_after_type_1_event
from <input_table> a
inner join <input_table> b
    on a.item = b.item
    and a.sequence_id < b.sequence_id
    and a.event_type = 0
    and b.event_type = 1
group by a.item, a.sequence_id, b.counter_after_event;

更新

我已经尝试使用 Lead() 函数解决它，并且像下面这样的构造可以解决原始问题：

-- only three values need to be checked, because the counter ensures that we don't have to look at more than 3 following items before getting a type=1 event
,case when lead(a.event_type, 1, -1) over(partition by a.item order by a.sequence_id) = 1
        then lead(a.sequence_id, 1, null) over(partition by a.item order by a.sequence_id)
    when lead(a.event_type, 2, -1) over(partition by a.item order by a.sequence_id) = 1
        then lead(a.sequence_id, 2, null) over(partition by a.item order by a.sequence_id)
    when lead(a.event_type, 3, -1) over(partition by a.item order by a.sequence_id) = 1
        then lead(a.sequence_id, 3, null) over(partition by a.item order by a.sequence_id)
    else null
    end as sequence_id_for_type_1

不幸的是，任务现在已经扩展，我现在正在寻找“额外学分”任务的解决方案。特别是，我最关心的是找到第一个 counter_after_type_1_event=0 的事件。对于这个任务，我们不能使用上面的技巧，因为我们不能设置事件数量的上限，直到我们得到达到特定计数器值的 type=1。

Answer 1

您应该考虑使用LEAD和LAG 分析函数以及适当的索引进行排序。我已经与他们更改了一个自联接查询。经过的时间减少了十倍。