Date: Tue, 4 Feb 2020 21:02:05 +0100
From: Dmitry Dolgov <9erthalion6@gmail.com>
To: Floris Van Nee <florisvannee@Optiver.com>
Cc: Peter Geoghegan <pg@bowt.ie>,
	Jesper Pedersen <jesper.pedersen@redhat.com>,
	David Rowley <david.rowley@2ndquadrant.com>,
	Tomas Vondra <tomas.vondra@2ndquadrant.com>,
	Kyotaro Horiguchi <horikyota.ntt@gmail.com>,
	Alvaro Herrera <alvherre@2ndquadrant.com>,
	Thomas Munro <thomas.munro@gmail.com>,
	James Coleman <jtc331@gmail.com>,
	Rafia Sabih <rafia.pghackers@gmail.com>,
	Jeff Janes <jeff.janes@gmail.com>,
	Bhushan Uparkar <bhushan.uparkar@gmail.com>,
	PostgreSQL-development <pgsql-hackers@postgresql.org>,
	Alexander Korotkov <a.korotkov@postgrespro.ru>
Subject: Re: Index Skip Scan
Message-ID: <20200204200205.ip5c2mzy3i2okqey@localhost>
References: <1e59d800b38141c5af2ad3a64cf9758e@opammb0562.comp.optiver.com>
 <802e46fa-dc2c-4c32-e55b-884e04aa7f12@redhat.com>
 <CAH2-Wzk6hvXvZ+1q4JBRunZkxmJwdXxnNsWuKJBp+F+mJuZYZw@mail.gmail.com>
 <20200121160942.eu4bvbu46nt223ug@localhost>
 <a713fef85da14e1fbca51d19c872d023@opammb0562.comp.optiver.com>
 <20200122160441.ograupmzyytde2mi@localhost>
 <1579713885361.64964@Optiver.com>
 <20200122213603.ndlm6t4ryivdwxs7@localhost>
 <20200127103016.ieflsboqveb6iduc@localhost>
 <e198edfa18804c13b6b383b62fbfd94a@opammb0561.comp.optiver.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <e198edfa18804c13b6b383b62fbfd94a@opammb0561.comp.optiver.com>
Precedence: bulk

> On Mon, Jan 27, 2020 at 02:00:39PM +0000, Floris Van Nee wrote:
>
> Thanks for the new patch! I tested it and managed to find a case that causes
> some issues. Here's how to reproduce:

So, after a bit of investigation I found out the issue (it was actually there
even in the previous version). In this only case of moving forward and reading
backward, exactly scenarious you've described above, current implementation was
not ignoring deleted tuples.

My first idea to fix this was to use _bt_readpage when necessary and put
couple of _bt_killitems when we leave a page while jumping before, so that
deleted tuples will be ignored. To demonstrate it visually, let's say we
want to go backward on a cursor over an ORDER BY a DESC, b DESC query,
i.e. return:

    (1,100), (2, 100), (3, 100) etc.

To achieve that we jump from (1,1) to (1,100), from (2,1) to (2,100) and so on.
If some values are deleted, we need to read backward. E.g. if (3,100) is
deleted, we need to return (3,99).
                                                                             
   +---------------+---------------+---------------+---------------+         
   |               |               |               |               |         
   | 1,1 ... 1,100 | 2,1 ... 2,100 | 3,1 ... 3,100 | 4,1 ... 4,100 |         
   |               |               |               |               |         
   +---------------+---------------+---------------+---------------+         
                                                                             
   |             ^ |             ^ |             ^ |             ^           
   |             | |             | |             | |             |           
   +-------------+ +-------------+ +-------------+ +-------------+           
                                                                             
If it happened that a whole value series is deleted, we return to the
previous value and need to detect such situation. E.g. if all the values
from (3,1) to (3,100) were deleted, we will return to (2,100).
                                                                             
   +---------------+---------------+               +---------------+         
   |               |               |               |               |         
   | 1,1 ... 1,100 | 2,1 ... 2,100 |<--------------+ 4,1 ... 4,100 |         
   |               |               |               |               |         
   +---------------+---------------+               +---------------+         
                                                                 ^           
   |             ^ |             ^ |             ^               |           
   |             | |             | |             |               |           
   +-------------+ +-------------+ +-------------+               |           
                                   +-----------------------------+ 
                                                                             
This all is implemented inside _bt_skip. Unfortunately as I see it now the idea
of relying on ability to skip dead index tuples without checking a heap tuple
is not reliable, since an index tuple will be added into killedItems and can be
marked as dead only when not a single transaction can see it anymore.

Potentially there are two possible solutions:

* Adjust the code in nodeIndexOnlyscan to perform a proper visibility check and
  understand if we returned back. Obviously it will make the patch more invasive.

* Reduce scope of the patch, and simply do not apply jumping in this case. This
  means less functionality but hopefully still brings some value.

At this point me and Jesper inclined to go with the second option. But maybe
I'm missing something, are there any other suggestions?