Pushing down Distinct Node

[Michael Alexeev]

Hi All,

I have a couple of questions
1. Currently only single distinct column is allowed but plan itself
permits multiple ones
DISTINCT
DISTINCT
SEQUENTIAL SCAN of "LOG"
Should I account for this case while pushing down distinct nodes? Or
exception should be thrown if more then one distinct nodes are
encountered similar to the handleDistinct code?
2. If we do allow, is it possible for a distinct node to have more
then one child and if so, can it be a mixture of distinct and some
other nodes?
DISTINCT
DISTINCT
SEQUENTIAL SCAN of "LOG"
DISTINCT
SEQUENTIAL SCAN of "LOG"

Or
DISTINCT
DISTINCT
SEQUENTIAL SCAN of "LOG"
SEQUENTIAL SCAN of "LOG"

It shouldn’t be a big deal to accommodate for the first plan, but I am
not sure how to handle the next two.

Thanks,
Mike

[Paul Martel]

Hi, Mike.

Can you send a simple example query so that I am clear on what you mean by multiple distinct columns?

Thanks,
--paul

[Michael Alexeev]

Hi Paul, sorry, I meant multiple columns with the distinct keyword.
Something like

select distinct a,b from t;

where a and b are columns in t.

Mike

[Paul Martel]

Mike,

The DISTINCT processing in this case has to happen on the combinations of column values from the same row/scan, so the structure of the plan does not change vs. the single column case.

BTW, having looked at the description of ENG 2503/2504, I'm not sure that it's as simple as a push-down issue, though the push-down is a good first step.
I am new to the code and haven't had a chance to study the DISTINCT implementation, but I suspect that there may be ways to tune it to better suit the case of low-cardinality columns. I'm hoping to look deeper into this in the next few days.

--paul

[John Hugg]

I spoke with Michael last night and he's going to try to make the distinct node executor work with subsets of tuples, rather than single rows.

[Michael Alexeev]

Paul,

On Fri, Mar 16, 2012 at 10:17 PM, Paul Martel <pma...@voltdb.com> wrote:

Mike,

The DISTINCT processing in this case has to happen on the combinations of column values from the same row/scan, so the structure of the plan does not change vs. the single column case.

BTW, having looked at the description of ENG 2503/2504, I'm not sure that it's as simple as a push-down issue, though the push-down is a good first step.
I am new to the code and haven't had a chance to study the DISTINCT implementation, but I suspect that there may be ways to tune it to better suit the case of low-cardinality columns. I'm hoping to look deeper into this in the next few days.

Yes, I am aware of this. The out-of-memory exception happens withing the sequential scan executor p_execute call, way ahead of the distinct executor call. I guess, the only way to avoid it is to eliminate intermediate temp table as Ryan suggested earlier. The condition for that is the absence of predicate and inline nodes for the scan node.In this particular case, the predicate is NULL but there is an inline node and this is why the copy is taken. I am trying to figure out where this inline node is coming from.

Please let me know if you have any suggestion.

Mike

[Michael Alexeev]

On Sat, Mar 17, 2012 at 5:58 PM, John Hugg <jh...@voltdb.com> wrote:

I spoke with Michael last night and he's going to try to make the distinct node executor work with subsets of tuples, rather than single rows.

John, thank you very much. It was very helpful. My plan is to do one step at a time. First - push down DISTINCT for a single column and then try to make it for multiple columns.

Mike

[Paul Martel]

All,

I see now that I made my comments about other performance issues with DISTINCT before reading Ryan's comments on the other (ENG-2503) thread. So, I think I'm just agreeing with him and with Mike's re-cap that the DISTINCT processing could be inlined with the scan rather than requiring a copy.

I would add the following observation:

Though not a major issue in the low-cardinality case, we could leverage the ordering established in the std:set of values calculated in distinctexecutor.cpp to produce the values in sorted order, improving determinism and potentially allowing a much-reduced final DISTINCT phase that simply merge-sorted the pre-sorted results from each node -- weeding out successive duplicates in cases when they are possible -- i.e. when the partition key is not included in the column list.

Ideally, any "order by" clause would also be taken into account. The std::set's ordering function could optionally use the requested ordering (possibly extended to include all columns) for its comparison operator, saving an additional sort (copy).

But this all seems like it could be layered on afterwards as a follow-on effort to support high-cardinality DISTINCTs.

--paul