Index Skip Scan

classic Classic list List threaded Threaded
65 messages Options
1234
Reply | Threaded
Open this post in threaded view
|

Index Skip Scan

Jesper Pedersen
Hi all,

I would like to start a discussion on Index Skip Scan referred to as
Loose Index Scan in the wiki [1].

My use-case is the simplest form of Index Skip Scan (B-Tree only),
namely going from

CREATE TABLE t1 (a integer PRIMARY KEY, b integer);
CREATE INDEX idx_t1_b ON t1 (b);
INSERT INTO t1 (SELECT i, i % 3 FROM generate_series(1, 10000000) as i);
ANALYZE;
EXPLAIN (ANALYZE, VERBOSE, BUFFERS ON) SELECT DISTINCT b FROM t1;
  HashAggregate  (cost=169247.71..169247.74 rows=3 width=4) (actual
time=4104.099..4104.099 rows=3 loops=1)
    Output: b
    Group Key: t1.b
    Buffers: shared hit=44248
    ->  Seq Scan on public.t1  (cost=0.00..144247.77 rows=9999977
width=4) (actual time=0.059..1050.376 rows=10000000 loops=1)
          Output: a, b
          Buffers: shared hit=44248
  Planning Time: 0.157 ms
  Execution Time: 4104.155 ms
(9 rows)

to

CREATE TABLE t1 (a integer PRIMARY KEY, b integer);
CREATE INDEX idx_t1_b ON t1 (b);
INSERT INTO t1 (SELECT i, i % 3 FROM generate_series(1, 10000000) as i);
ANALYZE;
EXPLAIN (ANALYZE, VERBOSE, BUFFERS ON) SELECT DISTINCT b FROM t1;
  Index Skip Scan using idx_t1_b on public.t1  (cost=0.43..1.30 rows=3
width=4) (actual time=0.061..0.137 rows=3 loops=1)
    Output: b
    Heap Fetches: 3
    Buffers: shared hit=13
  Planning Time: 0.155 ms
  Execution Time: 0.170 ms
(6 rows)

I took Thomas Munro's previous patch [2] on the subject, added a GUC, a
test case, documentation hooks, minor code cleanups, and made the patch
pass an --enable-cassert make check-world run. So, the overall design is
the same.

However, as Robert Haas noted in the thread there are issues with the
patch as is, especially in relationship to the amcanbackward functionality.

A couple of questions to begin with.

Should the patch continue to "piggy-back" on T_IndexOnlyScan, or should
a new node (T_IndexSkipScan) be created ? If latter, then there likely
will be functionality that needs to be refactored into shared code
between the nodes.

Which is the best way to deal with the amcanbackward functionality ? Do
people see another alternative to Robert's idea of adding a flag to the
scan.

I wasn't planning on making this a patch submission for the July
CommitFest due to the reasons mentioned above, but can do so if people
thinks it is best. The patch is based on master/4c8156.

Any feedback, suggestions, design ideas and help with the patch in
general is greatly appreciated.

Thanks in advance !

[1] https://wiki.postgresql.org/wiki/Loose_indexscan
[2]
https://www.postgresql.org/message-id/flat/CADLWmXXbTSBxP-MzJuPAYSsL_2f0iPm5VWPbCvDbVvfX93FKkw%40mail.gmail.com

Best regards,
  Jesper

