Synchronized scans

Heikki Linnakangas <heikki@enterprisedb.com> writes:

For the record, this patch has a small negative impact on scans like
"SELECT * FROM foo LIMIT 1000". If such a scan is run repeatedly, in CVS
HEAD the first 1000 rows will stay in buffer cache, but with the patch
each scan will start from roughly where previous one stopped, requiring
more pages to be read from disk each time. I don't think it's something
to worry about in practice, but I thought I'd mention it.

Urgh. The answers change depending on (more or less) the phase of the
moon? I've got a serious problem with that. You might look back to
1997 when GEQO very nearly got tossed out entirely because it destroyed
reproducibility of query results.

regards, tom lane

Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

For the record, this patch has a small negative impact on scans like
"SELECT * FROM foo LIMIT 1000". If such a scan is run repeatedly, in CVS
HEAD the first 1000 rows will stay in buffer cache, but with the patch
each scan will start from roughly where previous one stopped, requiring
more pages to be read from disk each time. I don't think it's something
to worry about in practice, but I thought I'd mention it.

Urgh. The answers change depending on (more or less) the phase of the
moon? I've got a serious problem with that. You might look back to
1997 when GEQO very nearly got tossed out entirely because it destroyed
reproducibility of query results.

That's a very fundamental result of this patch, unfortunately. It only
happens on scans on tables larger than the threshold. And because we
only report the current scan location every 128KB, if you repeat the
same SELECT .. LIMIT X query with no other scanners on that table,
you'll get the same results as long as X is smaller than 128KB.

I thought we've been through this issue already...

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas wrote:

Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

For the record, this patch has a small negative impact on scans like
"SELECT * FROM foo LIMIT 1000". If such a scan is run repeatedly, in CVS
HEAD the first 1000 rows will stay in buffer cache, but with the patch
each scan will start from roughly where previous one stopped, requiring
more pages to be read from disk each time. I don't think it's something
to worry about in practice, but I thought I'd mention it.

Urgh. The answers change depending on (more or less) the phase of the
moon? I've got a serious problem with that. You might look back to
1997 when GEQO very nearly got tossed out entirely because it destroyed
reproducibility of query results.

That's a very fundamental result of this patch, unfortunately. It only
happens on scans on tables larger than the threshold. And because we
only report the current scan location every 128KB, if you repeat the
same SELECT .. LIMIT X query with no other scanners on that table,
you'll get the same results as long as X is smaller than 128KB.

I thought we've been through this issue already...

Agreed. I thought we always said that a LIMIT without an ORDER BY was
meaningless, particuarly because an intervening UPDATE could have moved
rows to another place in the table. In fact, at one time we considered
prevening LIMIT without ORDER BY because it was meaningless, but decided
if people want unstable results, they should be able to get them.

An argument could be made that a LIMIT without ORDER BY on a table
locked read-only should be stable.

As I understand it, the problem is that while currently LIMIT without
ORDER BY always starts at the beginning of the table, it will not with
this patch. I consider that acceptable.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Bruce Momjian <bruce@momjian.us> writes:

As I understand it, the problem is that while currently LIMIT without
ORDER BY always starts at the beginning of the table, it will not with
this patch. I consider that acceptable.

It's definitely going to require stronger warnings than we have now
about using LIMIT without ORDER BY.

regards, tom lane

Tom Lane wrote:

Bruce Momjian <bruce@momjian.us> writes:

As I understand it, the problem is that while currently LIMIT without
ORDER BY always starts at the beginning of the table, it will not with
this patch. I consider that acceptable.

It's definitely going to require stronger warnings than we have now
about using LIMIT without ORDER BY.

Along the lines of

NOTICE: LIMIT without ORDER BY returns an arbitrary set of matching rows

perhaps? I wonder how easy it is to detect that in the planner.

Or just a remark in the manual?

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

On Mon, 2007-06-04 at 10:53 +0100, Heikki Linnakangas wrote:

I'm now done with this patch and testing it.

Great!

For the record, this patch has a small negative impact on scans like
"SELECT * FROM foo LIMIT 1000". If such a scan is run repeatedly, in CVS
HEAD the first 1000 rows will stay in buffer cache, but with the patch
each scan will start from roughly where previous one stopped, requiring
more pages to be read from disk each time. I don't think it's something
to worry about in practice, but I thought I'd mention it.

No surprise here, as you and Bruce have already pointed out.

If we wanted to reduce the occurrence of this phenomena, we could
perhaps "time out" the hints so that it's impossible to pick up a hint
from a scan that finished 5 minutes ago.

