ERROR: found unexpected null value in index

On Tue, Jul 9, 2019 at 4:52 PM Manuel Rigger <rigger.manuel@gmail.com> wrote:

CREATE TABLE t0(c0 TEXT);
INSERT INTO t0(c0) VALUES('b'), ('a');
ANALYZE;
INSERT INTO t0(c0) VALUES (NULL);
UPDATE t0 SET c0 = 'a';
CREATE INDEX i0 ON t0(c0);
SELECT * FROM t0 WHERE 'baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'

t0.c0; -- unexpected: ERROR: found unexpected null value in index

"i0"

The SELECT can result in "ERROR: found unexpected null value in index
"i0"". I could reproduce this error only when some actions on other
databases are performed. The error is rather difficult to reproduce,
and small changes to the above statements cause it to no longer be
reproducible on my machine.

The error comes from a point at which the planner accesses the index
before execution proper, within get_actual_variable_range(). Perhaps
commit 3ca930fc39c is to blame.

--
Peter Geoghegan

Manuel Rigger <rigger.manuel@gmail.com> writes:

CREATE TABLE t0(c0 TEXT);
INSERT INTO t0(c0) VALUES('b'), ('a');
ANALYZE t0;
INSERT INTO t0(c0) VALUES (NULL);
UPDATE t0 SET c0 = 'a';
CREATE INDEX i0 ON t0(c0);
SELECT * FROM t0 WHERE 'baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' > t0.c0;
-- unexpected: ERROR: found unexpected null value in index "i0"

Nifty. As before, the way to make this reproducible is to do it with
another open transaction holding a snapshot, so that the NULL entry
has to be reflected in the index. (I'm not sure why the HOT-update
exception doesn't apply here, but apparently it doesn't.) That is,
it's sufficient to set up one session with

begin transaction isolation level serializable;
select * from some_table;

and then run the above script in another session.

The error is coming from the planner's get_actual_variable_range:

/* Shouldn't have got a null, but be careful */
if (isnull[0])
elog(ERROR, "found unexpected null value in index \"%s\"",
RelationGetRelationName(indexRel));

and I think it's entirely within its rights to complain, because it
set up the scan key to reject nulls. In short, somebody seems to
have broken btrees' processing of SK_ISNULL | SK_SEARCHNOTNULL scankeys,
and they broke it in v11, because prior versions don't show this failure.

regards, tom lane

On Tue, Jul 9, 2019 at 6:08 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

The error is coming from the planner's get_actual_variable_range:

/* Shouldn't have got a null, but be careful */
if (isnull[0])
elog(ERROR, "found unexpected null value in index \"%s\"",
RelationGetRelationName(indexRel));

and I think it's entirely within its rights to complain, because it
set up the scan key to reject nulls. In short, somebody seems to
have broken btrees' processing of SK_ISNULL | SK_SEARCHNOTNULL scankeys,
and they broke it in v11, because prior versions don't show this failure.

It's not obvious to me why that might be. I'll run a "git bisect" to
track down the offending commit.

--
Peter Geoghegan

Peter Geoghegan <pg@bowt.ie> writes:

On Tue, Jul 9, 2019 at 6:08 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

The error is coming from the planner's get_actual_variable_range:
and I think it's entirely within its rights to complain, because it
set up the scan key to reject nulls. In short, somebody seems to
have broken btrees' processing of SK_ISNULL | SK_SEARCHNOTNULL scankeys,
and they broke it in v11, because prior versions don't show this failure.

It's not obvious to me why that might be. I'll run a "git bisect" to
track down the offending commit.

I just finished doing that, and indeed it fingers 3ca930fc3 as the
first bad commit. Seems like it must have exposed a pre-existing
problem though? Too tired to look further tonight.

regards, tom lane

On Tue, Jul 9, 2019 at 6:43 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

I just finished doing that, and indeed it fingers 3ca930fc3 as the
first bad commit. Seems like it must have exposed a pre-existing
problem though?

I think that the issue is related to a broken HOT chain -- the index
doesn't even have any NULL key values, since the CREATE INDEX came
after the INSERT that added a NULL value. However, it does have a
tuple with the key value 'a' that points to the root of a HOT chain
whose first value for the indexed attribute is NULL. The successor
tuple's value for the indexed attribute is 'a', as expected (of
course, this is a normal state that
IndexBuildHeapScan()/heapam_index_build_range_scan() expect other code
to deal with).

Back when get_actual_variable_range() used a dirty snapshot, it would
have not seen any NULL value with this test case, because the root of
the HOT chain would be considered recently dead.

--
Peter Geoghegan

Peter Geoghegan <pg@bowt.ie> writes:

