Обсуждение: Alternative SAOP support for GiST

Hi All,

Since it looks like there is not much interest in the patch I will try to provide some background to explain why I
thinkit is needed. 

We are in the process of migration from an old db platform to PostgreSQL.
Our database is around 10TB big and contains around 10 billion financial transactions in a single table.
Each transaction is assigned to an account (column acc_number).

We have partitioned the table BY HASH (acc_number).

A client can query transactions belonging to his accounts using several criteria - among them is te xt search.
Queries are of type TOP N (ie ORDER BY … LIMIT ).

The list of accounts that we are querying is provided as a parameter to the query.

We have decided to use a single Gist index supporting all queries (reasons described in [1]).

There are several problems with Gist usage (but I still think we have no other choice) but the most important is
that we cannot use SAOP in our queries - since Gist does not support it the planner decides to perform Bitmap Scan
which in turn does not support ORDER BY … LIMIT well because requires Sort.

So when we use “= ANY (array of account numbers) … ORDER BY ...” the plan requires reading all records meeting
search criteria and then sort.

As a workaround we have to perform LATERAL joins:

unnest(list of account numbers) AS a(n) LATERAL JOIN (SELECT * FROM … WHERE account_number = a.n ORDER BY … LIMIT …)
ORDERBY … LIMIT … 

It is still bad because requires multiple scans of the same partition if account number hashes are the same.

What we really need is for Gist to support “= ANY (…)”.
As Gist index is extensible in terms of queries it supports it is quite easy to implement an operator class/family with
operator:

||= (text, text[])

that has semantics the same as “= ANY (…)”

With this operator we can write our queries like:

account_number ||= [list of account numbers] AND
account_number = ANY ([list of account numbers]) — redundant for partition pruning as it does not understand ||=

and have optimal plans:

Limit
— Merge Append
—— Index scan of relevant partitions

The problem is that now each partition scan is for the same list of accounts.
The “consistent” function cannot assume anything about contents of the table so it has to check all elements of the
list
and that in turn causes reading unnecessary index pages for accounts not in this partition.

What we need is a way for the “consistent” function to be able to pre-process input query array and remove elements
that are not relevant for this scan. To do that it is necessary to have enough information to read necessary metadata
fromthe catalog. 

The proposed patch addresses this need and seems (to me) largely uncontroversial as it does not break any existing
extensions.

Attached is a patch with consolidated changes (I am pretty new to managing patches so previous two were partial and not
somethingshareable, I am afraid). 

—
Michal

On Tue, 19 Mar 2024 at 17:00, Michał Kłeczek <michal@kleczek.org> wrote:
>
> Hi All,
>
> Since it looks like there is not much interest in the patch I will try to provide some background to explain why I
thinkit is needed. 
>
[...]
> What we really need is for Gist to support “= ANY (…)”.
> As Gist index is extensible in terms of queries it supports it is quite easy to implement an operator class/family
withoperator: 
>
> ||= (text, text[])
>
> that has semantics the same as “= ANY (…)”

I've had a similar idea while working on BRIN, and was planning on
overloading `@>` for @>(anyarray, anyelement) or using a new
`@>>(anyarray, anyelement)` operator. No implementation yet, though.

> With this operator we can write our queries like:
>
> account_number ||= [list of account numbers] AND
> account_number = ANY ([list of account numbers]) — redundant for partition pruning as it does not understand ||=
>
> and have optimal plans:
>
> Limit
> — Merge Append
> —— Index scan of relevant partitions
>
> The problem is that now each partition scan is for the same list of accounts.
> The “consistent” function cannot assume anything about contents of the table so it has to check all elements of the
list
> and that in turn causes reading unnecessary index pages for accounts not in this partition.

You seem to already be using your own operator class, so you may want
to look into CREATE FUNCTION's support_function parameter; which would
handle SupportRequestIndexCondition and/or SupportRequestSimplify.
I suspect a support function that emits multiple clauses that each
apply to only a single partition at a time should get you quite far if
combined with per-partition constraints that filter all but one of
those. Also, at plan-time you can get away with much more than at
runtime.

> What we need is a way for the “consistent” function to be able to pre-process input query array and remove elements
> that are not relevant for this scan. To do that it is necessary to have enough information to read necessary metadata
fromthe catalog. 

> The proposed patch addresses this need and seems (to me) largely uncontroversial as it does not break any existing
extensions.

