Optimize single tuple fetch from nbtree index

Floris Van Nee <florisvannee@Optiver.com> writes:

Every time the index scan is done, all tuples from the leaf page are
read in nbtsearch.c:_bt_readpage. The idea of this patch is to make an
exception for this *only* the first time amgettuple gets called.

Regardless of whether there's actually a LIMIT 1? That seems disastrous
for every other case than the narrow one where the optimization wins.
Because every other case is now going to have to touch the index page
twice. That's more CPU and about double the contention --- if you could
not measure any degradation from that, you're not measuring the right
thing.

In principle, you could pass down knowledge of whether there's a LIMIT,
using the same mechanism used to enable top-N sorting. But it'd have to
also go through the AM interface layer, so I'm not sure how messy this
would be.

This calls _bt_first in nbtsearch.c, which will, if there are scankeys, descend the tree to a leaf page and read just the first (or possibly two) tuples. It won't touch the rest of the page yet. If indeed just one tuple was required, there won't be a call to _bt_next and we're done. If we do need more than one tuple, _bt_next will resume reading tuples from the index page at the point where we left off.

How do you know how many index entries you have to fetch to get a tuple
that's live/visible to the query?

- We need to take into account page splits, insertions and vacuums while we do not have the read-lock in between _bt_first and the first call to _bt_next. This made my patch quite a bit more complicated than my initial implementation.

Meh. I think the odds that you got this 100% right are small, and the
odds that it would be maintainable are smaller. There's too much that
can happen if you're not holding any lock --- and there's a lot of active
work on btree indexes, which could break whatever assumptions you might
make today.

I'm not unalterably opposed to doing something like this, but my sense
is that the complexity and probable negative performance impact on other
cases are not going to look like a good trade-off for optimizing the
case at hand.

BTW, you haven't even really made the case that optimizing a query that
behaves this way is the right thing to be doing ... maybe some other
plan shape that isn't a nestloop around a LIMIT query would be a better
solution.

regards, tom lane

Hi Tom,

Thanks for your quick reply!

Regardless of whether there's actually a LIMIT 1? That seems disastrous
for every other case than the narrow one where the optimization wins.
Because every other case is now going to have to touch the index page
twice. That's more CPU and about double the contention --- if you could
not measure any degradation from that, you're not measuring the right
thing.

I thought the same as well at first. Note that I did measure degradation of 2-3% as mentioned on some cases, but initially I also expected worse. Do you have any ideas on cases that would suffer the most? I thought the tight inner nested loop that I posted in my performance tests would have this index lookup as bottleneck. I know they are the bottleneck for the LIMIT 1 query (because these improve by a factor 2-3 with the patch). And my theory is that for a LIMIT 3, the price paid for this optimization is highest, because it would touch the page twice and read all items from it, while only returning three of them.

In principle, you could pass down knowledge of whether there's a LIMIT,
using the same mechanism used to enable top-N sorting. But it'd have to
also go through the AM interface layer, so I'm not sure how messy this
would be.

This was an idea I had as well and I would be willing to implement such a thing if this is deemed interesting enough by the community. However, I didn't want to do this for the first version of this patch, as it would be quite some extra work, which would be useless if the idea of the patch itself gets rejected already. :-) I'd appreciate any pointers in the right direction - I can take a look at how top-N sorting pushes the LIMIT down. Given enough interest for the basic idea of this patch, I will implement it.

This calls _bt_first in nbtsearch.c, which will, if there are scankeys, descend the tree to a leaf page and read just the first (or possibly two) tuples. It won't touch the rest of the page yet. If indeed just one tuple was required, there won't be a call to _bt_next and we're done. If we do need more than one tuple, _bt_next will resume reading tuples from the index page at the point where we left off.

How do you know how many index entries you have to fetch to get a tuple

that's live/visible to the query?

Indeed we don't know that - that's why this initial patch does not make any assumptions about this and just assumes the good-weather scenario that everything is visible. I'm not sure if it's possible to give an estimation of this and whether or not that would be useful. Currently, if it turns out that the tuple is not visible, there'll just be another call to _bt_next again which will resume reading the page as normal. I'm open to implement any suggestions that may improve this.