It doesn't seem helpful to further obscure the non-determinism of the
results, however.

Regards,
Jeff Davis

Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

For the record, this patch has a small negative impact on scans like
"SELECT * FROM foo LIMIT 1000". If such a scan is run repeatedly, in CVS
HEAD the first 1000 rows will stay in buffer cache, but with the patch
each scan will start from roughly where previous one stopped, requiring
more pages to be read from disk each time. I don't think it's something
to worry about in practice, but I thought I'd mention it.

Urgh. The answers change depending on (more or less) the phase of the
moon? I've got a serious problem with that. You might look back to
1997 when GEQO very nearly got tossed out entirely because it destroyed
reproducibility of query results.

What about the simple idea of just disabling the use of a sync scan when
the query has LIMIT and no ORDER BY, and start always at block 0 in that
case?

--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

Alvaro Herrera wrote:

Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

For the record, this patch has a small negative impact on scans like
"SELECT * FROM foo LIMIT 1000". If such a scan is run repeatedly, in CVS
HEAD the first 1000 rows will stay in buffer cache, but with the patch
each scan will start from roughly where previous one stopped, requiring
more pages to be read from disk each time. I don't think it's something
to worry about in practice, but I thought I'd mention it.

Urgh. The answers change depending on (more or less) the phase of the
moon? I've got a serious problem with that. You might look back to
1997 when GEQO very nearly got tossed out entirely because it destroyed
reproducibility of query results.

What about the simple idea of just disabling the use of a sync scan when
the query has LIMIT and no ORDER BY, and start always at block 0 in that
case?

That handles the LIMIT case, but you would still observe the different
ordering. And some people do LIMIT-like behavior in client side, by
opening a cursor and only fetching first n rows.

I don't think anyone can reasonably expect to get the same ordering when
the same query issued twice in general, but within the same transaction
it wouldn't be that unreasonable. If we care about that, we could keep
track of starting locations per transaction, only do the synchronization
on the first scan in a transaction, and start subsequent scans from the
same page as the first one. That way if you issue the same query twice
in a transaction, or do something like:
BEGIN;
SELECT * FROM queue FOR UPDATE LIMIT 10
do stuff..
DELETE FROM queue LIMIT 10
COMMIT;

you'd get the expected result.

I think the warning on LIMIT without ORDER BY is a good idea, regardless
of the synchronized scans patch.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Jeff Davis wrote:

No surprise here, as you and Bruce have already pointed out.

If we wanted to reduce the occurrence of this phenomena, we could
perhaps "time out" the hints so that it's impossible to pick up a hint
from a scan that finished 5 minutes ago.

It doesn't seem helpful to further obscure the non-determinism of the
results, however.

I agree it's probably not a good idea to try masking this. It'll just
make it harder to hit the issue in testing, so that you run into it in
production.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas <heikki@enterprisedb.com> writes:

I don't think anyone can reasonably expect to get the same ordering when
the same query issued twice in general, but within the same transaction
it wouldn't be that unreasonable. If we care about that, we could keep
track of starting locations per transaction, only do the synchronization
on the first scan in a transaction, and start subsequent scans from the
same page as the first one.

I think the real problem here is that the first scan is leaving state
behind that changes the behavior of the next scan. Which can have no
positive benefit, since obviously the first scan is not still
proceeding; the best you can hope for is that it's a no-op and the worst
case is that it actively pessimizes things. Why doesn't the patch
remove the shmem entry at scan termination?

I think the warning on LIMIT without ORDER BY is a good idea, regardless
of the synchronized scans patch.

I seriously doubt that can be done in any way that doesn't both warn
about perfectly-safe cases and fail to warn about other unsafe ones.
Furthermore, it's not uncommon for people to do "SELECT * ... LIMIT 1"
just to remind themselves of column names or whatever. Do we really
want the thing to be so nannyish? I was envisioning simply a stronger
warning in the SELECT reference page ...

regards, tom lane

Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

I don't think anyone can reasonably expect to get the same ordering when
the same query issued twice in general, but within the same transaction
it wouldn't be that unreasonable. If we care about that, we could keep
track of starting locations per transaction, only do the synchronization
on the first scan in a transaction, and start subsequent scans from the
same page as the first one.

I think the real problem here is that the first scan is leaving state
behind that changes the behavior of the next scan. Which can have no
positive benefit, since obviously the first scan is not still
proceeding; the best you can hope for is that it's a no-op and the worst
case is that it actively pessimizes things. Why doesn't the patch
remove the shmem entry at scan termination?

