not using index for select min(...)

On Fri, Jan 31, 2003 at 04:12:38PM -0500, Don Bowman wrote:

Why wouldn't I be doing an index scan on this table?

Because you're using the aggregate function min(). See

<http://www.ca.postgresql.org/docs/faq-english.html#4.8&gt;

A

-- 
----
Andrew Sullivan                         204-4141 Yonge Street
Liberty RMS                           Toronto, Ontario Canada
<andrew@libertyrms.info>                              M2P 2A8
                                         +1 416 646 3304 x110

Don,

I have a table which is very large (~65K rows). I have
a column in it which is indexed, and I wish to use for
a join. I'm finding that I'm using a sequential scan
for this when selecting a MIN.

Due to Postgres' system of extensible aggregates (i.e. you can write your own
aggregates), all aggregates will trigger a Seq Scan in a query. It's a
known drawrback that nobody has yet found a good way around.

--
-Josh Berkus
Aglio Database Solutions
San Francisco

On Fri, Jan 31, 2003 at 16:12:38 -0500,
Don Bowman <don@sandvine.com> wrote:

I have a table which is very large (~65K rows). I have
a column in it which is indexed, and I wish to use for
a join. I'm finding that I'm using a sequential scan
for this when selecting a MIN.

I've boiled this down to something like this:

=> create table X( value int primary key );
=> explain select min(value) from x;

Use the following instead:
select value from x order by value limit 1;

I have a table which is very large (~65K rows). I have
a column in it which is indexed, and I wish to use for
a join. I'm finding that I'm using a sequential scan
for this when selecting a MIN.

Due to Postgres' system of extensible aggregates (i.e. you can write
your own aggregates), all aggregates will trigger a Seq Scan in a
query. It's a known drawrback that nobody has yet found a good way
around.

I've spent some time in the past thinking about this, and here's the
best idea that I can come up with:

Part one: setup an ALTER TABLE directive that allows for the
addition/removal of cached aggregates. Ex:

ALTER TABLE tab1 ADD AGGREGATE CACHE ON count(*);
ALTER TABLE tab1 ADD AGGREGATE CACHE ON sum(col2);
ALTER TABLE tab1 ADD AGGREGATE CACHE ON sum(col2) WHERE col2 > 100;
ALTER TABLE tab1 ADD AGGREGATE CACHE ON sum(col2) WHERE col2 <= 100;

Which would translate into some kind of action on a pg_aggregate_cache
catalog:

aggregate_cache_oid OID -- OID for the aggregate cache
aggregate_table_oid OID -- table OID
ins_aggfn_oid OID -- aggregate function id for inserts
upd_aggfn_oid OID -- aggregate function id for updates
del_aggfn_oid OID -- aggregate function id for deletes
cache_value INT -- the value of the cache
private_data INT[4] -- temporary data space for needed
-- data necessary to calculate cache_value
-- four is just a guesstimate for how much
-- space would be necessary to calculate
-- the most complex of aggregates
where_clause ??? -- I haven't the faintest idea how to
-- express some kind of conditional like this

Part two: setup a RULE or TRIGGER that runs on INSERT, UPDATE, or
DELETE. For the count(*) exercise, the ON UPDATE would be a no-op.
For ON INSERT, the count(*) rule would have to do something like:

UPDATE pg_catalog.pg_aggregate_cache SET cached_value = (cached_value + 1)
WHERE aggregate_cache_oid = 1111111;

For the sum(col2) aggregate cache, the math is a little more complex,
but I think it's quite reasonable given that it obviates a full table
scan. For an insert:

UPDATE pg_catalog.pg_aggregate_cache SET cached_value =
((cached_value * private_data[0] + NEW.col2) / (private_data[0] + 1))
WHERE aggregate_cache_oid = 1111112;

Now, there are some obvious problems:

1) avg requires a floating point return value, therefore an INT may
not be an appropriate data type for cache_value or private_data.

