Обсуждение: Re: [PERFORM] not using index for select min(...)
> > 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
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.