4

I want to perform a complex self-join on a table. I know that this could in theory be done very efficiently (see below), but I have trouble getting SQL (on Microsoft SQL Server) to do so.

My question is:

How can I get SQL to do this efficiently? What information do I need to provide it to be able to infer the optimal solution, or something similarly fast?

The input:

I have a table of events. Each event belongs to a certain item and has one of two types. I am free to do with this table whatever I want, and create any index I want, as it is an intermediate table. It is also only used for offline processing, so no new data will be added later.

The table has hundreds of millions of rows. Entries with type=0 and entries with type=1 appear roughly with the same frequency, and they are more or less fairly distributed because the input data is created in a way that follows certain rules, so that the following can be assumed to be true for the data: Each time an event of type=0 happens, a counter increases for the item involved, and each time an event of type=1 happens, it decreases again. The counter will always lie between 0 and 3 (inclusive).

The table currently looks like this, but you can feel free to suggest changes:

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;

I have tried several types of indices and several orders of the columns in those indices, but the below task will not get any faster:

The task:

"For each event of type=0, find the chronologically next event of type=1 that involved the same item. Get tuples of (item, sequence_id_for_type_0, sequence_id_for_type_1)."

A query to get this could look like this:

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;

Example

Each item can be considered separately. For a single item, the entries in input_table ordered by their sequence_id could look like the following. the value of the counter after the entry is given in brackets:

sequence_id=1, type=0 (1)

sequence_id=2, type=1 (0)

sequence_id=3, type=0 (2) -- an increase/decrease of the counter by more than one sequence_id=1 at a time is possible

sequence_id=4, type=0 (3)

sequence_id=5, type=1 (1) -- this entry must be type=1, since the counter has reached its maximum

sequence_id=6, type=1 (0)

sequence_id=7, type=0 (1)

In this example, we would want the following output pairs for this item:

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

The theoretical solution:

In theory, this problem could be solved very quickly: Create a B-Tree index on input_table(item, sequence_id, event_type). Traverse the tree. For every node you encounter that has event_type=0, look ahead until you find the next node with event_type=1, but cancel the look-ahead if the item changes.

If the look-ahead finds a match, you can construct a (item, sequence_id_for_type_0, sequence_id_for_type_1) tuple from it. This gives a theoretical runtime of O(n*log(n)*k), where k is the maximum number of look-aheads required, which is very limited due to the above explanation of the counter (there can be only up to 4 consecutive type=0 events for an item before the next type=1 must occur).

Unfortunately, I don't know how to tell SQL this latter fact, that k is very small and that this is therefore the optimal solution.

Also, if the index is partitioned between several machines, the maximum communication necessary would be one entry per adjacent pair of machines: to tell the neighbouring machine that one's last look-ahead exceeded the own part of the index.

What SQL does instead:

Regardless of how I set my indices, the basic solution approach is always the same:

The input_table is scanned twice, in parallel. Depending on the indices, I can get SQL to perform one index_scan and one index_seek instead, but I can't get it to realize that it could just use a look-ahead on the index's tree structure (or at least if SQL does realize it can do this, the query plan Microsoft SQL Server generates does not indicate this).

The group by is handled in the same naive way as any other group by: a hashtable is created (with (a.item,a.sequence_id) as key). This adds an unacceptable amount of overhead to the query. Is there a way to speed things up?

Extra credit:

there is an advanced version of this task that is not required but would be helpful, too: Make the above-mentioned counter explicit. We now want to know tuples of (item, sequence_id_for_type_0, sequence_id_for_type_1, counter_value_at_type_1_entry).

This theoretically increases the task difficulty by a factor of at most 3 (since the counter can only be decremented to either 0, 1 or 2). The theoretical solution does not change much at all. However, the SQL query now has an entry from table b in the group by clause:

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;

Update

I have tried using solving it with the lead() function, and a construct like the following can solve the original problem:

-- 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

Unfortunately, the task has now been extended and I am now looking for a solution to the "extra credit" task. In particular, I care the most about finding the first event with counter_after_type_1_event=0. For this task, we can not use the above trick since we can't put an upper limit on the number of events until we get a type=1 that reaches a particular counter value.

4
  • 3
    Can you add some example data and expected result? What's your SQL Server version, does it support LAG/LEAD?
    – dnoeth
    Feb 10, 2016 at 12:56
  • 1
    Have you examined your query plans?
    – RLF
    Feb 10, 2016 at 13:49
  • Can you post the table DDL with some data and expected results ? Also, post the actual query plan xml (use pastebin and link it here). Have you tried using APPLY operator that would be more efficient. sqlblog.com/blogs/rob_farley/archive/2011/04/13/…
    – Kin Shah
    Feb 10, 2016 at 17:25
  • my SQL Server version is 2014, LAG/LEAD are supported. I have added examples to the question. Feb 11, 2016 at 10:40

2 Answers 2

5

You should consider using LEAD and LAG Analytic Functions and appropriate indices for sorting. I've changed one self-join query with them. Elapsed time was reduced tenfold.

1
  • Thanks, I didn't know about Analytic Functions in SQL before! Feb 11, 2016 at 10:35
1

I don't really follow the examples but based just on:

Each time an event of type=0 happens, a counter increases for the item involved, and each time an event of type=1 happens, it decreases again. The counter must always lie between 0 and 3 (inclusive).

Easier if you just change event_type to -1 and 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;

above find the violations
if you just want the good then flop the where and drop the group by and min
from the question it is not clear what you want to do with this counter
and you don't seem to address the counter in the task

as for the task

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;

As far as theoretical why do a look ahead for EACH row?
Just read the rows and hold the 0 in a buffer
If you get to a 1 then update buffer with 1 information and write out the buffer
If you get to a new item then discard the buffer
This is an easy single pass operation
This would be all of 12 lines of C# with CLR

6
  • Sorry for being unclear: the counter is something you can assume to be true, not something you need to check. I have updated the question accordingly. Feb 11, 2016 at 10:22
  • I have not used analytic functions in SQL before, but from googling this quickly, won't lead(event_type) simply return the event_type of the next entry? I need the next event_type that is 1, which is not the same as checking if the very next entry has event_type=1. However, we can use the fact that the counter exists to surmise that if there is a next event_type=1, it will appear within the next 3 entries. That might be helpful. Feb 11, 2016 at 10:25
  • Could use lead / lag to find first and last but sounds like you did not even test this so will not waste my time
    – paparazzo
    Feb 11, 2016 at 13:42
  • "As far as theoretical why do a look ahead for EACH row? ..." There can be more than one 0 encountered in a row before the next 1 is found. You are correct in that it can be done in one scan, though. We just need to store a list of 0s in a buffer instead of only one. Is it possible to use c++ in SQL Server directly, or do I have to load all the data into a separate c++ program? Feb 12, 2016 at 11:01
  • 1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.