Re: Hash support for grouping sets

On 2017-03-23 05:09:46 +0000, Andrew Gierth wrote:
> >>>>> "Andres" == Andres Freund <andres(at)anarazel(dot)de> writes:
>
> >> - Assert(newphase == 0 || newphase == aggstate->current_phase + 1);
> >> + Assert(newphase <= 1 || newphase == aggstate->current_phase + 1);
>
> Andres> I think this somewhere in the file header needs an expanded
> Andres> explanation about what these "special" phases mean.
>
> I could move most of the block comment for ExecInitAgg up into the file
> header; would that be better?

Yes, I think so.

> >> + values = palloc((1 + max_weight) * sizeof(double));
> >> + sets = palloc((1 + max_weight) * sizeof(Bitmapset *));
>
> Andres> We usually cast the result of palloc.
>
> Rough count in the backend has ~400 without casts to ~1350 with, so this
> doesn't seem to have been consistently enforced.

Yea, but we're still trying.

> >> + RelOptInfo *grouped_rel,
> >> + Path *path,
> >> + bool is_sorted,
> >> + bool can_hash,
> >> + PathTarget *target,
> >> + grouping_sets_data *gd,
> >> + const AggClauseCosts *agg_costs,
> >> + double dNumGroups)
> >> +{
> >> + Query *parse = root->parse;
> >> +
> >> + /*
> >> + * If we're not being offered sorted input, then only consider plans that
> >> + * can be done entirely by hashing.
> >> + *
> >> + * We can hash everything if it looks like it'll fit in work_mem. But if
> >> + * the input is actually sorted despite not being advertised as such, we
> >> + * prefer to make use of that in order to use less memory.
> >> + * If none of the grouping sets are sortable, then ignore the work_mem
> >> + * limit and generate a path anyway, since otherwise we'll just fail.
> >> + */
> >> + if (!is_sorted)
> >> + {
> >> + List *new_rollups = NIL;
> >> + RollupData *unhashable_rollup = NULL;
> >> + List *sets_data;
> >> + List *empty_sets_data = NIL;
> >> + List *empty_sets = NIL;
> >> + ListCell *lc;
> >> + ListCell *l_start = list_head(gd->rollups);
> >> + AggStrategy strat = AGG_HASHED;
> >> + Size hashsize;
> >> + double exclude_groups = 0.0;
> >> +
> >> + Assert(can_hash);
> >> +
> >> + if (pathkeys_contained_in(root->group_pathkeys, path->pathkeys))
> >> + {
> >> + unhashable_rollup = lfirst(l_start);
>
> Andres> a) cast result of lfirst/lnext/whatnot.
>
> casting lfirst is defensible (and only about 10% of existing uses don't
> cast it), but why would you ever cast the result of lnext?

Obviously lnext is bogus, was thinking of linitial...

> >> + if (can_hash && gd->any_hashable)
> >> + {
> >> + List *rollups = NIL;
> >> + List *hash_sets = list_copy(gd->unsortable_sets);
> >> + double availspace = (work_mem * 1024.0);
>
> Andres> Why the parens, and why the .0?
>
> The .0 is because the * should be done as a double, not an int.

I was just missing why - but now that I've not already been awake for 20
hours, 8 of those crammed into a plane, it's obviously beneficial
because of overflow concerns.

> Andres> I think you need a higher level explanation of how you're
> Andres> mapping the work_mem issue to knapsack somewhere.
>
> The general overview ("work_mem is the knapsack size, and we need to
> figure out how best to pack it with hashtables"), or the specific issue
> of the scale factor for discrete chunking of the size?

The general overview - the scaling thing doesn't seem that important to
understand in detail, to understand the approach. Briefly explaining
what we're trying to minimize (sort steps), what the constraint is
(memory), that the problem is representable as the classic "knapsack
problem".

> Andres> Hm. So we're solely optimizing for the number of sorts, rather
> Andres> the cost of the sorts. Probably an acceptable tradeoff.
>
> The existing cost model for sorts doesn't actually seem to help us here;
> all of our sorts sort the same data, just with different comparison
> columns, but cost_sort doesn't actually account for that (all its
> callers except the CLUSTER planning code pass in 0.0 for
> comparison_cost).
>
> If the sort costs were correct, we could compute a "value" for each
> rollup that reflected the cost difference between the sort+unique
> comparisons for it, and the hash functions that would be called if we
> hashed instead; and just pass that to the knapsack function.

That'd indeed be desirable - but I think we can punt on that for now.

Greetings,

Andres Freund