Re: Index filter instead of index condition w/ IN / ANY queries above certain set size

[Danny Shemesh]

Hey Laurenz, Tom - thanks again !

> that it is cheaper to use the index that supports the ORDER BY
Thing is, that both queries use the exact same index (idx_hashes), but one
uses it w/ the filter and one does not.

> This doesn't match up terribly well with the table definition you showed
before
Yeah.. it was a bit hard to reproduce exactly, but the fiddle does showcase
that there's some threshold to the ANY set-size
where it stops using the column in the index condition, and moves it to the
filter step - I thought it might originate
from similar reasons.

> but I wonder whether tidh is a low-order index column.
The index indeed uses tidh as a low order column, and it's better to have
it the other way around -
currently, it's: (tid, pidh, tidh) - where (tid, tidh, pidh) would've
probably worked better.

We've already optimized the query itself - but for pure understanding of
the planner decision here,
I'd really still like to understand, if possible, the difference between
ANY and IN,
and why, even though the column order isn't optimal - one plan still
successfully uses the index more efficiently than another.

Any idea where I could zone-in in the source code to look for hints, maybe ?

Appreciate it !
Danny

On Wed, Nov 23, 2022 at 4:29 PM Tom Lane  wrote:

> Danny Shemesh  writes:
> > ->  Index Only Scan using
> > idx_hashes on refs  (cost=0.56..722735.47 rows=33715 width=16) (actual
> > time=1727.208..1727.208 rows=1 loops=1)
> >   Index Cond: (tid =
> > '13371337-1337-1337-1337-133713371337'::uuid)
> > *  Filter: (tidh = ANY
> > ('{13391339-1339-1339-1339-133913391339}'::uuid[]))<<<<<<<<<<<<<<<-
> > Note this line*  Rows Removed
> > by Filter: 109087
> >   Heap Fetches: 16976
> >   Buffers: shared hit=13051
> > read=14561
> >   I/O Timings: read=53405.294
>
> This doesn't match up terribly well with the table definition
> you showed before, but I wonder whether tidh is a low-order
> index column.  If you need to optimize this specific shape
> of query you need to pay attention to the index column order, per
>
> https://www.postgresql.org/docs/current/indexes-multicolumn.html
>
> That is, tid and tidh need to be the first two index columns.
>
> regards, tom lane
>

Re: Index filter instead of index condition w/ IN / ANY queries above certain set size

[Danny Shemesh]

D
(tidh = '13391339-1339-1339-1339-133913391339'::uuid))**
 <<<<<<<<<<<<<<<- Note this line*
  Heap Fetches: 10
  Buffers: shared hit=90020
read=164
  I/O Timings: read=151.151
Planning:
  Buffers: shared hit=8
Planning Time: 0.505 ms
Execution Time: 297.948 ms


I can also note that if I change the IN expression to compare on 2 or more
items - it is converted to an ANY expression,
and the previous plan is chosen again.

Thanks a ton !
Danny

On Wed, Nov 23, 2022 at 11:22 AM Laurenz Albe 
wrote:

> On Wed, 2022-11-23 at 10:49 +0200, Danny Shemesh wrote:
> > I'm trying to understand when the planner decides to use an index
> condition vs an index filter
>
> I am not sure what you mean by "index filter".
>
> If you could send the result of EXPLAIN (ANALYZE, BUFFERS) for the queries,
> that would be most useful.
>
> Yours,
> Laurenz Albe
>

Index filter instead of index condition w/ IN / ANY queries above certain set size

[Danny Shemesh]

Hey everyone,

I'm trying to understand when the planner decides to use an index condition
vs an index filter, specifically for x IN / = ANY {set}, and if we can tune
some parameters to move it between these plans.

We have two tables and a query similar to the following fiddle:
https://www.db-fiddle.com/f/g9tZvVk65RRg3XRskQZpXK/1

In the fiddle - we see that the planner uses an index condition up to a set
of 3 elements, and fallbacks to use an index filter when the set has 4 or
more elements;

In our case - which I couldn't easily replicate in the fiddle - the
threshold is a single element - that is, a single element uses the index
condition, and 2 or more elements use an index filter, and the latter is
much slower on our data set.

This ^ also causes a side effect, where IN queries of a single element are
'flattened' to a single element comparison (x = y), but ANY queries aren't
flattened, and are still being compared against a set of one element;
This flattening is what makes our IN queries use the index condition, but
the = ANY(array[one-element]) to use the index filter.

