Thread: 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

=?utf-8?Q?Micha=C5=82_K=C5=82eczek?= <michal@kleczek.org> writes:
> I understand extensibility of GIST makes many operators opaque to the planner and it is the “consistent” function
thatcan perform optimisations (or we can come up with some additional mechanism during planning phase). 
> Providing more information to “consistent” function would make it possible to implement optimisations not only for
arrayscan keys but for ranges and others. 

> What we can do is to provide the index attribute number (reduntantly) as option - it is going to work but is somewhat
ugly- especially that this information is already available when calling consistent function. 

While the proposed change is simple enough and wouldn't break
anything, I share Matthias' distaste for it, because the motivation
you've given for it is deeply unsatisfying and indeed troubling.
A GIST consistent function is surely the wrong place to be optimizing
away unnecessary partitions: that consideration is not unique to
GIST indexes (or even to indexscans), much less to particular opclasses.
Moreover, having a consistent function inspect catalog state seems
like a kluge of the first order, not least because there'd be no good
place to cache the lookup results, so you'd be doing them over and
over again.

I like Matthias' suggestion of seeing whether you could use a
planner support function to split up the query by partitions
during planning.

There are bits of what you mentioned that I would gladly take
patches for --- for example, I think the reason GIST lacks SAOP
support is mostly lack of round tuits, not that it'd be a bad
thing.  But it's not clear to me that that alone would help you
much.  The whole design as you've described it seems like multiple
layers of kluges, so that getting rid of any one of them doesn't
really make it not klugy.  (I also have serious doubts about how well
it would perform for you, even with this additional kluge in place.
I don't think that a multidimensional GIST over zillions of rows will
perform very well: the upper tree layers are just not going to be very
selective.)

            regards, tom lane

Hi Tom,

Thanks for looking at it.

> On 24 Jul 2024, at 22:19, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> =?utf-8?Q?Micha=C5=82_K=C5=82eczek?= <michal@kleczek.org> writes:
>> I understand extensibility of GIST makes many operators opaque to the planner and it is the “consistent” function
thatcan perform optimisations (or we can come up with some additional mechanism during planning phase). 
>> Providing more information to “consistent” function would make it possible to implement optimisations not only for
arrayscan keys but for ranges and others. 
>
>> What we can do is to provide the index attribute number (reduntantly) as option - it is going to work but is
somewhatugly - especially that this information is already available when calling consistent function. 
>
> While the proposed change is simple enough and wouldn't break
> anything, I share Matthias' distaste for it, because the motivation
> you've given for it is deeply unsatisfying and indeed troubling.
> A GIST consistent function is surely the wrong place to be optimizing
> away unnecessary partitions: that consideration is not unique to
> GIST indexes (or even to indexscans), much less to particular opclasses.
> Moreover, having a consistent function inspect catalog state seems
> like a kluge of the first order, not least because there'd be no good
> place to cache the lookup results, so you'd be doing them over and
> over again.

Indeed - caching results of such lookups is clumsy.

And I agree the whole thing is hackish.
But in reality I think this is due to fundamental mismatch between
extensibility interface of GIST and the lack of it in partition pruning code.

>
> I like Matthias' suggestion of seeing whether you could use a
> planner support function to split up the query by partitions
> during planning.

You mean implement custom partition pruning algorithm using
query rewriting?

As I’ve written in another message in this thread:
If it was possible to write the query in such a way then the whole
discussion would be moot and I wouldn’t propose this patch :)

>
> There are bits of what you mentioned that I would gladly take
> patches for --- for example, I think the reason GIST lacks SAOP
> support is mostly lack of round tuits, not that it'd be a bad
> thing.  But it's not clear to me that that alone would help you
> much.  The whole design as you've described it seems like multiple
> layers of kluges, so that getting rid of any one of them doesn't
> really make it not klugy.

Kluges are workarounds for lack of two things in GIST:
- missing SAOP support (which I try to simulate using custom operator)
- missing ORDER BY support (for which I posted a draft idea in another patch)

> (I also have serious doubts about how well
> it would perform for you, even with this additional kluge in place.
> I don't think that a multidimensional GIST over zillions of rows will
> perform very well: the upper tree layers are just not going to be very
> selective.)

It work surprisingly well in practice as our performance tests show.
A single multicolumn GIST index is capable of handling most of our queries.

Regards,


—
Michal

On Fri, 22 Mar 2024, 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.
>
> Thanks for suggestion.
>
> I am afraid I don’t understand how it might actually work though:
[...]
> 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.

I would probably (try to) implement something like the following:

- Alter each partition by adding a constraint `CHECK
(hash(partitioncol) % part_modulus = part_remainder)`, to give the
planner the tools to do partition pruning. This solves the partition
pruning part, in userspace. I woudln't be opposed to a fix in
PostgreSQL if done well - hash partition pruning sounds like a niche,
but a valid niche nonetheless.
- Add support function that translates e.g. ||=(array, elem) on the
base table into a list of OR-ed `(hash(partitioncol) % part_modulus =
part_remainder AND col ||= [sublist])`-statements, one for each of the
partitions.
- Make sure there's a planner facility that pushes down OR branches
and removes non-matched qualifiers. Presumably, partition pruning can
already take care of that.

The planner should be able to deduct that each partition has their own
-unique- CHECK constraint, and that this check can't be satisfied by
any other partition and thus is ignored for those other partitions'
scans.

Alternatively, partition the table not using HASH, but using LIST
((hash(partitioncol) % modulus)) - this should enable partition
pruning without creating those manual CHECK constraints. However,
that'd be at the cost of access to hash partitioning-related features,
like different modulos at the same partitioning level.

All in all, this still seems like a very (very) specific optimization,
of which I'm not sure that it is generalizable. However, array
introspection and filtering for SAOP equality checks feel like a
relatively easy (?) push-down optimization in (e.g.) runtime partition
pruning (or planning); isn't that even better patch potential here?


Kind regards,

Matthias van de Meent
Neon (https://neon.tech)