I don't think "my index operator class will go into the table
definition and check if parts of the scankey are consistent with the
table constraints" is a good reason to expose the index column to
operator classes.
Note that operator classes were built specifically so that they're
independent from their column position. It doens't really make sense
to expose this. Maybe my suggestion up above helps?

Kind regards,

Matthias van de Meent

> On 21 Mar 2024, at 23:42, Matthias van de Meent <boekewurm+postgres@gmail.com> wrote:
>
> On Tue, 19 Mar 2024 at 17:00, Michał Kłeczek <michal@kleczek.org> wrote:
>
>> With this operator we can write our queries like:
>>
>> account_number ||= [list of account numbers] AND
>> account_number = ANY ([list of account numbers]) — redundant for partition pruning as it does not understand ||=
>>
>> and have optimal plans:
>>
>> Limit
>> — Merge Append
>> —— Index scan of relevant partitions
>>
>> The problem is that now each partition scan is for the same list of accounts.
>> The “consistent” function cannot assume anything about contents of the table so it has to check all elements of the
list
>> and that in turn causes reading unnecessary index pages for accounts not in this partition.
>
> You seem to already be using your own operator class, so you may want
> to look into CREATE FUNCTION's support_function parameter; which would
> handle SupportRequestIndexCondition and/or SupportRequestSimplify.
> I suspect a support function that emits multiple clauses that each
> apply to only a single partition at a time should get you quite far if
> combined with per-partition constraints that filter all but one of
> those. Also, at plan-time you can get away with much more than at
> runtime.

Thanks for suggestion.

I am afraid I don’t understand how it might actually work though:

1) I think planning time is too early for us - we are heavily using planner_mode = force_generic_plan:
- we have many partitions and planning times started to dominate execution time
- generic plans are not worse than specialised

2) I am not sure how I could transform
"col ||= [array]" to multiple criteria to make sure it works well with partition pruning and planner.

It looks like what you are suggesting is to generate something like:
(part_condition AND col ||= [subarray1]) OR (part_condition AND col ||= [subarray2])
and hope the planner would generate proper Merge Append node (which I doubt would happen and planner would generate
Bitmapscan due to lack of OR support in Gist). 
What’s more - there is no part_condition for hash partitions.

>
>> What we need is a way for the “consistent” function to be able to pre-process input query array and remove elements
>> that are not relevant for this scan. To do that it is necessary to have enough information to read necessary
metadatafrom the catalog. 
>
>> The proposed patch addresses this need and seems (to me) largely uncontroversial as it does not break any existing
extensions.
>
> I don't think "my index operator class will go into the table
> definition and check if parts of the scankey are consistent with the
> table constraints" is a good reason to expose the index column to
> operator classes.

Quite possibly but I still don’t see any other way to do that TBH.

—
Michal

> On 22 Mar 2024, at 01:29, Michał Kłeczek <michal@kleczek.org> wrote:
>
> 
>
>> On 21 Mar 2024, at 23:42, Matthias van de Meent <boekewurm+postgres@gmail.com> wrote:
>>
>>> On Tue, 19 Mar 2024 at 17:00, Michał Kłeczek <michal@kleczek.org> wrote:
>>>
>>> With this operator we can write our queries like:
>>>
>>> account_number ||= [list of account numbers] AND
>>> account_number = ANY ([list of account numbers]) — redundant for partition pruning as it does not understand ||=
>>>
>>> and have optimal plans:
>>>
>>> Limit
>>> — Merge Append
>>> —— Index scan of relevant partitions
>>>
>>> The problem is that now each partition scan is for the same list of accounts.
>>> The “consistent” function cannot assume anything about contents of the table so it has to check all elements of the
list
>>> and that in turn causes reading unnecessary index pages for accounts not in this partition.
>>
>> You seem to already be using your own operator class, so you may want
>> to look into CREATE FUNCTION's support_function parameter; which would
>> handle SupportRequestIndexCondition and/or SupportRequestSimplify.
>> I suspect a support function that emits multiple clauses that each
>> apply to only a single partition at a time should get you quite far if
>> combined with per-partition constraints that filter all but one of
>> those. Also, at plan-time you can get away with much more than at
>> runtime.

Thinking about it some more - the suggestion goes backwards - ie. there must have been some deep misunderstanding:

If I was able to write my query such that the planner generates optimal plan, I would not implement the custom operator
inthe first place. 

And this need of custom operator and operator class triggered the proposal in turn.

—
Michal