wip_indexskipscan.patch (31K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Alexander Korotkov
Hi!

On Mon, Jun 18, 2018 at 6:26 PM Jesper Pedersen
<[hidden email]> wrote:
> I would like to start a discussion on Index Skip Scan referred to as
> Loose Index Scan in the wiki [1].

Great, I glad to see you working in this!

> However, as Robert Haas noted in the thread there are issues with the
> patch as is, especially in relationship to the amcanbackward functionality.
>
> A couple of questions to begin with.
>
> Should the patch continue to "piggy-back" on T_IndexOnlyScan, or should
> a new node (T_IndexSkipScan) be created ? If latter, then there likely
> will be functionality that needs to be refactored into shared code
> between the nodes.

Is skip scan only possible for index-only scan?  I guess, that no.  We
could also make plain index scan to behave like a skip scan.  And it
should be useful for accelerating DISTINCT ON clause.  Thus, we might
have 4 kinds of index scan: IndexScan, IndexOnlyScan, IndexSkipScan,
IndexOnlySkipScan.  So, I don't think I like index scan nodes to
multiply this way, and it would be probably better to keep number
nodes smaller.  But I don't insist on that, and I would like to hear
other opinions too.

> Which is the best way to deal with the amcanbackward functionality ? Do
> people see another alternative to Robert's idea of adding a flag to the
> scan.

Supporting amcanbackward seems to be basically possible, but rather
complicated and not very efficient.  So, it seems to not worth
implementing, at least in the initial version.  And then the question
should how index access method report that it supports both skip scan
and backward scan, but not both together?  What about turning
amcanbackward into a function which takes (bool skipscan) argument?
Therefore, this function will return whether backward scan is
supported depending of whether skip scan is used.

> I wasn't planning on making this a patch submission for the July
> CommitFest due to the reasons mentioned above, but can do so if people
> thinks it is best. The patch is based on master/4c8156.

Please, register it on commitfest.  If even there wouldn't be enough
of time for this patch on July commitfest, it's no problem to move it.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Andrew Dunstan-8
In reply to this post by Jesper Pedersen


On 06/18/2018 11:25 AM, Jesper Pedersen wrote:
> Hi all,
>
> I would like to start a discussion on Index Skip Scan referred to as
> Loose Index Scan in the wiki [1].


awesome


>
>
>
> I wasn't planning on making this a patch submission for the July
> CommitFest due to the reasons mentioned above, but can do so if people
> thinks it is best. T


New large features are not appropriate for the July CF. September should
be your goal.

cheers

andrew

--
Andrew Dunstan                https://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Alexander Korotkov
On Mon, Jun 18, 2018 at 11:20 PM Andrew Dunstan
<[hidden email]> wrote:
> On 06/18/2018 11:25 AM, Jesper Pedersen wrote:
> > I wasn't planning on making this a patch submission for the July
> > CommitFest due to the reasons mentioned above, but can do so if people
> > thinks it is best. T
>
> New large features are not appropriate for the July CF. September should
> be your goal.

Assuming this, should we have possibility to register patch to
September CF from now?

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Michael Paquier-2
On Tue, Jun 19, 2018 at 12:06:59AM +0300, Alexander Korotkov wrote:
> Assuming this, should we have possibility to register patch to
> September CF from now?

There cannot be two commit fests marked as open at the same time as
Magnus mentions here:
https://www.postgresql.org/message-id/CABUevEx1k+axZcV2t3wEYf5uLg72YbKSch_hUhFnZq+-KSoJsA@...

There is no issue in registering new patches in future ones for admins,
but normal users cannot, right?  In this case, could you wait that the
next CF is marked as in progress and that the one of September is
opened?  You could also add it to the July one if you are not willing to
wait, and that will get bumped by one of the CFMs, but this makes the
whole process unnecessary noisy.
--
Michael

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Dmitry Dolgov
> On 18 June 2018 at 19:31, Alexander Korotkov <[hidden email]> wrote:
>>
>> A couple of questions to begin with.
>>
>> Should the patch continue to "piggy-back" on T_IndexOnlyScan, or should
>> a new node (T_IndexSkipScan) be created ? If latter, then there likely
>> will be functionality that needs to be refactored into shared code
>> between the nodes.
>
> Is skip scan only possible for index-only scan?  I guess, that no.  We
> could also make plain index scan to behave like a skip scan.  And it
> should be useful for accelerating DISTINCT ON clause.  Thus, we might
> have 4 kinds of index scan: IndexScan, IndexOnlyScan, IndexSkipScan,
> IndexOnlySkipScan.  So, I don't think I like index scan nodes to
> multiply this way, and it would be probably better to keep number
> nodes smaller.  But I don't insist on that, and I would like to hear
> other opinions too.

In one of patches I'm working on I had similar situation, when I wanted to
split one node into two similar nodes (before I just extended it) and logically
it made perfect sense. But it turned out to be quite useless and the advantage
I've got wasn't worth it - and just to mention, those nodes had more differences
than in this patch. So I agree that probably it would be better to keep using
IndexOnlyScan.

> On 19 June 2018 at 03:40, Michael Paquier <[hidden email]> wrote:
> On Tue, Jun 19, 2018 at 12:06:59AM +0300, Alexander Korotkov wrote:
>> Assuming this, should we have possibility to register patch to
>> September CF from now?
>
> There cannot be two commit fests marked as open at the same time as
> Magnus mentions here:
> https://www.postgresql.org/message-id/CABUevEx1k+axZcV2t3wEYf5uLg72YbKSch_hUhFnZq+-KSoJsA@...
>
> In this case, could you wait that the next CF is marked as in progress and
> that the one of September is opened?

Yep, since the next CF will start shortly that's the easiest thing to do.

Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Jesper Pedersen
In reply to this post by Alexander Korotkov
Hi Alexander,

On 06/18/2018 01:31 PM, Alexander Korotkov wrote:

> <[hidden email]> wrote:
>> Should the patch continue to "piggy-back" on T_IndexOnlyScan, or should
>> a new node (T_IndexSkipScan) be created ? If latter, then there likely
>> will be functionality that needs to be refactored into shared code
>> between the nodes.
>
> Is skip scan only possible for index-only scan?  I guess, that no.  We
> could also make plain index scan to behave like a skip scan.  And it
> should be useful for accelerating DISTINCT ON clause.  Thus, we might
> have 4 kinds of index scan: IndexScan, IndexOnlyScan, IndexSkipScan,
> IndexOnlySkipScan.  So, I don't think I like index scan nodes to
> multiply this way, and it would be probably better to keep number
> nodes smaller.  But I don't insist on that, and I would like to hear
> other opinions too.
>

Yes, there are likely other use-cases for Index Skip Scan apart from the
simplest form. Which sort of suggests that having dedicated nodes would
be better in the long run.

My goal is to cover the simplest form, which can be handled by extending
  the T_IndexOnlyScan node, or by having common functions that both use.
We can always improve the functionality with future patches.

>> Which is the best way to deal with the amcanbackward functionality ? Do
>> people see another alternative to Robert's idea of adding a flag to the
>> scan.
>
> Supporting amcanbackward seems to be basically possible, but rather
> complicated and not very efficient.  So, it seems to not worth
> implementing, at least in the initial version. > And then the question
> should how index access method report that it supports both skip scan
> and backward scan, but not both together?  What about turning
> amcanbackward into a function which takes (bool skipscan) argument?
> Therefore, this function will return whether backward scan is
> supported depending of whether skip scan is used.
>

The feedback from Robert Haas seems to suggest that it was a requirement
for the patch to be considered.

>> I wasn't planning on making this a patch submission for the July
>> CommitFest due to the reasons mentioned above, but can do so if people
>> thinks it is best. The patch is based on master/4c8156.
>
> Please, register it on commitfest.  If even there wouldn't be enough
> of time for this patch on July commitfest, it's no problem to move it.
>

Based on the feedback from Andrew and Michael I won't register this
thread until the September CF.

Thanks for your feedback !

Best regards,
  Jesper

Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Jesper Pedersen
In reply to this post by Dmitry Dolgov
Hi Dmitry,

On 06/19/2018 06:01 AM, Dmitry Dolgov wrote:

>> On 18 June 2018 at 19:31, Alexander Korotkov <[hidden email]> wrote:
>> Is skip scan only possible for index-only scan?  I guess, that no.  We
>> could also make plain index scan to behave like a skip scan.  And it
>> should be useful for accelerating DISTINCT ON clause.  Thus, we might
>> have 4 kinds of index scan: IndexScan, IndexOnlyScan, IndexSkipScan,
>> IndexOnlySkipScan.  So, I don't think I like index scan nodes to
>> multiply this way, and it would be probably better to keep number
>> nodes smaller.  But I don't insist on that, and I would like to hear
>> other opinions too.
>
> In one of patches I'm working on I had similar situation, when I wanted to
> split one node into two similar nodes (before I just extended it) and logically
> it made perfect sense. But it turned out to be quite useless and the advantage
> I've got wasn't worth it - and just to mention, those nodes had more differences
> than in this patch. So I agree that probably it would be better to keep using
> IndexOnlyScan.
>

I looked at this today, and creating a new node (T_IndexOnlySkipScan)
would make the patch more complex.

The question is if the patch should create such a node such that future
patches didn't have to deal with refactoring to a new node to cover
additional functionality.

Thanks for your feedback !

Best regards,
  Jesper

Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Bhushan Uparkar
In reply to this post by Alexander Korotkov
Hello Jesper,

I was reviewing index-skip patch example and have a comment on it. Example query “select distinct b from t1” is equivalent to “select b from t1 group by b”. When I tried the 2nd form of query it came up with different plan, is it possible that index skip scan can address it as well?


postgres=# explain verbose select  b from t1 group by b;
                                             QUERY PLAN
----------------------------------------------------------------------------------------------------
 Group  (cost=97331.29..97332.01 rows=3 width=4)
   Output: b
   Group Key: t1.b
   ->  Gather Merge  (cost=97331.29..97331.99 rows=6 width=4)
         Output: b
         Workers Planned: 2
         ->  Sort  (cost=96331.27..96331.27 rows=3 width=4)
               Output: b
               Sort Key: t1.b
               ->  Partial HashAggregate  (cost=96331.21..96331.24 rows=3 width=4)
                     Output: b
                     Group Key: t1.b
                     ->  Parallel Seq Scan on public.t1  (cost=0.00..85914.57 rows=4166657 width=4)
                           Output: a, b
(14 rows)

Time: 1.167 ms

— And here is the original example
postgres=# explain verbose SELECT DISTINCT b FROM t1;
                                  QUERY PLAN
-------------------------------------------------------------------------------
 Index Skip Scan using idx_t1_b on public.t1  (cost=0.43..1.30 rows=3 width=4)
   Output: b
(2 rows)

Time: 0.987 ms



> On Jun 18, 2018, at 10:31 AM, Alexander Korotkov <[hidden email]> wrote:
>
> Hi!
>
> On Mon, Jun 18, 2018 at 6:26 PM Jesper Pedersen
> <[hidden email]> wrote:
>> I would like to start a discussion on Index Skip Scan referred to as
>> Loose Index Scan in the wiki [1].
>
> Great, I glad to see you working in this!
>
>> However, as Robert Haas noted in the thread there are issues with the
>> patch as is, especially in relationship to the amcanbackward functionality.
>>
>> A couple of questions to begin with.
>>
>> Should the patch continue to "piggy-back" on T_IndexOnlyScan, or should
>> a new node (T_IndexSkipScan) be created ? If latter, then there likely
>> will be functionality that needs to be refactored into shared code
>> between the nodes.
>
> Is skip scan only possible for index-only scan?  I guess, that no.  We
> could also make plain index scan to behave like a skip scan.  And it
> should be useful for accelerating DISTINCT ON clause.  Thus, we might
> have 4 kinds of index scan: IndexScan, IndexOnlyScan, IndexSkipScan,
> IndexOnlySkipScan.  So, I don't think I like index scan nodes to
> multiply this way, and it would be probably better to keep number
> nodes smaller.  But I don't insist on that, and I would like to hear
> other opinions too.
>
>> Which is the best way to deal with the amcanbackward functionality ? Do
>> people see another alternative to Robert's idea of adding a flag to the
>> scan.
>
> Supporting amcanbackward seems to be basically possible, but rather
> complicated and not very efficient.  So, it seems to not worth
> implementing, at least in the initial version.  And then the question
> should how index access method report that it supports both skip scan
> and backward scan, but not both together?  What about turning
> amcanbackward into a function which takes (bool skipscan) argument?
> Therefore, this function will return whether backward scan is
> supported depending of whether skip scan is used.
>
>> I wasn't planning on making this a patch submission for the July
>> CommitFest due to the reasons mentioned above, but can do so if people
>> thinks it is best. The patch is based on master/4c8156.
>
> Please, register it on commitfest.  If even there wouldn't be enough
> of time for this patch on July commitfest, it's no problem to move it.
>
> ------
> Alexander Korotkov
> Postgres Professional: http://www.postgrespro.com
> The Russian Postgres Company
>
>


Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Thomas Munro-3
On Thu, Aug 16, 2018 at 5:44 PM, Bhushan Uparkar
<[hidden email]> wrote:
> I was reviewing index-skip patch example and have a comment on it. Example query “select distinct b from t1” is equivalent to “select b from t1 group by b”. When I tried the 2nd form of query it came up with different plan, is it possible that index skip scan can address it as well?

Yeah, there are a few tricks you can do with "index skip scans"
(Oracle name, or as IBM calls them, "index jump scans"... I was
slightly tempted to suggest we call ours "index hop scans"...).  For
example:

* groups and certain aggregates (MIN() and MAX() of suffix index
columns within each group)
* index scans where the scan key doesn't include the leading columns
(but you expect there to be sufficiently few values)
* merge joins (possibly the trickiest and maybe out of range)

You're right that a very simple GROUP BY can be equivalent to a
DISTINCT query, but I'm not sure if it's worth recognising that
directly or trying to implement the more general grouping trick that
can handle MIN/MAX, and whether that should be the same executor
node...  The idea of starting with DISTINCT was just that it's
comparatively easy.  We should certainly try to look ahead and bear
those features in mind when figuring out the interfaces though.  Would
the indexam skip(scan, direction, prefix_size) operation I proposed be
sufficient?  Is there a better way?

I'm glad to see this topic come back!

--
Thomas Munro
http://www.enterprisedb.com

Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Jesper Pedersen
In reply to this post by Bhushan Uparkar
Hi Bhushan,

On 08/16/2018 01:44 AM, Bhushan Uparkar wrote:
> I was reviewing index-skip patch example and have a comment on it.

Thanks for your interest, and feedback on this patch !

> Example query “select distinct b from t1” is equivalent to “select b from t1 group by b”. When I tried the 2nd form > of query it came up with different plan, is it possible that index skip scan can address it as well?
>

Like Thomas commented down-thread my goal is to keep this contribution
as simple as possible in order to get to something that can be
committed. Improvements can follow in future CommitFests, which may end
up in the same release.

However, as stated in my original mail my goal is the simplest form of
Index Skip Scan (or whatever we call it). I welcome any help with the patch.

Best regards,
  Jesper

Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Jesper Pedersen
In reply to this post by Thomas Munro-3
Hi Thomas,

On 08/16/2018 02:22 AM, Thomas Munro wrote:
> The idea of starting with DISTINCT was just that it's
> comparatively easy.  We should certainly try to look ahead and bear
> those features in mind when figuring out the interfaces though.  Would
> the indexam skip(scan, direction, prefix_size) operation I proposed be
> sufficient?  Is there a better way?
>

Yeah, I'm hoping that a Committer can provide some feedback on the
direction that this patch needs to take.

One thing to consider is the pluggable storage patch, which is a lot
more important than this patch. I don't want this patch to get in the
way of that work, so it may have to wait a bit in order to see any new
potential requirements.

> I'm glad to see this topic come back!
>

You did the work, and yes hopefully we can get closer to this subject in
12 :)