- We need to take into account page splits, insertions and vacuums while we do not have the read-lock in between _bt_first and the first call to _bt_next. This made my patch quite a bit more complicated than my initial implementation.

Meh. I think the odds that you got this 100% right are small, and the
odds that it would be maintainable are smaller. There's too much that
can happen if you're not holding any lock --- and there's a lot of active
work on btree indexes, which could break whatever assumptions you might
make today.

Agreed, which is also why I posted this initial version of the patch here already, to get some input from the experts on this topic what assumptions can be made now and in the future. If it turns out that it's completely not feasible to do an optimization like this, because of other constraints in the btree implementation, then we're done pretty quickly here. :-) For what it's worth: the patch at least passes make check consistently - I caught a lot of these edge cases related to page splits and insertions while running the regression tests, which runs the modified bits of code quite often and in parallel. There may be plenty of edge cases left however...

I'm not unalterably opposed to doing something like this, but my sense
is that the complexity and probable negative performance impact on other
cases are not going to look like a good trade-off for optimizing the
case at hand.

I do think it could be a big win if we could get something like this working. Cases with a LIMIT seem common enough to me to make it possible to add some extra optimizations, especially if that could lead to 2-3x the TPS for these kind of queries. However, it indeed needs to be within a reasonable complexity. If it turns out that in order for us to optimize this, we need to add a lot of extra complexity, it may not be worth it to add it.

BTW, you haven't even really made the case that optimizing a query that
behaves this way is the right thing to be doing ... maybe some other
plan shape that isn't a nestloop around a LIMIT query would be a better
solution.

It is pretty difficult to come up with any faster plans than this unfortunately. We have a large database with many tables with timeseries data, and when tables get large and when there's an efficient multi-column index and when you want to do these kind of time-base or item-based lookups, the nested loop is generally the fastest option. I can elaborate more on this, but I'm not sure if this thread is the best place for that.

I appreciate you taking the time to take a look at this. I'd be happy to look more into any suggestions you come up with. Working on this has taught me a lot about the internals of Postgres already - I find it really interesting!

-Floris

On Fri, Aug 2, 2019 at 1:43 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Meh. I think the odds that you got this 100% right are small, and the
odds that it would be maintainable are smaller. There's too much that
can happen if you're not holding any lock --- and there's a lot of active
work on btree indexes, which could break whatever assumptions you might
make today.

I agree that this sounds very scary.

BTW, you haven't even really made the case that optimizing a query that
behaves this way is the right thing to be doing ... maybe some other
plan shape that isn't a nestloop around a LIMIT query would be a better
solution.

I wonder if some variety of block nested loop join would be helpful
here. I'm not aware of any specific design that would help with
Floris' case, but the idea of reducing the number of scans required on
the inner side by buffering outer side tuples (say based on the
"k=:val" constant) seems like it might generalize well enough. I
suggest Floris look into that possibility. This paper might be worth a
read:

https://dl.acm.org/citation.cfm?id=582278