Because there's no reason why it should, and it would require a lot more
bookkeeping. There can be many scanners on the same table, so we'd need
to implement some kind of reference counting, which means having to
reliably decrement the counter when a scan terminates.

In any case if there actually is a concurrent scan, you'd still see
different ordering. Removing the entry when a scan is over would just
make it harder to trigger.

I think the warning on LIMIT without ORDER BY is a good idea, regardless
of the synchronized scans patch.

I seriously doubt that can be done in any way that doesn't both warn
about perfectly-safe cases and fail to warn about other unsafe ones.
Furthermore, it's not uncommon for people to do "SELECT * ... LIMIT 1"
just to remind themselves of column names or whatever. Do we really
want the thing to be so nannyish?

It really depends on how many false negatives and positives it gives. If
too many, it's just annoying, but if it's reasonably accurate I think it
would be OK to remind people running queries like that.

I was envisioning simply a stronger warning in the SELECT reference page ...

I doubt the people that would be bitten by this read the SELECT
reference page.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

On Jun 4, 2007, at 15:24 , Heikki Linnakangas wrote:

I don't think anyone can reasonably expect to get the same ordering
when the same query issued twice in general, but within the same
transaction it wouldn't be that unreasonable.

The order rows are returned without an ORDER BY clause *is*
implementation dependent, and is not guaranteed, at least by the
spec. Granted, LIMIT without ORDER BY (and DISTINCT for that matter)
brings this into sharp relief.

I think the warning on LIMIT without ORDER BY is a good idea,
regardless of the synchronized scans patch.

I'm not saying this isn't a good idea, but are there other places
where there might be gotchas for the unwary, such as DISTINCT without
ORDER BY or (for an unrelated example) UNION versus UNION ALL? How
many of these types of messages would be useful?

Michael Glaesemann
grzm seespotcode net

On Mon, 2007-06-04 at 16:42 -0400, Tom Lane wrote:

Heikki Linnakangas <heikki@enterprisedb.com> writes:

I don't think anyone can reasonably expect to get the same ordering when
the same query issued twice in general, but within the same transaction
it wouldn't be that unreasonable. If we care about that, we could keep
track of starting locations per transaction, only do the synchronization
on the first scan in a transaction, and start subsequent scans from the
same page as the first one.

I think the real problem here is that the first scan is leaving state
behind that changes the behavior of the next scan. Which can have no
positive benefit, since obviously the first scan is not still
proceeding; the best you can hope for is that it's a no-op and the worst
case is that it actively pessimizes things. Why doesn't the patch
remove the shmem entry at scan termination?

Sounds like a reasonable idea to me. We could add the PID to the data
structure so that it would only remove the hint if it's the one that set
the hint. I think we'd just need to call a function to do that from
heap_endscan(), correct?

However, we couldn't 100% guarantee that the state would be cleared. A
backend could be killed in the middle of a scan.

The case you're worried about seems very narrow to me, and I think
"actively pessimizes" is too strong. Unless I misunderstand, "the best
you can hope for" no-op happens in all cases except a most bizarre one:
that in which you're executing repeated identical LIMIT queries with no
ORDER BY; and the tuples returned occupy more than 128K (16 pages is the
reporting period) but fewer would be effective to cache; and the table
in question is larger than the large table threshold. I'm just trying to
add some perspective about what we're fixing, here.

But it's fair to say that a scan should clear any state when it's done.

Regards,
Jeff Davis

Michael Glaesemann wrote:

I think the warning on LIMIT without ORDER BY is a good idea,
regardless of the synchronized scans patch.

I'm not saying this isn't a good idea, but are there other places where
there might be gotchas for the unwary, such as DISTINCT without ORDER BY
or (for an unrelated example) UNION versus UNION ALL? How many of these
types of messages would be useful?

LIMIT without ORDER BY is worse because it not only returns tuples in
different order, but it can return different tuples altogether when you
run it multiple times.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

On Mon, 2007-06-04 at 22:09 +0100, Heikki Linnakangas wrote:

I think the real problem here is that the first scan is leaving state
behind that changes the behavior of the next scan. Which can have no
positive benefit, since obviously the first scan is not still
proceeding; the best you can hope for is that it's a no-op and the worst
case is that it actively pessimizes things. Why doesn't the patch
remove the shmem entry at scan termination?

Because there's no reason why it should, and it would require a lot more
bookkeeping. There can be many scanners on the same table, so we'd need
to implement some kind of reference counting, which means having to
reliably decrement the counter when a scan terminates.

That's what I thought at first, and why I didn't do it. Right now I'm
thinking we could just add the PID to the hint, so that it would only
remove its own hint. Would that work?