Best regards,
  Jesper

Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Stephen Frost
Greetings,

* Jesper Pedersen ([hidden email]) wrote:
> On 08/16/2018 02:22 AM, Thomas Munro wrote:
> >The idea of starting with DISTINCT was just that it's
> >comparatively easy.  We should certainly try to look ahead and bear
> >those features in mind when figuring out the interfaces though.  Would
> >the indexam skip(scan, direction, prefix_size) operation I proposed be
> >sufficient?  Is there a better way?
>
> Yeah, I'm hoping that a Committer can provide some feedback on the direction
> that this patch needs to take.

Thomas is one these days. :)

At least on first glance, that indexam seems to make sense to me, but
I've not spent a lot of time thinking about it.  Might be interesting to
ask Peter G about it though.

> One thing to consider is the pluggable storage patch, which is a lot more
> important than this patch. I don't want this patch to get in the way of that
> work, so it may have to wait a bit in order to see any new potential
> requirements.

Not sure where this came from, but I don't think it's particularly good
to be suggesting that one feature is more important than another or that
we need to have one wait for another as this seems to imply.  I'd
certainly really like to see PG finally have skipping scans, for one
thing, and it seems like with some effort that might be able to happen
for v12.  I'm not convinced that we're going to get pluggable storage to
happen in v12 and I don't really agree with recommending that people
hold off on making improvements to things because it's coming.

