Re: Resjunk sort columns, Heikki's index-only quals patch, and bug #5000

On Mon, Sep 14, 2009 at 5:41 AM, Heikki Linnakangas
<heikki(dot)linnakangas(at)enterprisedb(dot)com> wrote:
> Heikki Linnakangas wrote:
>> Tom Lane wrote:
>>> It strikes me that in the cases where it wouldn't be necessary to
>>> compute junk sort-key columns, it would be because we were scanning an
>>> index that includes those values.  So if the plan were set up to pull
>>> those values from the index and return them, then we'd not have to add
>>> this extra complexity to grouping_planner --- the argument that it's not
>>> worth it to get rid of the junk columns comes back into play.  Moreover,
>>> such an ability would also mean that if the user *does* ask for the
>>> sort column value as output (ie it's not resjunk), we can still satisfy
>>> the query from the index without recomputing the expensive function.
>>>
>>> So this is where we come to the connection to Heikki's index-only-quals
>>> patch.  As submitted, that code is only able to use an index column in
>>> a scan qual, it's not able to return it as part of the scan result.
>>> This example makes it clear that that definition is missing a large
>>> part of the potential benefit of an index value extraction capability.
>>>
>>> To be able to do anything along that line would require some more work
>>> in the executor and a *lot* more work in the planner, and I'm honestly
>>> not sure what the planner part of it would look like.
>>
>> I think we should separate the Heap Fetch operation from the IndexScan.
>
> I've been hacking on that approach. It's quite unfinished, but before I
> spend any more time on it, I'd like to get some feedback on the overall
> design.
>
> The attached patch can create plans where quals are checked and joins
> are performed using values from indexes only, and the heap tuples are
> fetched only for matching rows. Passes regression tests, but code is
> quite ugly at points. Cost estimation is bogus. The patch builds on the
> indexam-api-changes patch I posted earlier, which is also attached. I
> haven't yet done the changes to that patch that were discussed.
>
> I haven't done any performance testing. The overhead of an extra
> executor node for each index scan could slow down simple queries, we
> might need to compensate that somehow, maybe reintroduce a fastpath
> combined IndexScan+HeapFetch node.  I'm also afraid the extra work I've
> pushed to the stage where Paths are constructed could slow down planning
> quite a bit if you have a lot of indexes.
>
>
> Path nodes now carry a targetlist. That's because when you have a path like:
>
>  HeapFetch
>   -> Join
>     ...
>
> You won't have all the columns of the join rel available at the join
> node yet, because they will be fetched in the HeapFetch node above. The
> targetlist in Path nodes reflect that, and the targetlist of the final
> Plan nodes are created from the targetlists in the Path nodes instead of
> the ones in RelOptInfos.
>
> Per earlier discussion, I changed the way index tuple fetching works in
> B-tree, so that it can now be relied on. Matching index tuples are
> copied to backend-local memory when the scan steps on a page.
>
> Var nodes that refer to index columns (indexquals and the new index-only
> filters) now have a new field, varindexno, set. While we could've
> continued with the old representation, now that we have more expressions
> that refer to index vars instead of heap vars, this makes debugging easier.

Hi, I'm reviewing this patch for the 2009-09 CommitFest.

It doesn't seem to compile.

make[4]: Entering directory `/home/rhaas/pgsql-git/src/backend/optimizer/path'
gcc -O2 -Wall -Wmissing-prototypes -Wpointer-arith
-Wdeclaration-after-statement -Wendif-labels -fno-strict-aliasing
-fwrapv -g -I../../../../src/include -D_GNU_SOURCE
-I/usr/include/libxml2 -c -o joinpath.o joinpath.c -MMD -MP -MF
.deps/joinpath.Po
joinpath.c: In function ‘can_bubbleup’:
joinpath.c:170: warning: implicit declaration of function ‘make_indexonly_expr’
joinpath.c: In function ‘bubbleup_step’:
joinpath.c:187: warning: implicit declaration of function ‘makeVar’
joinpath.c:188: error: ‘SelfItemPointerAttributeNumber’ undeclared
(first use in this function)
joinpath.c:188: error: (Each undeclared identifier is reported only once
joinpath.c:188: error: for each function it appears in.)
joinpath.c:189: error: ‘TIDOID’ undeclared (first use in this function)
joinpath.c:189: warning: assignment makes pointer from integer without a cast

Actually, before I even tried compiling this, I was looking through
the joinpath.c changes, since that is an area of the code with which I
have some familiarity. As I'm sure you're aware, the lack of
commenting makes it quite difficult to understand what this is trying
to do, and the functions are poorly named. It isn't self-explanatory
what "bubbling up" means, even in the limited context of joinpath.c.

Leaving that aside, I think that the approach here is likely wrong;
the decision about when to perform a heap fetch doesn't seem to be
based on cost, which I think it needs to be. Consider A IJ B, with
the scan over A implemented as an index scan. It seems to me that if
the join selectivity is < 1, then assuming there's a choice, we
probably want to join A to B and then do the heap fetches against A
afterwards. But if the join selectivity is > 1 (consider, for
example, a cross join), we probably want to do the heap fetches first.

Am I right to think that the heap fetch node is not optional? i.e.
even if only columns in the index are ever used, we need to make sure
that a heap fetch node gets inserted to check visibility. Is that
right?

I also think that the use of the term index-only quals is misleading.
It seemed good when you first posted to -hackers about it, but looking
at the patch, it means we have both index quals and index-only quals,
and it seems like that might not be the greatest naming. Maybe we
could call them index-tuple quals or index-evaluated quals or
something.

I'll try to review this a bit more later in the week - need to get
some sleep now.

...Robert