I think that the issue is related to a broken HOT chain -- the index
doesn't even have any NULL key values, since the CREATE INDEX came
after the INSERT that added a NULL value. However, it does have a
tuple with the key value 'a' that points to the root of a HOT chain
whose first value for the indexed attribute is NULL. The successor
tuple's value for the indexed attribute is 'a', as expected (of
course, this is a normal state that
IndexBuildHeapScan()/heapam_index_build_range_scan() expect other code
to deal with).

Back when get_actual_variable_range() used a dirty snapshot, it would
have not seen any NULL value with this test case, because the root of
the HOT chain would be considered recently dead.

Hm. So maybe we need to teach it to ignore tuples that are not the tips
of their HOT chains?

regards, tom lane

On Tue, Jul 9, 2019 at 7:47 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Back when get_actual_variable_range() used a dirty snapshot, it would
have not seen any NULL value with this test case, because the root of
the HOT chain would be considered recently dead.

Hm. So maybe we need to teach it to ignore tuples that are not the tips
of their HOT chains?

An approach like that was the first thing that I thought of, but I'll
have to study the problem some more before coming up with a firm
opinion.

--
Peter Geoghegan

Peter Geoghegan <pg@bowt.ie> writes:

On Tue, Jul 9, 2019 at 7:47 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Hm. So maybe we need to teach it to ignore tuples that are not the tips
of their HOT chains?

An approach like that was the first thing that I thought of, but I'll
have to study the problem some more before coming up with a firm
opinion.

I experimented with the attached. It solves the reported problem and
passes check-world. I made it just ignore any tuple for which
HeapTupleHeaderIsHotUpdated is true. It might seem like there's a risk
of ignoring valid data, if the end tuple of a HOT chain is dead due to
a transaction abort, but since HeapTupleHeaderIsHotUpdated checks for
xmax validity I judge that the risk of that is small enough to be
acceptable.

A bigger problem with this is that in the tableam world, this seems
like a complete disaster modularity-wise. I think it won't actually
fail --- non-heap AMs are probably not returning
BufferHeapTupleTableSlots, and even if they are, they shouldn't be
marking tuples HOT_UPDATED unless that concept applies to them.
But it sure seems like this leaves get_actual_variable_range() knowing
way more than it ought to about storage-level concerns.

Should we try to transpose some of this logic to below the AM API,
and if so, what should that look like?

regards, tom lane

Hi,

On 2019-07-10 16:02:50 -0400, Tom Lane wrote:

A bigger problem with this is that in the tableam world, this seems
like a complete disaster modularity-wise. I think it won't actually
fail --- non-heap AMs are probably not returning
BufferHeapTupleTableSlots, and even if they are, they shouldn't be
marking tuples HOT_UPDATED unless that concept applies to them.
But it sure seems like this leaves get_actual_variable_range() knowing
way more than it ought to about storage-level concerns.

Yea, I think that's not pretty. I'm not concerned about wrong results
due to BufferHeapTupleTableSlots being returned, and misinterpreted, but
layering wise this seems not good. Even leaving tableam aside, it seems
not nice to have this concern leak into selfuncs.c

Should we try to transpose some of this logic to below the AM API,
and if so, what should that look like?

I wonder if we could push this down into a separate type of visibility
(or maybe redefine NonVacuumable)? So that the scan wouldn't ever
return them in the first place? It's a bit annoying to have a visibility
type that's perhaps best called "what selfuncs.c needs", but still seams
cleaner than having a separate callback? And the explanation for why
that's possibly needed also seems to better belong inside the AMs.

- Andres

Andres Freund <andres@anarazel.de> writes:

On 2019-07-10 16:02:50 -0400, Tom Lane wrote:

Should we try to transpose some of this logic to below the AM API,
and if so, what should that look like?

I wonder if we could push this down into a separate type of visibility
(or maybe redefine NonVacuumable)? So that the scan wouldn't ever
return them in the first place? It's a bit annoying to have a visibility
type that's perhaps best called "what selfuncs.c needs", but still seams
cleaner than having a separate callback? And the explanation for why
that's possibly needed also seems to better belong inside the AMs.

SnapshotNonVacuumable is already basically "what selfuncs.c needs" ---
nothing else is using it. So I wouldn't hesitate to redefine it if
that'd fix the problem. But it doesn't sound like a promising approach.
The problem here isn't whether the heap tuple is live or dead, it's
whether it can be trusted to match the index entry. Also, snapshot
checking isn't really below the AM API anyway is it?

I wonder if we'd be better off to switch over to using data directly
from the index entry, rather than trying to recover it from the heap.
We'd then need to make sure that the logic exploits btree's "killed
index entry" ability, so that dead extremal values are ignored as
much as possible. But that'd get us out of the broken-HOT-chain
problem.

regards, tom lane

Hi,

On July 10, 2019 1:25:49 PM PDT, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Andres Freund <andres@anarazel.de> writes:

On 2019-07-10 16:02:50 -0400, Tom Lane wrote:

Should we try to transpose some of this logic to below the AM API,
and if so, what should that look like?

I wonder if we could push this down into a separate type of

visibility

(or maybe redefine NonVacuumable)? So that the scan wouldn't ever
return them in the first place? It's a bit annoying to have a

visibility

type that's perhaps best called "what selfuncs.c needs", but still

seams

cleaner than having a separate callback? And the explanation for why
that's possibly needed also seems to better belong inside the AMs.

SnapshotNonVacuumable is already basically "what selfuncs.c needs" ---
nothing else is using it. So I wouldn't hesitate to redefine it if
that'd fix the problem. But it doesn't sound like a promising
approach.
The problem here isn't whether the heap tuple is live or dead, it's
whether it can be trusted to match the index entry.

Well, if we defined i the snapshot semantics as "return rows that are not vacuumable and safe for selfuncs.c considerations" it seems like a visibility concern if you squint a tiny bit. It's a mostly checking for certain kinds of dead rows, after all.

Also, snapshot
checking isn't really below the AM API anyway is it?

It is, imo. Scans callbacks are expected to only return visible rows. And if a tuple in a slot needs to be checked for visibility later, that goes through a callback. Don't see how you could otherwise make different non-pgheap storages work.

I wonder if we'd be better off to switch over to using data directly
from the index entry, rather than trying to recover it from the heap.
We'd then need to make sure that the logic exploits btree's "killed
index entry" ability, so that dead extremal values are ignored as
much as possible. But that'd get us out of the broken-HOT-chain
problem.

Hm, that doesn't sound like a trivial change. Not at my computer for 20min, so can't check rn, but does the index entry always have all the information we need?

Andres

Andres
--
Sent from my Android device with K-9 Mail. Please excuse my brevity.

Andres Freund <andres@anarazel.de> writes:

On July 10, 2019 1:25:49 PM PDT, Tom Lane <tgl@sss.pgh.pa.us> wrote:

The problem here isn't whether the heap tuple is live or dead, it's
whether it can be trusted to match the index entry.

Well, if we defined i the snapshot semantics as "return rows that are not vacuumable and safe for selfuncs.c considerations" it seems like a visibility concern if you squint a tiny bit. It's a mostly checking for certain kinds of dead rows, after all.

Hm, maybe. I was considering making it work like "apply
SnapshotNonVacuumable if the tuple isn't HOT_UPDATED, but some stricter
liveness check if it is". It didn't seem like there was much to be gained
that way given how HeapTupleHeaderIsHotUpdated works ... or, perhaps,
you could say that HeapTupleHeaderIsHotUpdated is already applying a very
strict liveness check.

Also, snapshot
checking isn't really below the AM API anyway is it?

It is, imo.

Ah, I see HeapTupleSatisfiesVisibility has already been pushed down
below that horizon. So I agree, we might be able to finesse this by
pushing the hot-update consideration into HeapTupleSatisfiesNonVacuumable,
or making another snapshot_type that does what we need.

I wonder if we'd be better off to switch over to using data directly
from the index entry, rather than trying to recover it from the heap.

Hm, that doesn't sound like a trivial change.

Not sure. We know we're dealing with btree, and it can always do
index-only scans, so it's certainly possible. But the relevant
APIs might not be conducive to getting what we want.

regards, tom lane

On Wed, Jul 10, 2019 at 1:25 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

I wonder if we'd be better off to switch over to using data directly
from the index entry, rather than trying to recover it from the heap.
We'd then need to make sure that the logic exploits btree's "killed
index entry" ability, so that dead extremal values are ignored as
much as possible. But that'd get us out of the broken-HOT-chain
problem.

I continue to have concerns about the effectiveness of the
kill_prior_tuple mechanism on 9.5+:

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

Maybe that problem has nothing to do with what you said, but I was
reminded of the fact that it's far from clear how effective
kill_prior_tuple actually is in the real world (i.e. with
concurrency). I guess that your suggestion would make it even less
likely that LP_DEAD hint bits would be set by
get_actual_variable_range() scans, because there would be no
opportunity to check the heap. Wasn't one of the goals of commit
3ca930fc39c to make it more likely that extrema values would be killed
by get_actual_variable_range() scans, for the benefit of future
get_actual_variable_range() scans?

--
Peter Geoghegan

Peter Geoghegan <pg@bowt.ie> writes:

On Wed, Jul 10, 2019 at 1:25 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

I wonder if we'd be better off to switch over to using data directly
from the index entry, rather than trying to recover it from the heap.

Maybe that problem has nothing to do with what you said, but I was
reminded of the fact that it's far from clear how effective
kill_prior_tuple actually is in the real world (i.e. with
concurrency). I guess that your suggestion would make it even less
likely that LP_DEAD hint bits would be set by
get_actual_variable_range() scans, because there would be no
opportunity to check the heap.