(Though it also might not be worth a read -- I haven't actually read it myself.)

--
Peter Geoghegan

On Fri, Aug 2, 2019 at 5:34 PM Peter Geoghegan <pg@bowt.ie> wrote:

I wonder if some variety of block nested loop join would be helpful
here. I'm not aware of any specific design that would help with
Floris' case, but the idea of reducing the number of scans required on
the inner side by buffering outer side tuples (say based on the
"k=:val" constant) seems like it might generalize well enough. I
suggest Floris look into that possibility. This paper might be worth a
read:

https://dl.acm.org/citation.cfm?id=582278

Actually, having looked at the test case in more detail, that now
seems less likely. The test case seems designed to reward making it
cheaper to access one specific tuple among a fairly large group of
related tuples -- reducing the number of inner scans is not going to
be possible there.

If this really is totally representative of the case that Floris cares
about, I suppose that the approach taken more or less makes sense.
Unfortunately, it doesn't seem like an optimization that many other
users would find compelling, partly because it's only concerned with
fixed overheads, and partly because most queries don't actually look
like this.

--
Peter Geoghegan

Hello everyone.

I am also was looking into possibility of such optimisation few days ago
(attempt to reduce memcpy overhead on IndexOnlyScan).

One thing I noticed here - whole page is scanned only if index quals are
"opened" at some side.

So, in case of
SELECT* FROM tbl WHERE k=:val AND ts<=:timestamp ORDER BY k, ts DESC
LIMIT 1;
whole index page will be read.

But
SELECT* FROM tbl WHERE k=:val AND ts<=:timestamp AND ts<:=timestamp -
:interval ORDER BY k, ts DESC LIMIT 1;
is semantically the same, but only few :interval records will be processed.

So, you could try to compare such query in your benchmarks.

Also, some info about current design is contained in
src\backend\access\nbtree\README ("To minimize lock/unlock traffic, an
index scan always searches a leaf page
to identify all the matching items at once").

Thanks,
Michail.

Hi Peter,

Actually, having looked at the test case in more detail, that now
seems less likely. The test case seems designed to reward making it
cheaper to access one specific tuple among a fairly large group of
related tuples -- reducing the number of inner scans is not going to
be possible there.

If this really is totally representative of the case that Floris cares
about, I suppose that the approach taken more or less makes sense.
Unfortunately, it doesn't seem like an optimization that many other
users would find compelling, partly because it's only concerned with
fixed overheads, and partly because most queries don't actually look
like this.

Thanks for taking a look. Unfortunately this is exactly the case I care about. I'm a bit puzzled as to why this case wouldn't come up more often by other users though. We have many large tables with timeseries data and it seems to me that with timeseries data, two of the most common queries are:
(1) What is the state of { a1,a2, a3 ...} at timepoint t (but you don't know that there's an update *exactly* at timepoint t - so you're left with trying to find the latest update smaller than t)
(2) What is the state of { a } at timepoints { t1, t2, t3 ... }
Given that a1,a2,a3... are indepedently updating, but similar time series (eg. sensor a1 and sensor a2, but both provide a temperature value and update independently from each other).
Both of these can also be done with some kind of DISTINCT ON clause, but this is often already much slower than just doing a nested loop of fast index lookups with LIMIT 1 (this depends on the frequency of the timeseries data itself versus the sampling rate of your query though, for high frequency time series and/or low frequency sampling the LIMIT 1 approach is much faster).

Note that there is actually some related work to this - in the Index Skip Scan thread [1]/messages/by-id/CA+hUKGKW4dXTP9G+WBskjT09tzD+9aMWEm=Fpeb6RS5SXfPyKw@mail.gmail.com a function called _bt_read_closest was developed which also partially reads the page. A Skip Scan has a very similar access pattern to the use case I describe here, because it's also very likely to just require one tuple from the page. Even though the implementation in that patch is currently incorrect, performance of the Skip Scan would likely also be quite a bit faster if it had a correct implementation of this partial page-read and it wouldn't have to read the full page every time.

I have one further question about these index offsets. There are several comments in master that indicate that it's impossible that an item moves 'left' on a page, if we continuously hold a pin on the page. For example, _bt_killitems has a comment like this:

* Note that if we hold a pin on the target page continuously from initially
* reading the items until applying this function, VACUUM cannot have deleted
* any items from the page, and so there is no need to search left from the
* recorded offset. (This observation also guarantees that the item is still
* the right one to delete, which might otherwise be questionable since heap
* TIDs can get recycled.) This holds true even if the page has been modified
* by inserts and page splits, so there is no need to consult the LSN.

Still, exactly this case happens in practice. In my tests I was able to get behavior like:
1) pin + lock a page in _bt_first
2) read a tuple, record indexOffset (for example offset=100) and heap tid
3) unlock page, but *keep* the pin (end of _bt_first of my patch)
4) lock page again in _bt_next (we still hold the pin, so vacuum shouldn't have occurred)
5) look inside the current page for the heap Tid that we registered earlier
6) we find that we can now find this tuple at indexOffset=98, eg. it moved left. This should not be possible.
This case sometimes randomly happens when running 'make check', which is why I added code in my patch to also look left on the page from the previous indexOffset.