Thanks!

Stephen

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Jesper Pedersen
Hi Stephen,

On 08/16/2018 02:36 PM, Stephen Frost wrote:
>> Yeah, I'm hoping that a Committer can provide some feedback on the direction
>> that this patch needs to take.
>
> Thomas is one these days. :)
>

I know :)  However, there are some open questions from Thomas' original
submission that still needs to be ironed out.

> At least on first glance, that indexam seems to make sense to me, but
> I've not spent a lot of time thinking about it.  Might be interesting to
> ask Peter G about it though.
>

Yes, or Anastasia who also have done a lot of work on nbtree/.

>> One thing to consider is the pluggable storage patch, which is a lot more
>> important than this patch. I don't want this patch to get in the way of that
>> work, so it may have to wait a bit in order to see any new potential
>> requirements.
>
> Not sure where this came from, but I don't think it's particularly good
> to be suggesting that one feature is more important than another or that
> we need to have one wait for another as this seems to imply.  I'd
> certainly really like to see PG finally have skipping scans, for one
> thing, and it seems like with some effort that might be able to happen
> for v12.  I'm not convinced that we're going to get pluggable storage to
> happen in v12 and I don't really agree with recommending that people
> hold off on making improvements to things because it's coming.
>

My point was that I know this patch needs work, so any feedback that get
it closer to a solution will help.