I was imagining it would still check the heap, if necessary, to verify
that it'd found a tuple passing the given snapshot.

Wasn't one of the goals of commit
3ca930fc39c to make it more likely that extrema values would be killed
by get_actual_variable_range() scans, for the benefit of future
get_actual_variable_range() scans?

Yes, and my point was that we still need that effect in some form. But
once we've found that there's a tuple that's "live enough" (for some
definition of that) we could pull the actual data from the index not heap.

regards, tom lane

On Wed, Jul 10, 2019 at 3:26 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

I was imagining it would still check the heap, if necessary, to verify
that it'd found a tuple passing the given snapshot.

Not sure I follow. When or how would it not be necessary? Are you
merely referring to the simple case where the LP_DEAD bit is already
set for the item on the B-Tree leaf page?

Wasn't one of the goals of commit
3ca930fc39c to make it more likely that extrema values would be killed
by get_actual_variable_range() scans, for the benefit of future
get_actual_variable_range() scans?

Yes, and my point was that we still need that effect in some form. But
once we've found that there's a tuple that's "live enough" (for some
definition of that) we could pull the actual data from the index not heap.

I think I follow -- that would do the right thing, without requiring
selfuncs.c to know about HOT, or some similar mechanism in an
alternative table AM.

--
Peter Geoghegan

Peter Geoghegan <pg@bowt.ie> writes:

On Wed, Jul 10, 2019 at 3:26 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

I was imagining it would still check the heap, if necessary, to verify
that it'd found a tuple passing the given snapshot.

Not sure I follow. When or how would it not be necessary? Are you
merely referring to the simple case where the LP_DEAD bit is already
set for the item on the B-Tree leaf page?

Index-only scans already have the LP_DEAD fast path (don't return value)
and the all_visible fast path (always return value), and otherwise they
do a heap visit. If we can use a custom visibility test in the heap
visit and not muck up the opportunity to set LP_DEAD when relevant, then
it seems like using the IOS code path will do exactly what we want.
Otherwise some finagling might be necessary. But it still might be
cleaner than directly looking at HOT-update status.

I'll take a look at that tomorrow if nobody beats me to it.

regards, tom lane

I wrote:

Index-only scans already have the LP_DEAD fast path (don't return value)
and the all_visible fast path (always return value), and otherwise they
do a heap visit. If we can use a custom visibility test in the heap
visit and not muck up the opportunity to set LP_DEAD when relevant, then
it seems like using the IOS code path will do exactly what we want.
Otherwise some finagling might be necessary. But it still might be
cleaner than directly looking at HOT-update status.

I'll take a look at that tomorrow if nobody beats me to it.

As far as I can tell, no special finagling is needed: if we just use
the regular index-only-scan logic then this all works the way we want,
and it's actually better than before because we get to skip heap visits
altogether when dealing with unchanging data. Attached is a patch
against HEAD that seems to do all the right things.

I'm a little dissatisfied with the fact that I had to duplicate the
all-visible checking logic out of nodeIndexonlyscan.c. Maybe we should
think about refactoring to avoid multiple copies of that? But that's
probably a task for a separate patch, if it's practical at all.

regards, tom lane

On Thu, Jul 11, 2019 at 2:20 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

As far as I can tell, no special finagling is needed: if we just use
the regular index-only-scan logic then this all works the way we want,
and it's actually better than before because we get to skip heap visits
altogether when dealing with unchanging data. Attached is a patch
against HEAD that seems to do all the right things.

Interesting approach. I certainly prefer it to the alternative
approach of framing the problem as a visibility concern.

I'm a little dissatisfied with the fact that I had to duplicate the
all-visible checking logic out of nodeIndexonlyscan.c. Maybe we should
think about refactoring to avoid multiple copies of that? But that's
probably a task for a separate patch, if it's practical at all.

I suspect that you'd end up writing more code than you'd save if you
generalized what we already have. Not clear that that's worth it.

--
Peter Geoghegan

Peter Geoghegan <pg@bowt.ie> writes:

On Thu, Jul 11, 2019 at 2:20 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

As far as I can tell, no special finagling is needed: if we just use
the regular index-only-scan logic then this all works the way we want,
and it's actually better than before because we get to skip heap visits
altogether when dealing with unchanging data. Attached is a patch
against HEAD that seems to do all the right things.

Interesting approach. I certainly prefer it to the alternative
approach of framing the problem as a visibility concern.

Yes, I certainly like this better than my previous attempt.

I still feel like we're going to want to push (most of?) this logic
below the tableam API at some point, because its implementation was
and remains tied to heap+btree. But other table AMs are likely to
support ordered scan accesses of some sort, and they're going to
want to be able to adjust the planner's extremal-value estimates
too. It's a job for later though.

regards, tom lane