I've tried playing w/ the random_page_cost, create extended statistics and
tune other sys parameters - but it didn't nudge the planner the other way;

Would appreciate if anyone could shed some light on this behavior (code
refs are also welcomed), and if there's any way we could help the planner
move between the plans.


Thanks a ton - appreciate your time !
Danny

Expr. extended stats are skipped with equality operator

[Danny Shemesh]

Hey all !

I'm on a quest to help the planner (on pg14) use the best of several
partial, expressional indices we have on some large tables (few TBs in
size, billions of records).

As we know, stats for expressions in partial indices aren't gathered by
default - so I'm tinkering with expressional extended stats to cover for
those.

I've tackled two interesting points there:
1. Seems like expressional stats involving the equality operator are
skipped or mismatched (fiddle
)
Let's take the following naive example:




*create table t1 (x integer[]);insert into t1 select array[1]::integer[]
from generate_series(1, 10, 1);create statistics s1 on (x[1] = 1) from
t1;analyze t1;*
*explain analyze select * from t1 where x[1] = 1;*
*> Seq Scan on t1 (cost=0.00..1986.00 rows=500 width=29) (actual
time=0.009..36.035 rows=10 loops=1)*

Now, of course one can just create the stat on x[1] directly in this case,
but I have a more complex use case where an equality operator is
beneficial;
should the above case be supported ? feels like I'm just missing something
fundamental.

2. Less important, just a minor note - feel free to ignore - although the
eq. operator above seems to be skipped when matching the ext. stats, I can
work around this by using a CASE expression (fiddle
);
Building on the above example, we can:
*create statistics s2 on (case x[1] when 1 then true else false end) from
t1;*
*explain analyze select * from t1 where (case x[1] when 1 then true else
false end*
*>  Seq Scan on t1 (cost=0.00..1986.00 rows=10 width=25) (actual
time=0.011..33.721 rows=10 loops=1)*

What's a bit problematic here, though, is that if we mix other dependent
columns to the extended stat, and specifically if we create an mcv,
queries involving the CASE expression throw with `error: unknown clause
type 130`, where clause type == T_CaseExpr.

The second point for me would be that I've found it a bit non intuitive
that creating an extended statistic can fail queries at query time; it
makes sense that the mcv wouldn't work for case expressions, but it
might've been a bit clearer to:

a. Fail this at statistic creation time, potentially, or
b. Convert the type numeric in the above error to its text representation,
if we can extract it out at runtime somehow -
I couldn't find a mapping of clause type numerics to their names, and as
the node tags are generated at compile time, it could be build-dependent
and a bit hard to track down if one doesn't control the build flags


Thanks a ton for your help - appreciate your time,
Danny

Re: Index only scans for expressional indices when querying for the expression

[Danny Shemesh]

A-ha, interesting !

I think we have some specific use cases where it'd be worth the overhead,
I'd need to measure it, though;

Do you think there'd be room to accept a contribution for such
functionality with a disabled-by-default pg setting,
or are you skeptical it would ever be worth the trade-off ?

Thanks again,
Danny

On Thu, Aug 4, 2022 at 4:38 PM Tom Lane  wrote:

> Danny Shemesh  writes:
> > That is of course correct, but what I mean is that, I think that if one
> > would explicitly query f(x), and never for x directly, it would've been
> > theoretically possible to say that the index is covering for every f(x),
> > wouldn't it ?
>
> Theoretically, yeah, but we don't support that: an index-only scan
> will only be considered if x itself is available from the index.
> There are a couple of reasons for that, but the main one is that
> detecting whether an index matches the query would be far more expensive
> if it had to consider expression subtrees not just the base Vars.
>
> regards, tom lane
>

Re: Index only scans for expressional indices when querying for the expression

[Danny Shemesh]

Hey David - thanks for the prompt response !

That is of course correct, but what I mean is that, I think that if one
would explicitly query f(x), and never for x directly, it would've been
theoretically possible to say that the index is covering for every f(x),
wouldn't it ?

Or in other words, if one only ever queries f(x), and the only available
index is on f(x), then the index will hold all f(x) values
and would never need to reverse engineer the value of x to answer such a
specific query.

Danny

On Thu, Aug 4, 2022 at 3:28 PM David G. Johnston 
wrote:

> On Thursday, August 4, 2022, Danny Shemesh  wrote:
>>
>> I believe the expressional index in itself could've been considered as
>> covering, when querying for the expression explicitly.
>>
>
> This belief is wrong.  When storing f(x) there is no way to recover the
> value of x.
>
> David J.
>
>

Index only scans for expressional indices when querying for the expression

[Danny Shemesh]

Hello everyone,

Quick question here about index-only scans and expressional indices, tested
on postgres <= 14,
Say I have a column, and an expressional index on said column (fiddle
) - e.g.

create table t1 (x text);
create index idx_upper on t1 (upper(x));

I see that even if I query for upper(x) in itself, I won't achieve an
index-only scan without creating a covering index that includes the
manipulated field:
create index idx_upper_covering on t1 (upper(x)) include (x);

I wonder if it would've been possible to have an index-only scan for
similar cases without having to include the base column ?
I believe the expressional index in itself could've been considered as
covering, when querying for the expression explicitly.

The thing is, indices with include clauses do not support page
deduplication, which causes the size of the index to bloat in our case,
over 20x in size at times.
Also, it could've been beneficial when creating indices on complex types,
say - indexing the first element on an array, or a specific nested element
of a jsonb column, et-al.

Appreciate your time !
Danny

Re: Extended multivariate statistics are ignored (potentially related to high null fraction, not sure)

[Danny Shemesh]

Hey bruce, thanks for the prompt reply !

It reproduces in 12.11 and 13.7, we use a managed offering that is yet to
include pg 14,
so sadly I can't try expressional extended statistics as of yet, nor can I
attach gdb to the process
to debug the flow.

If any other directions come to mind, I'd really appreciate hearing them.
Thanks again !

On Wed, Jun 1, 2022 at 11:08 PM Bruce Momjian  wrote:

> On Wed, Jun  1, 2022 at 07:28:58PM +0300, Danny Shemesh wrote:
> > Hey everyone,
> >
> > I'm working on improving gathered statistics on several large tables
> (2TB /
> > 500M records);
> > I've created extended stats on correlated columns, ran analyze, compared
> the
> > pre and post explains, and it seems as though the extended statistics are
> > ignored -
> > the estimation doesn't change much, and I can accurately derive the est.
> rows
> > from multiplying the single-column freqs from pg_stats with the supplied
> > values.
> >
> >
> > Context:
> > - pg 12.8
>
> You should be on the most recent version of 12.X, and I do see some
> extended statistics change in the later releases you are missing.
>
> --
>   Bruce Momjian  https://momjian.us
>   EDB  https://enterprisedb.com
>
>   Indecision is a decision.  Inaction is an action.  Mark Batterson
>
>

Extended multivariate statistics are ignored (potentially related to high null fraction, not sure)

[Danny Shemesh]

Hey everyone,

I'm working on improving gathered statistics on several large tables (2TB /
500M records);
I've created extended stats on correlated columns, ran analyze, compared
the pre and post explains, and it seems as though the extended statistics
are ignored -
the estimation doesn't change much, and I can accurately derive the est.
rows from multiplying the single-column freqs from pg_stats with the
supplied values.