Pluggable storage may / may not add new requirements, but it is up to
the people working on that, some of which are Committers, to take time
"off" to provide feedback for this patch in order steer me in right
direction.

Work can happen in parallel, and I'm definitely not recommending that
people hold off on any patches that they want to provide feedback for,
or submit for a CommitFest.

Best regards,
  Jesper

Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Stephen Frost
Greetings,

* Jesper Pedersen ([hidden email]) wrote:

> On 08/16/2018 02:36 PM, Stephen Frost wrote:
> >Not sure where this came from, but I don't think it's particularly good
> >to be suggesting that one feature is more important than another or that
> >we need to have one wait for another as this seems to imply.  I'd
> >certainly really like to see PG finally have skipping scans, for one
> >thing, and it seems like with some effort that might be able to happen
> >for v12.  I'm not convinced that we're going to get pluggable storage to
> >happen in v12 and I don't really agree with recommending that people
> >hold off on making improvements to things because it's coming.
>
> My point was that I know this patch needs work, so any feedback that get it
> closer to a solution will help.
>
> Pluggable storage may / may not add new requirements, but it is up to the
> people working on that, some of which are Committers, to take time "off" to
> provide feedback for this patch in order steer me in right direction.
I don't think it's really necessary for this work to be suffering under
some concern that pluggable storage will make it have to change.  Sure,
it might, but it also very well might not.  For my 2c, anyway, this
seems likely to get into the tree before pluggable storage does and it's
pretty unlikely to be the only thing that that work will need to be
prepared to address when it happens.

