Thread: [BUGFIX] amcanbackward is not checked before building backward indexpaths

Hi hackers!

Experimenting with the new pluggable storage API, I found that amcanbackward
flag is not checked in build_index_paths() before
build_index_pathkeys(... BackwardScanDirection) call when we are building
paths for ORDER BY.  And this flag is even not copied into IndexOptInfo struct.
Obviously, this can lead to misuse of Backward Index [Only] Scan plans.

Attached patch with the corresponding fix.

There are no test cases because now only btree supports ordered scans but it
supports backward scans too.

-- 
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Nikita Glukhov <n.gluhov@postgrespro.ru> writes:
> Experimenting with the new pluggable storage API, I found that amcanbackward
> flag is not checked in build_index_paths() before
> build_index_pathkeys(... BackwardScanDirection) call when we are building
> paths for ORDER BY.  And this flag is even not copied into IndexOptInfo struct.
> Obviously, this can lead to misuse of Backward Index [Only] Scan plans.

> Attached patch with the corresponding fix.

I think this patch is based on a misunderstanding of what amcanbackward
means.  We *require* indexes that claim to support amcanorder to support
scanning in either direction.  What amcanbackward is about is whether
the index can support reversing direction mid-scan, as would be required
to support FETCH FORWARD followed by FETCH BACKWARD in a cursor.  That's
actually independent of whether the index can implement a defined
ordering; see for example the hash AM, which sets amcanbackward but not
amcanorder.

This is documented, though perhaps not sufficiently clearly, in
indexam.sgml:

    The amgettuple function has a direction argument, which can be either
    ForwardScanDirection (the normal case) or BackwardScanDirection. If
    the first call after amrescan specifies BackwardScanDirection, then
    the set of matching index entries is to be scanned back-to-front
    rather than in the normal front-to-back direction, so amgettuple must
    return the last matching tuple in the index, rather than the first one
    as it normally would. (This will only occur for access methods that
    set amcanorder to true.) After the first call, amgettuple must be
    prepared to advance the scan in either direction from the most
    recently returned entry. (But if amcanbackward is false, all
    subsequent calls will have the same direction as the first one.)

Perhaps there is a case for adding an additional flag to allow specifying
"I can't support ORDER BY DESC", but I'm not in a big hurry to do so.
I think there would be more changes than this needed to handle such a
restriction, anyway.

            regards, tom lane

Alexander Korotkov <a.korotkov@postgrespro.ru> writes:
> On Wed, May 16, 2018 at 1:41 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Perhaps there is a case for adding an additional flag to allow specifying
>> "I can't support ORDER BY DESC", but I'm not in a big hurry to do so.
>> I think there would be more changes than this needed to handle such a
>> restriction, anyway.

> OK, got it.  We'll probably propose a patch implementing that to the
> next commitfest.

If you do, it wouldn't be a bad idea to try to clarify the existing
code and docs around this point.  I'm thinking that amcanbackward is
misleadingly named; maybe we should rename it as part of the change?

            regards, tom lane

>>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:

 Tom> What amcanbackward is about is whether the index can support
 Tom> reversing direction mid-scan, as would be required to support
 Tom> FETCH FORWARD followed by FETCH BACKWARD in a cursor. That's
 Tom> actually independent of whether the index can implement a defined
 Tom> ordering; see for example the hash AM, which sets amcanbackward
 Tom> but not amcanorder.

Ugh, so the docs for amutils get this wrong, and if I'd looked at this
more carefully when doing them to begin with I'd have given the
'backwards_scan' property a better name or omitted it entirely.

I'll fix the docs accordingly. I'm referring specifically to this bit:

https://www.postgresql.org/docs/current/static/functions-info.html#FUNCTIONS-INFO-INDEX-PROPS

which I think should say "Can the scan direction be changed in
mid-scan?" in place of the current text (unless anyone has better
wording?)

-- 
Andrew (irc:RhodiumToad)

Andrew Gierth <andrew@tao11.riddles.org.uk> writes:
> Ugh, so the docs for amutils get this wrong, and if I'd looked at this
> more carefully when doing them to begin with I'd have given the
> 'backwards_scan' property a better name or omitted it entirely.

Ooops.

> I'll fix the docs accordingly. I'm referring specifically to this bit:
> https://www.postgresql.org/docs/current/static/functions-info.html#FUNCTIONS-INFO-INDEX-PROPS
> which I think should say "Can the scan direction be changed in
> mid-scan?" in place of the current text (unless anyone has better
> wording?)

Maybe "Can the scan direction be reversed in mid-scan?".  I'm not
absolutely sure that that's better ...

            regards, tom lane

"David G. Johnston" <david.g.johnston@gmail.com> writes:
> On Thu, May 17, 2018 at 8:46 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Maybe "Can the scan direction be reversed in mid-scan?".  I'm not
>> absolutely sure that that's better ...

> ​A cursory read might conclude that "reversing" can only happen once while
> they will likely understand that "changing" can happen multiple times.
> This is minor point - the two are effectively the same.
> Maybe: "Supports both FETCH FORWARD and FETCH BACKWARD during the same scan"