It's still vulnerable to a backend being killed and the hint hanging
around. However, the next scan would clear get it back to normal.
Reference counting would cause weirdness if a backend died or something,
because it would never decrement to 0.

In any case if there actually is a concurrent scan, you'd still see
different ordering. Removing the entry when a scan is over would just
make it harder to trigger.

Agreed. I don't know for sure whether that's good or bad, but it would
make the nondeterminism less immediately visible.

Regards,
Jeff Davis

Jeff Davis wrote:

On Mon, 2007-06-04 at 22:09 +0100, Heikki Linnakangas wrote:

I think the real problem here is that the first scan is leaving state
behind that changes the behavior of the next scan. Which can have no
positive benefit, since obviously the first scan is not still
proceeding; the best you can hope for is that it's a no-op and the worst
case is that it actively pessimizes things. Why doesn't the patch
remove the shmem entry at scan termination?

Because there's no reason why it should, and it would require a lot more
bookkeeping. There can be many scanners on the same table, so we'd need
to implement some kind of reference counting, which means having to
reliably decrement the counter when a scan terminates.

That's what I thought at first, and why I didn't do it. Right now I'm
thinking we could just add the PID to the hint, so that it would only
remove its own hint. Would that work?

Were you thinking of storing the PID of the backend that originally
created the hint, or updating the PID every time the hint is updated? In
any case, we still wouldn't know if there's other scanners still running.

We could just always remove the hint when a scan ends, and rely on the
fact that if there's other scans still running they will put the hint
back very quickly. There would then be a small window where there's no
hint but a scan is active, and a new scan starting during that window
would fail to synchronize with the other scanners.

It's still vulnerable to a backend being killed and the hint hanging
around. However, the next scan would clear get it back to normal.

Oh, did you mean that the PID would be updated whenever a new scan
starts? So that the PID stored would always be the PID of the latest
scanner. That might work pretty well, though a small scan with a LIMIT,
or any other situation where some scans run faster than others, might
clear the hint prematurely while other scans are still running.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

On Mon, 2007-06-04 at 22:57 +0100, Heikki Linnakangas wrote:

That's what I thought at first, and why I didn't do it. Right now I'm
thinking we could just add the PID to the hint, so that it would only
remove its own hint. Would that work?

Were you thinking of storing the PID of the backend that originally
created the hint, or updating the PID every time the hint is updated? In
any case, we still wouldn't know if there's other scanners still running.

My thought was that every time the location was reported by a backend,
it would store 3 pieces of information, not 2:
* relfilenode
* the PID of the backend that created or updated this particular hint
last
* the location

Then, on heap_endscan() (if that's the right place), we find the hint,
and if the PID matches, we remove it. If not, it does nothing.

This would only matter when there weren't other scans. When concurrent
scans were happening, chances are the PID wouldn't match anyway, and
thus not be removed.

Regards,
Jeff Davis

On Jun 4, 2007, at 16:34 , Heikki Linnakangas wrote:

LIMIT without ORDER BY is worse because it not only returns tuples
in different order, but it can return different tuples altogether
when you run it multiple times.

Wouldn't DISTINCT ON suffer from the same issue without ORDER BY?

Michael Glaesemann
grzm seespotcode net

Jeff Davis <pgsql@j-davis.com> writes:

My thought was that every time the location was reported by a backend,
it would store 3 pieces of information, not 2:
* relfilenode
* the PID of the backend that created or updated this particular hint
last
* the location

Then, on heap_endscan() (if that's the right place), we find the hint,
and if the PID matches, we remove it. If not, it does nothing.

This would only matter when there weren't other scans. When concurrent
scans were happening, chances are the PID wouldn't match anyway, and
thus not be removed.

But note that barring backend crash, once all the scans are done it is
guaranteed that the hint will be removed --- somebody will be last to
update the hint, and therefore will remove it when they do heap_endscan,
even if others are not quite done. This is good in the sense that
later-starting backends won't be fooled into starting at what is
guaranteed to be the most pessimal spot, but it's got a downside too,
which is that there will be windows where seqscans are in process but
a newly started scan won't see them. Maybe that's a killer objection.

When exactly is the hint updated? I gathered from something Heikki said
that it's set after processing X amount of data, but I think it might be
better to set it *before* processing X amount of data. That is, the
hint means "I'm going to be scanning at least <threshold> blocks
starting here", not "I have scanned <threshold> blocks ending here",
which seems like the interpretation that's being used at the moment.
What that would mean is that successive "LIMIT 1000" calls would in fact
all start at the same place, barring interference from other backends.

regards, tom lane