如何優化這個棘手的 SQL 自連接？

我想在表上執行複雜的自聯接。我知道這在理論上可以非常有效地完成（見下文），但我很難讓 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;

例子

每個項目都可以單獨考慮。對於單個項目，按其 sequence_id 排序的 input_table 中的條目可能如下所示。條目後的計數器值在括號中給出：

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

理論解決方案：

理論上，這個問題可以很快解決：在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）。理論解決方案根本沒有太大變化。group by但是，SQL 查詢現在在子句中有一個來自表 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 達到特定計數器值之前，我們不能對事件數量設置上限。

您應該考慮使用LEAD和LAG 分析函式以及適當的索引進行排序。我已經用他們更改了一個自聯接查詢。經過的時間減少了十倍。

我並沒有真正遵循這些範例，而只是基於：

每次 type=0 的事件發生時，所涉及的項目的計數器都會增加，而每次 type=1 的事件發生時，它會再次減少。計數器必須始終位於 0 和 3（含）之間。

如果您只需將 event_type 更改為 -1 和 1 會更容易

select item, min(seq) 
from ( select a.item
           , row_number()           over(partition by a.item order by a.date asc) as seq
           , sum(-2*event_type + 1) over(partition by a.item order by a.date asc) as counter 
        from <original_source_table> a 
    ) tt 
where counter < 0 or counter > 3 
group by item;

上面找到違規

如果你只是想要好的然後翻到哪裡並

從問題中刪除組和分鐘不清楚你想用這個計數器

做什麼並且你似乎沒有在任務中解決計數器

至於任務

select *
 from ( select a.item
             , row_number()           over(partition by a.item order by a.date asc) as seq
             , sum(-2*event_type + 1) over(partition by a.item order by a.date asc) as counter
             , lead(event_type)       over(partition by a.item order by a.date asc) as lead_event_type 
          from <original_source_table> a 
      ) tt 
where event_type 0 lead_event_type = 1;

就理論上而言，為什麼要向前看每一行？

只需讀取行並將 0 保存在緩衝區中

如果您獲得 1 則使用 1 資訊更新緩衝區並寫出緩衝區

如果您獲得新項目然後丟棄緩衝區

這是一個簡單的單遍操作

這將是全部帶有 CLR 的 12 行 C#

引用自：https://dba.stackexchange.com/questions/128837