However, this is in contradiction with the comments (and code) of _bt_killitems.
Is the comment incorrect/outdated or is there a bug in vacuum or any other part of Postgres that might move index items left even though there are others holding a pin?

-Floris

[1]: /messages/by-id/CA+hUKGKW4dXTP9G+WBskjT09tzD+9aMWEm=Fpeb6RS5SXfPyKw@mail.gmail.com

05.08.2019 14:34, Floris Van Nee wrote:

I have one further question about these index offsets. There are several comments in master that indicate that it's impossible that an item moves 'left' on a page, if we continuously hold a pin on the page. For example, _bt_killitems has a comment like this:

* Note that if we hold a pin on the target page continuously from initially
* reading the items until applying this function, VACUUM cannot have deleted
* any items from the page, and so there is no need to search left from the
* recorded offset. (This observation also guarantees that the item is still
* the right one to delete, which might otherwise be questionable since heap
* TIDs can get recycled.) This holds true even if the page has been modified
* by inserts and page splits, so there is no need to consult the LSN.

Still, exactly this case happens in practice. In my tests I was able to get behavior like:
1) pin + lock a page in _bt_first
2) read a tuple, record indexOffset (for example offset=100) and heap tid
3) unlock page, but*keep* the pin (end of _bt_first of my patch)
4) lock page again in _bt_next (we still hold the pin, so vacuum shouldn't have occurred)
5) look inside the current page for the heap Tid that we registered earlier
6) we find that we can now find this tuple at indexOffset=98, eg. it moved left. This should not be possible.
This case sometimes randomly happens when running 'make check', which is why I added code in my patch to also look left on the page from the previous indexOffset.

However, this is in contradiction with the comments (and code) of _bt_killitems.
Is the comment incorrect/outdated or is there a bug in vacuum or any other part of Postgres that might move index items left even though there are others holding a pin?

Hello,
welcome to hackers with your first patch)

As far as I understood from the thread above, the design of this
optimization is under discussion, so I didn't review the proposed patch
itself.
Though, I got interested in the comment inconsistency you have found.
I added debug message into this code branch of the patch and was able to
see it in regression.diffs after 'make check':
Speaking of your patch, it seems that the buffer was unpinned and pinned
again between two reads,
and the condition of holding it continuously has not been met.

I didn't dig into the code, but this line looks suspicious (see my
findings about BTScanPosIsPinned below):

        /* bump pin on current buffer for assignment to mark buffer */
        if (BTScanPosIsPinned(so->currPos))
            IncrBufferRefCount(so->currPos.buf);

While reading the code to answer your question, I noticed that
BTScanPosIsPinned macro name is misleading.
It calls BufferIsValid(), not BufferIsPinned() as one could expect.
And BufferIsValid in bufmgr.h comment explicitly states that it
shouldn't be confused with BufferIsPinned.
The same goes for BTScanPosUnpinIfPinned().

I propose that we update BTScanPosIsPinned macro. Or, at least write a
comment, why its current behavior is fine.
There are a few existing callers, that are definitely expecting that
this macro checks a pin, which it doesn't do.
I don't quite understand if that already causes any subtle bug, or the
current algorithm is fine.

Peter, Tom, what do you think?

--
Anastasia Lubennikova
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Fri, Aug 23, 2019 at 10:14 AM Anastasia Lubennikova
<a.lubennikova@postgrespro.ru> wrote:

Though, I got interested in the comment inconsistency you have found.
I added debug message into this code branch of the patch and was able to
see it in regression.diffs after 'make check':
Speaking of your patch, it seems that the buffer was unpinned and pinned
again between two reads,
and the condition of holding it continuously has not been met.

See commit 2ed5b87f. The code is supposed to do that, but it might do
it more often than is truly necessary. We don't want to block VACUUM
by holding a buffer pin for a very long time, which is theoretically
possible here. Do you think that it is actually unnecessary here? In
other words, do you think that we can fix this without breaking cases
that commit 2ed5b87f cares about?

I have been suspicious of this commit all along. For example, I
noticed that it can cause the kill_prior_tuple mechanism to be
ineffective in a way that didn't happen prior to Postgres 9.5:

/messages/by-id/CAH2-Wz=SfAKVMv1x9Jh19EJ8am8TZn9f-yECipS9HrrRqSswnA@mail.gmail.com

That particular complaint was never addressed. I meant to do more on
commit 2ed5b87f.

I didn't dig into the code, but this line looks suspicious (see my
findings about BTScanPosIsPinned below):

/* bump pin on current buffer for assignment to mark buffer */
if (BTScanPosIsPinned(so->currPos))
IncrBufferRefCount(so->currPos.buf);

While reading the code to answer your question, I noticed that
BTScanPosIsPinned macro name is misleading.
It calls BufferIsValid(), not BufferIsPinned() as one could expect.
And BufferIsValid in bufmgr.h comment explicitly states that it
shouldn't be confused with BufferIsPinned.
The same goes for BTScanPosUnpinIfPinned().

I have always hated this macro. I think that code like the specific
code you quoted might be correct, kind of, but it looks like the
author was trying to change as little as possible about the code as it
existed in 2015, rather than changing things so that everything made
sense. It looks like a messy accretion.

Let me see if I can get it straight:

We're incrementing the ref count on the buffer if and only if it is
pinned (by which we mean valid), though only when the scan is valid
(which is not the same as pinned). Whether or not we increment the
count of a valid scan doesn't affect anything else we do (i.e. we
still restore a marked position either way).

This is just awful.

I propose that we update BTScanPosIsPinned macro. Or, at least write a
comment, why its current behavior is fine.
There are a few existing callers, that are definitely expecting that
this macro checks a pin, which it doesn't do.
I don't quite understand if that already causes any subtle bug, or the
current algorithm is fine.

I think that you're right -- at a minimum, this requires more
documentation. This code is a few years old, but I still wouldn't be
surprised if it turned out to be slightly wrong in a way that was
important. We still have no way of detecting if a buffer is accessed
without a pin. There have been numerous bugs like that before. (We
have talked about teaching Valgrind to detect the case, but that never
actually happened.)

--
Peter Geoghegan

Hello,
welcome to hackers with your first patch)

Thank you.

Though, I got interested in the comment inconsistency you have found.
I added debug message into this code branch of the patch and was able to
see it in regression.diffs after 'make check':
Speaking of your patch, it seems that the buffer was unpinned and pinned
again between two reads,
and the condition of holding it continuously has not been met.

May I ask what makes you conclude that the condition of holding the pin continuously has not been met?
Your reply encouraged me to dig a little bit more into this today. First, I wanted to check if indeed the pin was continuously held by the backend or not. I added some debug info to ReleaseBuffer for this: it turned out that the pin on the buffer was definitely never released by the backend between the calls to _bt_first and _bt_next. So the buffer got compacted while the backend held a pin on it.
After some more searching I found the following code: _bt_vacuum_one_page in nbtinsert.c
This function compacts one single page without taking a super-exclusive lock. It is used during inserts to make room on a page. I verified that if I comment out the calls to this function, the compacting never happens while I have a pin on the buffer.
So I guess that answers my own question: cleaning up garbage during inserts is one of the cases where compacting may happen even while other backends hold a pin to the buffer. Perhaps this should also be more clearly phrased in the comments in eg. _bt_killitems? Because currently those comments make it look like this case never occurs.

While reading the code to answer your question, I noticed that
BTScanPosIsPinned macro name is misleading.
It calls BufferIsValid(), not BufferIsPinned() as one could expect.
And BufferIsValid in bufmgr.h comment explicitly states that it
shouldn't be confused with BufferIsPinned.
The same goes for BTScanPosUnpinIfPinned().

I agree the name is misleading. It clearly does something else than how it's named. However, I don't believe this introduces problems in these particular pieces of code, as long as the macro's are always used. BTScanPosIsPinned actually checks whether it's valid and not necessarily whether it's pinned, as you mentioned. However, any time the buffer gets unpinned using the macro BTScanPosUnpin, the buffer gets set to Invalid by the macro as well. Therefore, any consecutive call to BTScanPosIsPinned should indeed return false. It'd definitely be nice if this gets clarified in comments though.