Context:
- pg 12.8
- relation w/ three columns of interest - user (text), row_type (text),
deleted_at (timestamp).
- different users have different distributions for row_type
- deleted_at is set if said record is marked for deletion - stays marked
for a long retention period, around 95% of the rows have a value, and
around 5% have null
- we query and operate on the 5% of records with deleted_at = null, most of
our indexes are partial on that as well

I'll give a simplified example with two users, one being extremely dominant
w/ 99.9% of the data; the next holds much less, but still accounts to
around 200k rows.

>From pg_stats:
attname| user
n_distinct | 2.0
most_common_vals   | {A,B}
most_common_freqs  | [0.9996333, 0.0003667]

attname| row_type
n_distinct | 4.0
most_common_vals   | {A,B}
most_common_freqs  | [0.9968, 0.002534]

attname| deleted_at
n_distinct | 20761.0
null_frac  | 0.04313


Querying before extended stats:


*$> explain select 1 from my_rel where user ='B and row_type = 'A' and
deleted_at is null;Index Only Scan using
idx_user_row_type_where_deleted_at_is_null on my_rel  (cost=0.69..2851.78
rows=8213 width=4)Index Cond: ((user = 'B') AND (row_type = 'B'))*

The number is derived from:
reltuples*user_b_freq*row_type_a_freq*deleted_at_null_frac
= 520982816*0.0003667*0.9968*0.04313 = 8213.26586