2) aggregate caching wouldn't speed up anything but full table
aggregates or regions of a column that are frequently needed.

3) all of the existing aggregates would have to be updated to include
an insert, update, delete procedure (total of 60 aggregates, but
only 7 by name).

4) the planner would have to be taught how to use/return values from
the cache.

5) Each aggregate type makes use of the private_data column
differently. It's up to the cached aggregate function authors to
not jumble up their private data space.

6) I don't know of a way to handle mixing of floating point numbers
and integers. That said, there's some margin of error that could
creep into the floating point calculations such as avg.

And some benefits:

1) You only get caching for aggregates that you frequently use
(sum(col2), count(*), etc.).

2) Aggregate function authors can write their own caching routines.

3) For tens of millions of rows, it can be very time consuming to
sum() fifty million rows, but it's easy to amortize the cost of
updating the cache on insert, update, delete over the course of a
month.

4) If an aggregate cache definition isn't setup, it should be easy for
the planner to fall back to a full table scan, as it currently is.

This definitely would be a performance boost and something that would
only be taken advantage of by DBAs that are intentionally performance
tuning their database, but for those that do, it could be a massive
win. Thoughts? -sc

--
Sean Chittenden

Sean Chittenden <sean@chittenden.org> writes:

Now, there are some obvious problems:

You missed the real reason why this will never happen: it completely
kills any prospect of concurrent updates. If transaction A has issued
an update on some row, and gone and modified the relevant aggregate
cache entries, what happens when transaction B wants to update another
row? It has to wait for A to commit or not, so it knows whether to
believe A's changes to the aggregate cache entries.

For some aggregates you could imagine an 'undo' operator to allow
A's updates to be retroactively removed even after B has applied its
changes. But that doesn't work very well in general. And in any case,
you'd have to provide serialization interlocks on physical access to
each of the aggregate cache entries. That bottleneck applied to every
update would be likely to negate any possible benefit from using the
cached values.

regards, tom lane

Now, there are some obvious problems:

You missed the real reason why this will never happen: it completely
kills any prospect of concurrent updates. If transaction A has
issued an update on some row, and gone and modified the relevant
aggregate cache entries, what happens when transaction B wants to
update another row? It has to wait for A to commit or not, so it
knows whether to believe A's changes to the aggregate cache entries.

I never claimed it was perfect, :) but it'd be is no worse than a
table lock. For the types of applications that this would be of
biggest use to, there would likely be more reads than writes and it
wouldn't be as bad as one could imagine. A few examples:

# No contension
Transaction A begins
Transaction A updates tab1
Transaction B begins
Transaction B updates tab1
Transaction B commits
Transaction A commits

# contension
Transaction A begins
Transaction A updates tab1
Transaction B begins
Transaction B updates tab1
Transaction A commits
Transaction B commits

This is just about the only case that I can see where there would be
contension. In this case, transaction B would have to re-run its
trigger serially. In the worse case scenario:

Transaction A begins
Transaction A updates tab1
Transaction B begins
Transaction B updates tab1
Transaction A commits
Transaction B selects
Transaction B updates tab1 again
Transaction B commits

In my journals or books I haven't found any examples of a transaction
based cache that'd work any better than this. It ain't perfect, but,
AFAICT, it's as good as it's going to get. The only thing that I
could think of that would add some efficiency in this case would be to
have transaction B read trough the committed changes from a log file.
After a threshold, it could be more efficient than having transaction
B re-run its queries.

Like I said, it ain't perfect, but what would be a better solution?
::shrug:: Even OODB's with stats agents have this problem (though
their overhead for doing this kind of work is much much lower). -sc

--
Sean Chittenden

Tom Lane wrote:

Sean Chittenden <sean@chittenden.org> writes:

Now, there are some obvious problems:

You missed the real reason why this will never happen: it completely
kills any prospect of concurrent updates. If transaction A has issued
an update on some row, and gone and modified the relevant aggregate
cache entries, what happens when transaction B wants to update another
row? It has to wait for A to commit or not, so it knows whether to
believe A's changes to the aggregate cache entries.

