Parallel filter execution

[tyt2y3]

Consider the following query

SELECT A.*, B.* from A, B WHERE A.a LIKE '%a%' AND B.b LIKE '%b%'

Can we exectue the two filter conditions in parallel?

A traditional query planner would try to figure out which condition is cheaper and apply it first

For example, given

SELECT * from user WHERE id = 1 AND name LIKE '%john%'

It's obvious that the equal condition is cheaper (especially if the id column is indexed), so the order would be:

input -> [WHERE id = 1] -> [WHERE name LIKE '%john%'] -> output

But in cases where the filter conditions have different sources and it's not possible to determine which is cheaper, why not exectue them in parallel and see which completes first?

Consider the following query

SELECT * from user WHERE first LIKE '%john%' AND last LIKE '%wick%'

(the reason where two %% is used is because it is impossible to utilize an index in this case, but it actually can be any scan operator)

I imagine the following algorithm:

1. divide the rows into two halves
2. the first condition filters the first half, the second condition filters the second half
3. the output of the first half would be fed into the second filter, while the output of the second half would be fed into the first filter
4. the two output list will be consolidated

The trick is to load balance the two processes.
If the input queue of one processor is empty, we will 'grab more' from the input queue of the other.
Since we are doing an AND operation, the rows rejected by the faster filter will not be piped into the slower filter, making the resultant query execution twice at fast at best, and equivalent to sequential filtering at worst.
But the benefit is we do not have to determine beforehand.

[tyt2y3]

Sorry for my bad diagram

[joaoh82]

Interesting! I like this idea. Basically applying Divide & Conquer to querying database.

I tried to make your diagram a bit clearer and added a merge step. What do you think @tyt2y3 ?

I also numbered the arrows to represent each step in the algorithm.

[tyt2y3]

Nice! It looks much better. I am still unsure how to generalize this concept to N filters though.

[joaoh82]

How about if we divide the rows based on total number of pages utilized? We could have an arbitrary number of page for each piece.

[tyt2y3]

So I have a better idea now.

Say we want to parallelize 4 AND filters A, B, C, D

We would then have (conceptually) 4 pipelines where we cycle their order and put each first

1. A -> B -> C -> D
2. B -> C -> D -> A
3. C -> D -> A -> B
4. D -> A -> B -> C

They are load-balanced so the ones running faster will process more items.

This is a dynamic process, so if one pipeline is experiencing a slow down (e.g. page fetch) the others can still be busy running.

At the end, there are 3 rules:

1. an 'accepted' item has to pass through all filters
2. a 'rejected' item only has to be rejected by one
3. evaluation will only be done at most once per item by each filter

[tyt2y3]

The advantage over parallizing the same pipeline (A -> B -> C -> D) is that we don't have to guess beforehand the optimal ordering.
Second, each row is handled by only one filter at any given time, so it only has to be Send but not Sync (in Rust terms).