When explain-analyzing, I get - *(actual time=0.051..72.503 rows=174954
loops=1)*
So in this specific case, the estimation is off by around 20x (note that
this is a simplified case just to showcase the symptom).

I then create extended stats - I've tried to add them on all three columns
in all combinations, and in pairs in all combinations - all leading to the
same result,
I'll only showcase the three column variant for brevity:

*$> create statistics s1 on user, row_type, deleted_at from my_rel;*
*$> analyze my_rel;*
*$> explain select 1 from my_rel where user ='B' and row_type = 'A' and
deleted_at is null;*
*Index Only Scan using **idx_user_row_type_where_deleted_at_is_null** on
my_rel  (cost=0.69..1560.01 rows=4491 width=4)*

After analyzing, pg_stats contain different values, as the large table is
sampled - I have user_b_freq = 0.0002, row_type_a_freq = 0.99686664,
deleted_at_null_frac = 0.04325,
thus the new calculation is: 520982816*0.0002*0.99686664*0.04325
= 4490.64987.

Now it's off by around 40x - and it seems to still only consider the single
column distributions.

Is there anything I'm missing ? I thought that maybe in my case, due to the
high null fractions of deleted_at, the extended stats aren't used, but
couldn't find an obvious hint from the code that would suggest that.


Appreciate your time !
Danny

The use of partial, expressional indices in pg < 14

[Danny Shemesh]

Hey everyone,

There's something I've been wondering about - to my understanding,
the planner won't use statistics collected on partial indices, as they may
or may not reflect the correct distribution of data.

When using expressional indices which are also partial, a-la an index on a
nested path of a jsonb column, or a function, with a where clause -
the planner won't actually use the collected statistics, and as such, the
index may end up unused or misused.

Since postgres 14, it's now possible to create extended statistics on an
expression, thus one could create a statistic on the expression used in the
partial index;
In previous versions, I believe the best one can do is either create a full
index on the expression, so the statistics would be utilized, or to extract
the expression to a dedicated column.

Concretely, this came from an index we've had on a relatively large table
(2TB~) on jsonb->some->>path;
the table serves several types of data, where some->>path is only relevant
for data type A, which is only a fraction of the total rows - thus an index
on type = A made lots of sense.

However, the collected statistics weren't used, even if the query contains
type = A, and thus the usage of the index is a bit random,
it's either utilized when it shouldn't, I believe due to the nature of the
hard-code estimation multipliers for the operators we use, or it's unused
when it would've been appropriate.

Two questions that came to mind were:
1. Are there any other actions one could take in pg < 14 (we're in 12,
specifically), avoiding creating a full index and extracting said fields to
a dedicated column ?
2. Would it be theoretically possible to use the collected statistics if
the index where clause is also specified in the query itself ?
or in other words, if the index only contains records where x is not null,
and the query also filters on x is not null, would the partial distribution
not be safe to use ?


Thank you for your time !
Danny

Showing alternative query planner plans with explain ?

[Danny Shemesh]

Hey all !

I'm currently optimizing queries and indices on a relatively large dataset;
one of the frequent questions I seem to ask myself is why the planner
chooses plan A over B.

Reading the docs, blogs, stack exchange posts, wiki, ... helps in trying to
tinker with the query or indices in a way that either A will be
discouraged, or B will be favoured, so I'd be more informed on why one was
chosen over the other and which is empirically better for a given dataset.

A tool I seem to be missing, and I wondered if such exists, is to have the
planner output alternative plans for a given query, i.e. to say, give me
the x top plans sorted by cost - I believe this would help shed some light
on the internal state machine and subsequent tinkering less
trial-and-error-ish.

Is there any way to achieve the above ?

Thanks a ton,
Danny

Would it be possible to utilize a GIN index to query for distinct values ?

[Danny Shemesh]

Hey everyone !

Bumping an older thread
,
I've read the GIN readme in the code base and have skimmed through the
implementation, it made me wonder -
would it be possible to use the index to query for distinct / count
distinct values, at least for some key types ?

For instance, say I have a GIN index on a single, highly cardinal but
non-unique text column (a-la 'name'); from my very limited understanding,
would it be possible to query for distinct / count distinct values via
roughly:
- Traversing the GIN entry tree tuples
- Gathering the key data from said tuples
- Discarding keys with no / empty posting lists, as they aren't discarded
from the tree
- Traversing the pending list for indices with fastupdate & merging the
result set

I'm probably off by quite a lot, but I'd really appreciate your great
insight on the above.

Thanks !
Danny