For some aggregates you could imagine an 'undo' operator to allow
A's updates to be retroactively removed even after B has applied its
changes. But that doesn't work very well in general. And in any case,
you'd have to provide serialization interlocks on physical access to
each of the aggregate cache entries. That bottleneck applied to every
update would be likely to negate any possible benefit from using the
cached values.

Hmm...any chance, then, of giving aggregate functions a means of
asking which table(s) and column(s) the original query referred to so
that it could do proper optimization on its own? For instance, for a
"SELECT min(x) FROM mytable" query, the min() function would be told
upon asking that it's operating on column x of mytable, whereas it
would be told "undefined" for the column if the query were "SELECT
min(x+y) FROM mytable". In the former case, it would be able to do a
"SELECT x FROM mytable ORDER BY x LIMIT 1" on its own, whereas in the
latter it would have no choice but to fetch the data to do its
calculation via the normal means.

But that may be more trouble than it's worth, if aggregate functions
aren't responsible for retrieving the values they're supposed to base
their computations on, or if it's not possible to get the system to
refrain from prefetching data for the aggregate function until the
function asks for it.

--
Kevin Brown kevin@sysexperts.com

Kevin Brown <kevin@sysexperts.com> writes:

Hmm...any chance, then, of giving aggregate functions a means of
asking which table(s) and column(s) the original query referred to so
that it could do proper optimization on its own?

You can't usefully do that without altering the aggregate paradigm.
It won't help for min() to intuit the answer quickly if the query
plan is going to insist on feeding every row to it anyway.

For instance, for a
"SELECT min(x) FROM mytable" query, the min() function would be told
upon asking that it's operating on column x of mytable, whereas it
would be told "undefined" for the column if the query were "SELECT
min(x+y) FROM mytable". In the former case, it would be able to do a
"SELECT x FROM mytable ORDER BY x LIMIT 1" on its own,

Don't forget that it would also need to be aware of whether there were
any WHERE clauses, joins, GROUP BY, perhaps other things I'm not
thinking of.

In the end, the only reasonable way to handle this kind of thing is
to teach the query planner about it. Considering the small number
of cases that are usefully optimizable (basically only MIN and MAX
on a single table without any WHERE or GROUP clauses), and the ready
availability of a SQL-level workaround, it strikes me as a very
low-priority TODO item.

regards, tom lane

Sean,

I've spent some time in the past thinking about this, and here's the
best idea that I can come up with:

Part one: setup an ALTER TABLE directive that allows for the
addition/removal of cached aggregates. Ex:

Actually, Joe Conway and I may be working on something like this for a client.
Joe's idea is to use a hacked version of the statistics collector to cache
selected aggregate values in memory. These aggregates would be
non-persistent, but the main concern for us is having aggregate values that
are instantly accessable, and that don't increase the cost of INSERTS and
UPDATES more than 10%.

This is to satisfy the needs of a particular client, though, so it may never
make it into the general PostgreSQL source. We'll post it somewhere if it
works, though.

We already implemented caching aggregates to tables, with is trivially easy to
do with triggers. The problem with this approach is the
UPDATE/INSERT/DELETE overhead; even with an SPI-optimized C trigger, it's
costing us up to 40% additional time when under heavy write activity ...
which is exactly when we can't afford delays.

For a database which has a low level of UPDATE activity, though, you can
already implement cached aggregates as tables without inventing any new
Postgres extensions.

--
Josh Berkus
Aglio Database Solutions
San Francisco

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

Kevin Brown <kevin@sysexperts.com> writes:

Hmm...any chance, then, of giving aggregate functions a means of
asking which table(s) and column(s) the original query referred to so
that it could do proper optimization on its own?

You can't usefully do that without altering the aggregate paradigm.
It won't help for min() to intuit the answer quickly if the query
plan is going to insist on feeding every row to it anyway.