Oh, yeah, mentioning what it's *for* would help clarify things, no?
So perhaps

"Can the scan direction be changed in mid-scan (to support FETCH FORWARD
and FETCH BACKWARD on a cursor)?"

> Or:
> "Supports SCROLL(able) WITHOUT HOLD cursors"

That seems a bit more vague/indirect.

            regards, tom lane

On 2018-May-17, Tom Lane wrote:

> "David G. Johnston" <david.g.johnston@gmail.com> writes:
> > On Thu, May 17, 2018 at 8:46 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> >> Maybe "Can the scan direction be reversed in mid-scan?".  I'm not
> >> absolutely sure that that's better ...
> 
> > ​A cursory read might conclude that "reversing" can only happen once while
> > they will likely understand that "changing" can happen multiple times.
> > This is minor point - the two are effectively the same.
> > Maybe: "Supports both FETCH FORWARD and FETCH BACKWARD during the same scan"
> 
> Oh, yeah, mentioning what it's *for* would help clarify things, no?
> So perhaps
> 
> "Can the scan direction be changed in mid-scan (to support FETCH FORWARD
> and FETCH BACKWARD on a cursor)?"

To me that sounds like the flag is a prerequisite of using the cursor in
either direction.  But maybe "to support both FETCH FORWARD and FETCH
BACKWARD on the same cursor" is sufficient.  Or maybe "to support
changing scan direction on a cursor".


To make matters worse, IIUC it's actually fine to read the cursor in one
direction to completion, then in the other direction to completion,
without this flag, right?

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

>>>>> "Alvaro" == Alvaro Herrera <alvherre@2ndquadrant.com> writes:

 >> "Can the scan direction be changed in mid-scan (to support FETCH
 >> FORWARD and FETCH BACKWARD on a cursor)?"

How about,

"Can the scan direction be changed in mid-scan (to support FETCH
BACKWARD on a cursor without needing materialization)?"

 Alvaro> To me that sounds like the flag is a prerequisite of using the
 Alvaro> cursor in either direction. But maybe "to support both FETCH
 Alvaro> FORWARD and FETCH BACKWARD on the same cursor" is sufficient.
 Alvaro> Or maybe "to support changing scan direction on a cursor".

 Alvaro> To make matters worse, IIUC it's actually fine to read the
 Alvaro> cursor in one direction to completion, then in the other
 Alvaro> direction to completion, without this flag, right?

If you explicitly declare your cursor as SCROLL, which you should do if
you want to fetch backward in it, then it's always OK to switch
directions - the planner will have inserted a Materialize node if one is
needed. If you didn't declare it with SCROLL, and it's not implicitly
SCROLL as per the rules below, you can't fetch backward in it at all
regardless of whether you reached the end. (see error message in
PortalRunSelect for where this happens)

(I found a bit of a wart in that code: MOVE/FETCH ABSOLUTE will
arbitrarily fail or not fail on a no-scroll cursor according to the
absolute position requested - if it's closer to 1 than the current
position it'll rewind to the start, which always works, then scan
forwards; but if it's closer to the current position, it'll try moving
backwards even in a no-scroll cursor.)

What amcanbackward actually affects, as I read the code, is this:

1. ExecSupportsBackwardScan applied to an IndexScan or IndexOnlyScan is
   true if and only if amcanbackward is true.

2. If you specify neither SCROLL nor NO SCROLL when creating a cursor,
   then the cursor is implicitly SCROLL if and only if the topmost plan
   node returns true from ExecSupportsBackwardScan.

3. If you specify SCROLL when creating a cursor, then the planner
   inserts a Materialize node on the top of the plan if
   ExecSupportsBackwardScan is not true of the previous top plan node.

-- 
Andrew (irc:RhodiumToad)

Alvaro Herrera <alvherre@2ndquadrant.com> writes:
> To make matters worse, IIUC it's actually fine to read the cursor in one
> direction to completion, then in the other direction to completion,
> without this flag, right?

In principle that'd be possible without amcanbackward if you were to
shut down the plan at the end of the forward scan and start a fresh
execution for the backwards scan; but there is no code or API for doing
that with a cursor.  So I think this is just a red herring.

The case that's actually of interest is where you write

    SELECT ... FROM tab ORDER BY indexed_col DESC

and then just read that normally without a cursor, or at least without
a scrollable one.  This does not require amcanbackward, since the
executor will not change scan directions: it's all ForwardScanDirection
at the top level (which gets inverted to BackwardScanDirection somewhere
in nodeIndexscan, which knows the index is being used backwards).

Currently we assume that any index capable of amcanorder can do this
scenario too.  I'm willing to entertain a proposal to have a separate
capability flag for it, although I think it's fair to question whether
designing an order-supporting index AM that can't do this is actually a
good idea.  The current user docs say explicitly that you don't need
to make both ASC and DESC order indexes on the same thing.  I do not
really want to put in weasel wording saying "unless you're using some
crappy third party index type".

            regards, tom lane