-Floris

25.08.2019 0:59, Floris Van Nee wrote:

Though, I got interested in the comment inconsistency you have found.
I added debug message into this code branch of the patch and was able to
see it in regression.diffs after 'make check':
Speaking of your patch, it seems that the buffer was unpinned and pinned
again between two reads,
and the condition of holding it continuously has not been met.

May I ask what makes you conclude that the condition of holding the pin continuously has not been met?
Your reply encouraged me to dig a little bit more into this today. First, I wanted to check if indeed the pin was continuously held by the backend or not. I added some debug info to ReleaseBuffer for this: it turned out that the pin on the buffer was definitely never released by the backend between the calls to _bt_first and _bt_next. So the buffer got compacted while the backend held a pin on it.
After some more searching I found the following code: _bt_vacuum_one_page in nbtinsert.c
This function compacts one single page without taking a super-exclusive lock. It is used during inserts to make room on a page. I verified that if I comment out the calls to this function, the compacting never happens while I have a pin on the buffer.
So I guess that answers my own question: cleaning up garbage during inserts is one of the cases where compacting may happen even while other backends hold a pin to the buffer. Perhaps this should also be more clearly phrased in the comments in eg. _bt_killitems? Because currently those comments make it look like this case never occurs.

You're right, the pin was not released between page reads.
I also added debug to UnpinBuffer, but now I see that I had interpreted
it wrongly.

As far as I understand, the issue with your patch is that it breaks the
*scan stops "between" pages* assumption
and thus it unsafely interacts with _bt_vacuum_one_page() cleanup.

See README:

Page read locks are held only for as long as a scan is examining a page.

To minimize lock/unlock traffic, an index scan always searches a leaf page
to identify all the matching items at once, copying their heap tuple IDs
into backend-local storage.  The heap tuple IDs are then processed while
not holding any page lock within the index.  We do continue to hold a pin
on the leaf page in some circumstances, to protect against concurrent
deletions (see below).  In this state the scan is effectively stopped
"between" pages, either before or after the page it has pinned. This is
safe in the presence of concurrent insertions and even page splits, because
items are never moved across pre-existing page boundaries --- so the scan
cannot miss any items it should have seen, nor accidentally return the same
item twice.

and

Once an index tuple has been marked LP_DEAD it can actually be removed

from the index immediately; since index scans only stop "between" pages,
no scan can lose its place from such a deletion.

It seems that it contradicts the very idea of your patch, so probably we
should look for other ways to optimize this use-case.
Maybe this restriction can be relaxed for write only tables, that never
have to reread the page because of visibility, or something like that.
Also we probably can add to IndexScanDescData info about expected number
of tuples, to allow index work more optimal
and avoid the overhead for other loads.=

While reading the code to answer your question, I noticed that
BTScanPosIsPinned macro name is misleading.
It calls BufferIsValid(), not BufferIsPinned() as one could expect.
And BufferIsValid in bufmgr.h comment explicitly states that it
shouldn't be confused with BufferIsPinned.
The same goes for BTScanPosUnpinIfPinned().

I agree the name is misleading. It clearly does something else than how it's named. However, I don't believe this introduces problems in these particular pieces of code, as long as the macro's are always used. BTScanPosIsPinned actually checks whether it's valid and not necessarily whether it's pinned, as you mentioned. However, any time the buffer gets unpinned using the macro BTScanPosUnpin, the buffer gets set to Invalid by the macro as well. Therefore, any consecutive call to BTScanPosIsPinned should indeed return false. It'd definitely be nice if this gets clarified in comments though.

That's true. It took me quite some time to understand that existing code
is correct.
There is a comment for the structure's field that claims that
BufferIsValid is the same that BufferIsPinned in ScanPos context.
Attached patch contains some comments' updates. Any suggestions on how
to improve them are welcome.

--
Anastasia Lubennikova
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