That just means you need some way for aggregates to declare which records they
need. The only values that seem like they would be useful would be "first
record" "last record" and "all records". Possibly something like "all-nonnull
records" for things like count(), but that might be harder.

Don't forget that it would also need to be aware of whether there were
any WHERE clauses, joins, GROUP BY, perhaps other things I'm not
thinking of.

In the end, the only reasonable way to handle this kind of thing is
to teach the query planner about it. Considering the small number
of cases that are usefully optimizable (basically only MIN and MAX
on a single table without any WHERE or GROUP clauses), and the ready
availability of a SQL-level workaround, it strikes me as a very
low-priority TODO item.

All true, but I wouldn't be so quick to dismiss it as low-priority. In my
experience I've seen the idiom "select min(foo) from bar" more times than I
can count. The frequency with which this question occurs here probably is
indicative of how much people expect it to work. And it's probably used by a
lot of multi-database applications and in a lot of auto-matically generated
code where it would be hard to hack in special purpose workarounds.

--
greg

On Sat, Feb 01, 2003 at 15:21:24 -0500,
Greg Stark <gsstark@mit.edu> wrote:

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

That just means you need some way for aggregates to declare which records they
need. The only values that seem like they would be useful would be "first
record" "last record" and "all records". Possibly something like "all-nonnull
records" for things like count(), but that might be harder.

I don't see how this is going to be all that useful for aggregates in general.
min and max are special and it is unlikely that you are going to get much
speed up for general aggregate functions. For the case where you really
only need to scan a part of the data (say skipping nulls when nearly all
of the entries are null), a DBA can add an appropiate partial index and
where clause. This will probably happen infrequently enough that adding
special checks for this aren't going to pay off.

For min and max, it seems to me that putting special code to detect these
functions and replace them with equivalent subselects in the case where
an index exists (since a sort is worse than a linear scan) is a possible
long term solution to make porting easier.

In the short term education is the answer. At least the documentation of the
min and max functions and the FAQ, and the section with performance tips
should recommend the alternative form if there is an appropiate index.

Tom,

In the end, the only reasonable way to handle this kind of thing is
to teach the query planner about it. Considering the small number
of cases that are usefully optimizable (basically only MIN and MAX
on a single table without any WHERE or GROUP clauses), and the ready
availability of a SQL-level workaround, it strikes me as a very
low-priority TODO item.

Low priority for you, Tom. For some of us, it's one of the three most
high-priority "bugs" in PostgreSQL.

I constantly try to sell my clients, and potential clients, on PostgreSQL.
And the two things that trip me up the most frequently are lack of
replication and our dog-slow aggregates. I can usually sell Postgres on our
strong points, but the aggregate issue is *always* a problem. And the "slow
aggregate" problem comes up about twice a week on Performance and three times
a week on SQL.

Regardless of the technical reason, among MSSQL, Oracle, MySQL and PostgreSQL,
we have the slowest performing simple aggregates. It's very well to explain
this is due to our system of extensible aggregates, but if a potential
Postgres developer doesn't want to create custom aggregates, but does want to
use MIN() in a correlated subquery, then they will go to a different RDBMS.

As I said before, I'm absolutely thrilled that you came up with a solution for
COUNT(*) ... GROUP BY queries through Hash Aggregates. That's half the
picture, now we need a way to speed up MIN() and MAX() for simple one-column
expressions. While there is a "workaround" using ORDER BY & LIMIT, this
doesn't work for correlated subqueries or if one wants to evaluate the result
of MAX() in the query. For example, the following query is not possible to
"workaround" in PostgreSQL:

select teams_desc.team_id, team_name, team_code, notes,
min(teams_tree.treeno) as lnode, max(teams_tree.treeno) as rnode,
parent.team_id as parent_id, count(*)/2 as tlevel
from teams_desc JOIN teams_tree USING (team_id)
join teams_tree parent ON parent.treeno < teams_tree.treeno
join teams_tree parents on parents.treeno < teams_tree.treeno
WHERE parent.treeno = (SELECT max(p1.treeno) from teams_tree p1
where p1.treeno < teams_tree.treeno
and exists (select treeno from teams_tree p2
where p2.treeno > teams_tree.treeno
and p2.team_id = p1.team_id))
AND EXISTS (select parents2.team_id from teams_tree parents2
where parents2.treeno > teams_tree.treeno
AND parents2.team_id = parents.team_id)
group by teams_desc.team_id, team_name, team_code, notes, parent.team_id;

While one would hardly expect the above query to be fast, it is dissapointing
that it takes about 8-10 times as long to execute on PostgreSQL as on MSSQL,
since MSSQL seems to be able to use indexes to evaluate all three MIN() and
MAX() expressions.

Further, assigning such a common query function to a Postgres-specific
workaround hardly upholds our project's dedication to standards. The fact
that we are telling new users to use non-SQL-compliant code to do a query
type present in 90% of databases bothers me every single time I give a newbie
that advice.

It still seems to me that if a query's WHERE expression can be evaluated using
an index, then any related MIN() or MAX() expression should be evaluable
using an index. That is, if you are selecting:
SELECT MAX(team_id) FROM teams WHERE team_id BETWEEN 100 and 200;
... with an index on team_id then this entire query should be able to return
trough an index scan. We've discussed the particular planner problems this
presents for PostgreSQL, but I still believe that these are solvable ... and
moreover, that we *need* to solve them if we're going to be competitive with
other SQL RDBMSes.

I do realize that it's my job to find something to do about this issue since
I'm the one so worked up about it. What I'm concerned about is the
possibility of having any idea or fix I come up with dismissed out of hand
because it's a "low-priority todo". Please add up the questions and
complaints of the users on SQL, NOVICE, and PERFORMANCE ... I know you read
them.

Thanks for reading, Tom.

--
Josh Berkus
Aglio Database Solutions
San Francisco

Josh Berkus <josh@agliodbs.com> writes:

For example, the following query is not possible to
"workaround" in PostgreSQL:

select teams_desc.team_id, team_name, team_code, notes,
min(teams_tree.treeno) as lnode, max(teams_tree.treeno) as rnode,
parent.team_id as parent_id, count(*)/2 as tlevel
from teams_desc JOIN teams_tree USING (team_id)
join teams_tree parent ON parent.treeno < teams_tree.treeno
join teams_tree parents on parents.treeno < teams_tree.treeno
WHERE parent.treeno = (SELECT max(p1.treeno) from teams_tree p1
where p1.treeno < teams_tree.treeno
and exists (select treeno from teams_tree p2
where p2.treeno > teams_tree.treeno
and p2.team_id = p1.team_id))
AND EXISTS (select parents2.team_id from teams_tree parents2
where parents2.treeno > teams_tree.treeno
AND parents2.team_id = parents.team_id)
group by teams_desc.team_id, team_name, team_code, notes, parent.team_id;

While one would hardly expect the above query to be fast, it is dissapointing
that it takes about 8-10 times as long to execute on PostgreSQL as on MSSQL,
since MSSQL seems to be able to use indexes to evaluate all three MIN() and
MAX() expressions.

I think you are leaping to conclusions about why there's a speed
difference. Or maybe I'm too dumb to see how an index could be used
to speed these min/max operations --- but I don't see that one would
be useful. Certainly not an index on treeno alone. Would you care to
explain exactly how it's done?

regards, tom lane

Tom,

I think you are leaping to conclusions about why there's a speed
difference. Or maybe I'm too dumb to see how an index could be used
to speed these min/max operations --- but I don't see that one would
be useful. Certainly not an index on treeno alone. Would you care to
explain exactly how it's done?

If I knew that, I'd have proposed a patch already, yes?

I'm working on it.