> Work can happen in parallel, and I'm definitely not recommending that people
> hold off on any patches that they want to provide feedback for, or submit
> for a CommitFest.

Yes, work can happen in parallel, and I don't really think there needs
to be a concern about some other patch set when it comes to getting this
patch committed.

Thanks!

Stephen

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Peter Geoghegan-4
In reply to this post by Thomas Munro-3
On Wed, Aug 15, 2018 at 11:22 PM, Thomas Munro
<[hidden email]> wrote:
> Yeah, there are a few tricks you can do with "index skip scans"
> (Oracle name, or as IBM calls them, "index jump scans"... I was
> slightly tempted to suggest we call ours "index hop scans"...).

Hopscotch scans?

> * groups and certain aggregates (MIN() and MAX() of suffix index
> columns within each group)
> * index scans where the scan key doesn't include the leading columns
> (but you expect there to be sufficiently few values)
> * merge joins (possibly the trickiest and maybe out of range)

FWIW, I suspect that we're going to have the biggest problems in the
optimizer. It's not as if ndistinct is in any way reliable. That may
matter more on average than it has with other path types.

--
Peter Geoghegan

Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Andres Freund
In reply to this post by Jesper Pedersen


On August 16, 2018 8:28:45 PM GMT+02:00, Jesper Pedersen <[hidden email]> wrote:
>One thing to consider is the pluggable storage patch, which is a lot
>more important than this patch. I don't want this patch to get in the
>way of that work, so it may have to wait a bit in order to see any new
>potential requirements.

