Re: Index Skip Scan (new UniqueKeys)

On 01/12/2020 22:21, Dmitry Dolgov wrote:
>> On Mon, Nov 30, 2020 at 04:42:20PM +0200, Heikki Linnakangas wrote:
>>
>> I had a quick look at this patch. I haven't been following this thread, so
>> sorry if I'm repeating old arguments, but here we go:
>
> Thanks!
>
>> - I'm surprised you need a new index AM function (amskip) for this. Can't
>> you just restart the scan with index_rescan()? The btree AM can check if the
>> new keys are on the same page, and optimize the rescan accordingly, like
>> amskip does. That would speed up e.g. nested loop scans too, where the keys
>> just happen to be clustered.
>
> An interesting point. At the moment I'm not sure whether it's possible
> to implement skipping via index_rescan or not, need to take a look. But
> checking if the new keys are on the same page would introduce some
> overhead I guess, wouldn't it be too invasive to add it into already
> existing btree AM?

I think it'll be OK. But if it's not, you could add a hint argument to
index_rescan() to hint the index AM that the new key is known to be
greater than the previous key.

>> - Does this optimization apply to bitmap index scans?
>
> No, from what I understand it doesn't.

Would it be hard to add? Don't need to solve everything in the first
version of this, but I think in principle you could do the same
optimization for bitmap index scans, so if the current API can't do it,
that's maybe an indication that the API isn't quite right.

>> - This logic in build_index_paths() is not correct:
>>
>>> + /*
>>> + * Skip scan is not supported when there are qual conditions, which are not
>>> + * covered by index. The reason for that is that those conditions are
>>> + * evaluated later, already after skipping was applied.
>>> + *
>>> + * TODO: This implementation is too restrictive, and doesn't allow e.g.
>>> + * index expressions. For that we need to examine index_clauses too.
>>> + */
>>> + if (root->parse->jointree != NULL)
>>> + {
>>> + ListCell *lc;
>>> +
>>> + foreach(lc, (List *)root->parse->jointree->quals)
>>> + {
>>> + Node *expr, *qual = (Node *) lfirst(lc);
>>> + Var *var;
>>> + bool found = false;
>>> +
>>> + if (!is_opclause(qual))
>>> + {
>>> + not_empty_qual = true;
>>> + break;
>>> + }
>>> +
>>> + expr = get_leftop(qual);
>>> +
>>> + if (!IsA(expr, Var))
>>> + {
>>> + not_empty_qual = true;
>>> + break;
>>> + }
>>> +
>>> + var = (Var *) expr;
>>> +
>>> + for (int i = 0; i < index->ncolumns; i++)
>>> + {
>>> + if (index->indexkeys[i] == var->varattno)
>>> + {
>>> + found = true;
>>> + break;
>>> + }
>>> + }
>>> +
>>> + if (!found)
>>> + {
>>> + not_empty_qual = true;
>>> + break;
>>> + }
>>> + }
>>> + }
>>
>> If you care whether the qual is evaluated by the index AM or not, you need
>> to also check that the operator is indexable. Attached is a query that
>> demonstrates that problem.
>> ...
>> Also, you should probably check that the index quals are in the operator
>> family as that used for the DISTINCT.
>
> Yes, good point, will change this in the next version.
>
>> I'm actually a bit confused why we need this condition. The IndexScan
>> executor node should call amskip() only after checking the additional quals,
>> no?
>
> This part I don't quite get, what exactly you mean by checking the
> additional quals in the executor node? But at the end of the day this
> condition was implemented exactly to address the described issue, which
> was found later and added to the tests.

As I understand this, the executor logic goes like this:

query: SELECT DISTINCT ON (a, b) a, b FROM foo where c like '%y%' and a
like 'a%' and b = 'b';

1. Call index_beginscan, keys: a >= 'a', b = 'b'

2. Call index_getnext, which returns first row to the Index Scan node

3. Evaluates the qual "c like '%y%'" on the tuple. If it's false, goto
step 2 to get next tuple.

4. Return tuple to parent node

5. index_amskip(), to the next tuple with a > 'a'. Goto 2.

The logic should work fine, even if there are quals that are not
indexable, like "c like '%y'" in the above example. So why doesn't it
work? What am I missing?

- Heikki