--
Josh Berkus
Aglio Database Solutions
San Francisco

Tom Lane wrote:

Josh Berkus <josh@agliodbs.com> writes:

For example, the following query is not possible to
"workaround" in PostgreSQL:

select teams_desc.team_id, team_name, team_code, notes,
min(teams_tree.treeno) as lnode, max(teams_tree.treeno) as rnode,
parent.team_id as parent_id, count(*)/2 as tlevel
from teams_desc JOIN teams_tree USING (team_id)
join teams_tree parent ON parent.treeno < teams_tree.treeno
join teams_tree parents on parents.treeno < teams_tree.treeno
WHERE parent.treeno = (SELECT max(p1.treeno) from teams_tree p1
where p1.treeno < teams_tree.treeno
and exists (select treeno from teams_tree p2
where p2.treeno > teams_tree.treeno
and p2.team_id = p1.team_id))
AND EXISTS (select parents2.team_id from teams_tree parents2
where parents2.treeno > teams_tree.treeno
AND parents2.team_id = parents.team_id)
group by teams_desc.team_id, team_name, team_code, notes, parent.team_id;

While one would hardly expect the above query to be fast, it is dissapointing
that it takes about 8-10 times as long to execute on PostgreSQL as on MSSQL,
since MSSQL seems to be able to use indexes to evaluate all three MIN() and
MAX() expressions.

I think you are leaping to conclusions about why there's a speed
difference. Or maybe I'm too dumb to see how an index could be used
to speed these min/max operations --- but I don't see that one would
be useful. Certainly not an index on treeno alone. Would you care to
explain exactly how it's done?

Intuitively, it seems that an index on treeno is exactly what would
make the difference -- but min() and max() have to be smart enough to
use them when necessary.

I have a strong suspicion that min() and max() in MSSQL and other
databases are integrated into the parser, planner, and executor
directly. It's the only way I can think of that would make it
possible for those functions to make use of indexes and other
advantages to the fullest extent possible. For instance, in the above
query, the max() operation in the subselect would tell the planner and
executor to use the index on p1.treeno for two comparisons
simultaneously: p1.treeno < teams_tree.treeno and max(p1.treeno).
That means that the executor would descend the tree of the (btree)
index and instead of just comparing whether a branch is less than
teams_tree.treeno and following *all* of the branches that qualify, it
would follow the *largest* branch that qualified and nothing else.
That's a very significant optimization of the search, because instead
of eliminating an average of 50% of the branches to follow at each
node, it eliminates all but one. But it's not something that a naive
aggregate function would be able to do: the min() and max() aggregates
would (I expect) have to become first class objects in the parser,
planner, and executor just as the WHERE clause and its conditions are.

There may be other aggregate functions that can make use of indexes to
the same extent that min() and max() should be able to, but I don't
know what they are offhand, and I certainly doubt that they would be
used nearly as often as min() and max().

Even with our type system, I'd think that min() and max() would be
relatively straightforward as first class objects (well, as
straightforward as any first class object that gets implemented in all
three stages, at any rate!): they work efficiently (that is, can use
an index scan) when the column in question has a btree index on it,
and fall back to sequential scans (and use the appropriate operator,
">" or "<") when the column in question doesn't. It might even be
reasonable to allow a type to "overload" these functions so that the
planner and executor use the type-provided functions when available
(with the limitation that such type-provided functions would always
require a sequential scan as they do now) and fall back to the builtin
ones when the type doesn't provide them. I imagine this might
complicate the parser, planner, and executor quite a bit, however.

So the interesting question that arises from the above is: are there
any types that define a min() and max() but which *do not* define "<"
and ">"? I can't think of such types myself but can imagine that some
esoteric data types might qualify. For the purposes of optimizing the
common case, however, such esoteric types could easily be ignored, but
it's for their sake that it would be useful to be able to use a
type-defined function in place of min() or max().

--
Kevin Brown kevin@sysexperts.com