It seems that it contradicts the very idea of your patch, so probably we
should look for other ways to optimize this use-case.
Maybe this restriction can be relaxed for write only tables, that never
have to reread the page because of visibility, or something like that.
Also we probably can add to IndexScanDescData info about expected number
of tuples, to allow index work more optimal
and avoid the overhead for other loads.=

The idea of the patch is exactly to relax this limitation. I forgot to update that README file though. The current implementation of the patch should be correct like this - that's why I added the look-back code on the page if the tuple couldn't be found anymore on the same location on the page. Similarly, it'll look on the page to the right if it detected a page split. These two measures combined should give a correct implementation of the 'it's possible that a scan stops in the middle of a page' relaxation. However, as Peter and Tom pointed out earlier, they feel that the performance advantage that this approach gives, does not outweigh the extra complexity at this time. I'd be open to other suggestions though.

That's true. It took me quite some time to understand that existing code
is correct.
There is a comment for the structure's field that claims that
BufferIsValid is the same that BufferIsPinned in ScanPos context.
Attached patch contains some comments' updates. Any suggestions on how
to improve them are welcome.

I'll have a look tomorrow. Thanks a lot for writing this up!

-Floris

It seems that it contradicts the very idea of your patch, so probably we
should look for other ways to optimize this use-case.
Maybe this restriction can be relaxed for write only tables, that never
have to reread the page because of visibility, or something like that.
Also we probably can add to IndexScanDescData info about expected number
of tuples, to allow index work more optimal
and avoid the overhead for other loads.=

The idea of the patch is exactly to relax this limitation. I forgot to update that README file though. The current implementation of the patch should be correct like this - that's why I added the look-back code on the page if the tuple couldn't be found anymore on the same location on the page. Similarly, it'll look on the page to the right if it detected a page split. These two measures combined should give a correct implementation of the 'it's possible that a scan stops in the middle of a page' relaxation. However, as Peter and Tom pointed out earlier, they feel that the performance advantage that this approach gives, does not outweigh the extra complexity at this time. I'd be open to other suggestions though.

Although now that I think of it - do you mean the case where the tuple that we returned to the caller after _bt_first actually gets deleted (not moved) from the page? I guess that can theoretically happen if _bt_first returns a non-visible tuple (but not DEAD yet in the index at the time of _bt_first). For my understanding, would a situation like the following lead to this (in my patch)?
1) Backend 1 does an index scan and returns the first tuple on _bt_first - this tuple is actually deleted in the heap already, however it's not marked dead yet in the index.
2) Backend 1 does a heap fetch to check actual visibility and determines the tuple is actually dead
3) While backend 1 is busy doing the heap fetch (so in between _bt_first and _bt_next) backend 2 comes in and manages to somehow do 1) a _bt_killitems on the page to mark tuples dead as well as 2) compact items on the page, thereby actually removing this item from the page.
4) Now backend 1 tries to find the next tuple in _bt_next - it first tries to locate the tuple where it left off, but cannot find it anymore because it got removed completely by backend 2.

If this is indeed possible then it's a bad issue unfortunately, and quite hard to try to reproduce, as a lot of things need to happen concurrently while doing a visiblity check.

As for your patch, I've had some time to take a look at it. For the two TODOs:

+		/* TODO Is it possible that currPage is not valid anymore? */
+		Assert(BTScanPosIsValid(so->currPos))

This Assert exists already a couple of lines earlier at the start of this function.

+ * TODO It is not clear to me
+ * why to check scanpos validity based on currPage value.
+ * I wonder, if we need currPage at all? Is there any codepath that
+ * assumes that currPage is not the same as BufferGetBlockNumber(buf)?
+ */

The comments in the source mention the following about this:
* We note the buffer's block number so that we can release the pin later.
* This allows us to re-read the buffer if it is needed again for hinting.
*/
so->currPos.currPage = BufferGetBlockNumber(so->currPos.buf);

As we figured out earlier, so->currPos.buf gets set to invalid when we release the pin by the unpin macro. So, if we don't store currPage number somewhere else, we cannot obtain the pin again if we need it during killitems. I think that's the reason that currPage is stored.

Other than the two TODOs in the code, I think the comments really help clarifying what's going on in the code - I'd be happy if this gets added.

-Floris