I don't think this would be a meaningful, relative to the size of the patch sets, amount of conflict between the two. So I don't think we have to consider relative importance (which I don't think is that easy to assess in this case).

Fwiw, I've a significantly further revised version of the tableam patch that I plan to send in a few days. Ported the current zheap patch as a separate AM which helped weed out a lot of issues.

Andres

Andres
--
Sent from my Android device with K-9 Mail. Please excuse my brevity.
Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Thomas Munro-3
In reply to this post by Peter Geoghegan-4
On Fri, Aug 17, 2018 at 7:48 AM, Peter Geoghegan <[hidden email]> wrote:

> On Wed, Aug 15, 2018 at 11:22 PM, Thomas Munro
> <[hidden email]> wrote:
>> * groups and certain aggregates (MIN() and MAX() of suffix index
>> columns within each group)
>> * index scans where the scan key doesn't include the leading columns
>> (but you expect there to be sufficiently few values)
>> * merge joins (possibly the trickiest and maybe out of range)
>
> FWIW, I suspect that we're going to have the biggest problems in the
> optimizer. It's not as if ndistinct is in any way reliable. That may
> matter more on average than it has with other path types.

Can you give an example of problematic ndistinct underestimation?

I suppose you might be able to defend against that in the executor: if
you find that you've done an unexpectedly high number of skips, you
could fall back to regular next-tuple mode.  Unfortunately that's
require the parent plan node to tolerate non-unique results.

I noticed that the current patch doesn't care about restrictions on
the range (SELECT DISTINCT a FROM t WHERE a BETWEEN 500 and 600), but
that causes it to overestimate the number of btree searches, which is
a less serious problem (it might not chose a skip scan when it would
have been better).

--
Thomas Munro
http://www.enterprisedb.com

Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Jesper Pedersen
In reply to this post by Peter Geoghegan-4
Hi Peter,

On 08/16/2018 03:48 PM, Peter Geoghegan wrote:

> On Wed, Aug 15, 2018 at 11:22 PM, Thomas Munro
> <[hidden email]> wrote:
>> * groups and certain aggregates (MIN() and MAX() of suffix index
>> columns within each group)
>> * index scans where the scan key doesn't include the leading columns
>> (but you expect there to be sufficiently few values)
>> * merge joins (possibly the trickiest and maybe out of range)
>
> FWIW, I suspect that we're going to have the biggest problems in the
> optimizer. It's not as if ndistinct is in any way reliable. That may
> matter more on average than it has with other path types.
>

Thanks for sharing this; it is very useful to know.

Best regards,
  Jesper

Reply | Threaded
Open this post in threaded view
|

Re: Index Skip Scan

Peter Geoghegan-4
In reply to this post by Thomas Munro-3
On Thu, Aug 16, 2018 at 4:10 PM, Thomas Munro
<[hidden email]> wrote:
> Can you give an example of problematic ndistinct underestimation?

Yes. See https://postgr.es/m/CAKuK5J12QokFh88tQz-oJMSiBg2QyjM7K7HLnbYi3Ze+Y5BtWQ@...,
for example. That's a complaint about an underestimation specifically.

This seems to come up about once every 3 years, at least from my
perspective. I'm always surprised that ndistinct doesn't get
implicated in bad query plans more frequently.

> I suppose you might be able to defend against that in the executor: if
> you find that you've done an unexpectedly high number of skips, you
> could fall back to regular next-tuple mode.  Unfortunately that's
> require the parent plan node to tolerate non-unique results.

I like the idea of dynamic fallback in certain situations, but the
details always seem complicated.

--
Peter Geoghegan

1234