Thread: Re: Much Ado About COUNT(*)
> Tom, Bruce, and others involved in this recurring TODO discussion... > > First, let me start by saying that I understand this has been discussed > many times before; however, I'd like to see what the current state of > affairs is regarding the possibility of using a unique index scan to > speed up the COUNT aggregate. To sum up: 1. There are good technical reasons why not to do this. The pg aggregate system is very elegant...not worth compromising it for a specific case. 2. postgresql can do many things faster than oracle. If you prefer the way oracle behaves, use oracle. 3. workaround #1: just run analyze once in a while (you should do that anyways) and query pg_Class for the #tuples in a relation. 4. workaround #2: rig up a materialized view and query that. This will be faster than what oracle does, btw, at the price of some coherency. 5. understand that count(*) from t, although frequently used, is of dubious value in the general sense. Sooner or later someone will optimize this, but in light of the currently available workarounds it doesn't seem that important. 6. for large tables, you can get a pretty accurate count by doing: select count(*) * 10 from t where random() > .9; on my setup, this shaved about 15% off of the counting time...YMMV. Merlin
> Greg Stark wrote: > > >I think part of the problem is that there's a bunch of features related > to > >these types of queries and the lines between them blur. > > > >You seem to be talking about putting visibility information inside > indexes for > >so index-only plans can be performed. But you're also talking about > queries > >like "select count(*) from foo" with no where clauses. Such a query > wouldn't > >be helped by index-only scans. > > > >Perhaps you're thinking about caching the total number of records in a > global > >piece of state like a materialized view? That would be a nice feature but > I > >think it should done as a general materialized view implementation, not a > >special case solution for just this one query. > > > >Perhaps you're thinking of the min/max problem of being able to use > indexes to > >pick out just the tuples satisfying the min/max constraint. That seems to > me > >to be one of the more tractable problems in this area but it would still > >require lots of work. > > > >I suggest you post a specific query you find is slow. Then discuss how > you > >think it ought to be executed and why. > > > > > > > You are correct, I am proposing to add visibility to the indexes. > > As for unqualified counts, I believe that they could take advantage of > an index-only scan as it requires much less I/O to perform an index scan > than a sequential scan on large tables. I agree with Greg...I think the way to approach this is a general materialized view solution. This would solve a broad class of tricky problems including count() and count(*)...you get to choice between the pay now/pay later tradeoff, etc. Merlin
A notion for indices that are not unique... (won't help much on select
count(*) but might be helpful for other types of query optimization)
Put a count in the index for each distinct type.
In the worst case, the index is actually unique and you have 8 wasted
bytes per index entry and all the entries are in the leaves (perhaps it
could be an OPTION for some tables). I don't know enough about the
structure of PostgreSQL's indexes to know if my suggestion is pure
hogwash, so don't laugh to hard if it is pure stupidity.
The most practical value of SELECT COUNT(*) is for updating statistics
(and looking good in phony-baloney benchmarks). But the statistics only
need to be updated when you vacuum, so it hardly seems a crucial issue
to me.
-----Original Message-----
From: pgsql-hackers-owner@postgresql.org
[mailto:pgsql-hackers-owner@postgresql.org] On Behalf Of Tom Lane
Sent: Wednesday, January 12, 2005 11:42 AM
To: Jonah H. Harris
Cc: pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Much Ado About COUNT(*)
"Jonah H. Harris" <jharris@tvi.edu> writes:
> My thinking is that we may be able to implement index usage for not
only
> unqualified counts, but also on any query that can be satisfied by the
> index itself.
The fundamental problem is that you can't do it without adding at least
16 bytes, probably 20, to the size of an index tuple header. That would
double the physical size of an index on a simple column (eg an integer
or timestamp). The extra I/O costs and extra maintenance costs are
unattractive to say the least. And it takes away some of the
justification for the whole thing, which is that reading an index is
much cheaper than reading the main table. That's only true if the index
is much smaller than the main table ...
regards, tom lane
---------------------------(end of broadcast)---------------------------
TIP 9: the planner will ignore your desire to choose an index scan if
your joining column's datatypes do not match
> Date: Wed, 12 Jan 2005 18:45:09 -0800
> From: Jeff Davis <jdavis-pgsql@empires.org>
> To: Alvaro Herrera <alvherre@dcc.uchile.cl>
> Cc: pgsql-hackers@postgresql.org
> Subject: Re: Much Ado About COUNT(*)
> Message-ID: <1105584309.2886.410.camel@jeff>
(cut)
> Thanks for the link. It looks like it breaks it up into chunks of about
2KB. I think the
> conversation was mostly assuming the tables were somewhat closer to the
size of an
> index. If you have more than 2KB per tuple, pretty much anything you do
with an index
> would be faster I would think.
Hi Jeff/Alvaro,
I'm considering an application at the moment whereby I would need to do lots
of COUNT(*) on lots of separate tables without a WHERE clause. Would
something like the following help speed up the COUNT(*) by reducing the
tuple size being used for the count?
CREATE SEQUENCE id_seq;
CREATE TABLE person_count (id int8);
CREATE TABLE person (id int8 DEFAULT nextval('id_seq');first_name text,surname text,age int,address1 text,address2
text,address3text,address4 text,postcode texttel text);
For each insert:
BEGIN;INSERT INTO person (first_name, .... Tel) VALUES ('Fred', ....
'12345');INSERT INTO person_count(id) VALUES (currval('id_seq'));COMMIT;
So then I would use SELECT COUNT(*) FROM person_count whenever I wanted to
know the current number of person records. How much quicker would a COUNT(*)
be if visibility were included in the indices as opposed to a "hacked"
approach like this?
Many thanks,
Mark.
------------------------
WebBased Ltd
South West Technology Centre
Tamar Science Park
Plymouth
PL6 8BT
T: +44 (0)1752 791021
F: +44 (0)1752 791023
W: http://www.webbased.co.uk
On Wed, Jan 19, 2005 at 14:59:17 -0000, Mark Cave-Ayland <m.cave-ayland@webbased.co.uk> wrote:
> BEGIN;
> INSERT INTO person (first_name, .... Tel) VALUES ('Fred', ....
> '12345');
> INSERT INTO person_count(id) VALUES (currval('id_seq'));
> COMMIT;
>
>
> So then I would use SELECT COUNT(*) FROM person_count whenever I wanted to
> know the current number of person records. How much quicker would a COUNT(*)
> be if visibility were included in the indices as opposed to a "hacked"
> approach like this?
You are only going to get a constant factor speed up unless the space savings
allows much better use of cache. You probably want to look at using
triggers to maintain counts in another table.
On Wed, Jan 19, 2005 at 10:16:38AM -0600, Bruno Wolff III wrote: > On Wed, Jan 19, 2005 at 14:59:17 -0000, > Mark Cave-Ayland <m.cave-ayland@webbased.co.uk> wrote: > > > So then I would use SELECT COUNT(*) FROM person_count whenever I wanted to > > know the current number of person records. How much quicker would a COUNT(*) > > be if visibility were included in the indices as opposed to a "hacked" > > approach like this? > > You are only going to get a constant factor speed up unless the space savings > allows much better use of cache. You probably want to look at using > triggers to maintain counts in another table. I'd try using a "start value" and a differences list. So the differences list would be initially empty and the start value would be 0. On insert or delete, you create a new difference (with +1 or whatever). Periodically, the differences would be added to the start value and the records deleted. Thus the time to calculate the total count is much smaller, and it follows MVCC rules. Of course there are lots of minor details not mentioned here. Not sure if I'd model this with a single table or two. -- Alvaro Herrera (<alvherre[@]dcc.uchile.cl>) "I would rather have GNU than GNOT." (ccchips, lwn.net/Articles/37595/)
To fill in some details I think what he's saying is this: => create table foo(...); => create table foo_count(num int); => insert into foo_count values(0); => create table foo_change(num int); then create a trigger "after delete on foo" that does "insert into foo_change values(-1)" and a trigger "after insert on foo" that inserts a +1 into foo_change. Periodically, do: => begin; => set transaction isolation level serializable; => update foo_count set num=num+(select sum(num) from foo_change); => delete from foo_change; => commit; => VACUUM; And then any time you need the correct count(*) value, do instead: => select sum(num) from (select num from foo_count union select num from foo_change); And that should work. I haven't tested this exact example, so I may have overlooked something. Hope that helps. That way, you don't have huge waste from the second table, and also triggers maintain it for you and you don't need to think about it. Regards,Jeff Davis On Wed, 2005-01-19 at 17:40 -0300, Alvaro Herrera wrote: > On Wed, Jan 19, 2005 at 10:16:38AM -0600, Bruno Wolff III wrote: > > On Wed, Jan 19, 2005 at 14:59:17 -0000, > > Mark Cave-Ayland <m.cave-ayland@webbased.co.uk> wrote: > > > > > So then I would use SELECT COUNT(*) FROM person_count whenever I wanted to > > > know the current number of person records. How much quicker would a COUNT(*) > > > be if visibility were included in the indices as opposed to a "hacked" > > > approach like this? > > > > You are only going to get a constant factor speed up unless the space savings > > allows much better use of cache. You probably want to look at using > > triggers to maintain counts in another table. > > I'd try using a "start value" and a differences list. So the > differences list would be initially empty and the start value would be > 0. On insert or delete, you create a new difference (with +1 or > whatever). Periodically, the differences would be added to the start > value and the records deleted. Thus the time to calculate the total > count is much smaller, and it follows MVCC rules. Of course there are > lots of minor details not mentioned here. > > Not sure if I'd model this with a single table or two. >
> -----Original Message----- > From: Jeff Davis [mailto:jdavis-pgsql@empires.org] > Sent: 19 January 2005 21:33 > To: Alvaro Herrera > Cc: Mark Cave-Ayland; pgsql-hackers@postgresql.org > Subject: Re: [HACKERS] Much Ado About COUNT(*) > > > > To fill in some details I think what he's saying is this: > > => create table foo(...); > => create table foo_count(num int); > => insert into foo_count values(0); > => create table foo_change(num int); > > then create a trigger "after delete on foo" that does "insert > into foo_change values(-1)" and a trigger "after insert on > foo" that inserts a +1 into foo_change. > > Periodically, do: > => begin; > => set transaction isolation level serializable; > => update foo_count set num=num+(select sum(num) from > foo_change); => delete from foo_change; => commit; => VACUUM; > > And then any time you need the correct count(*) value, do > instead: => select sum(num) from (select num from foo_count > union select num from foo_change); > > And that should work. I haven't tested this exact example, so > I may have overlooked something. > > Hope that helps. That way, you don't have huge waste from the > second table, and also triggers maintain it for you and you > don't need to think about it. > > Regards, > Jeff Davis Hi Jeff, Thanks for the information. I seem to remember something similar to this being discussed last year in a similar thread. My only real issue I can see with this approach is that the trigger is fired for every row, and it is likely that the database I am planning will have large inserts of several hundred thousand records. Normally the impact of these is minimised by inserting the entire set in one transaction. Is there any way that your trigger can be modified to fire once per transaction with the number of modified rows as a parameter? Many thanks, Mark. ------------------------ WebBased Ltd South West Technology Centre Tamar Science Park Plymouth PL6 8BT T: +44 (0)1752 791021 F: +44 (0)1752 791023 W: http://www.webbased.co.uk
On Thu, 20 Jan 2005 10:12:17 -0000 "Mark Cave-Ayland" <m.cave-ayland@webbased.co.uk> wrote: > Thanks for the information. I seem to remember something similar to > this being discussed last year in a similar thread. My only real issue > I can see with this approach is that the trigger is fired for every > row, and it is likely that the database I am planning will have large > inserts of several hundred thousand records. Normally the impact of > these is minimised by inserting the entire set in one transaction. Is > there any way that your trigger can be modified to fire once per > transaction with the number of modified rows as a parameter? I don't believe that such a facility exists but before dismissing it you should test it out. I think that you will find that disk buffering (the system's as well as PostgreSQL's) will effectively handle this for you anyway. -- D'Arcy J.M. Cain <darcy@druid.net> | Democracy is three wolves http://www.druid.net/darcy/ | and a sheep voting on +1 416 425 1212 (DoD#0082) (eNTP) | what's for dinner.
D'Arcy J.M. Cain wrote:
> On Thu, 20 Jan 2005 10:12:17 -0000
> "Mark Cave-Ayland" <m.cave-ayland@webbased.co.uk> wrote:
>
>>Thanks for the information. I seem to remember something similar to
>>this being discussed last year in a similar thread. My only real issue
>>I can see with this approach is that the trigger is fired for every
>>row, and it is likely that the database I am planning will have large
>>inserts of several hundred thousand records. Normally the impact of
>>these is minimised by inserting the entire set in one transaction. Is
>>there any way that your trigger can be modified to fire once per
>>transaction with the number of modified rows as a parameter?
>
>
> I don't believe that such a facility exists but before dismissing it you
> should test it out. I think that you will find that disk buffering (the
> system's as well as PostgreSQL's) will effectively handle this for you
> anyway.
Well, it looks like ROW_COUNT isn't set in a statement-level trigger
function (GET DIAGNOSTICS myvar=ROW_COUNT). Which is a shame, otherwise
it would be easy to handle. It should be possible to expose this
information though, since it gets reported at the command conclusion.
-- Richard Huxton Archonet Ltd
-- stmt_trig_test.sql --
BEGIN;
CREATE TABLE trigtest ( a int4 NOT NULL, b text, PRIMARY KEY (a)
);
CREATE FUNCTION tt_test_fn() RETURNS TRIGGER AS '
DECLARE nr integer; ro integer; nr2 integer;
BEGIN GET DIAGNOSTICS nr = ROW_COUNT; GET DIAGNOSTICS ro = RESULT_OID; SELECT count(*) INTO nr2 FROM
trigtest;
RAISE NOTICE ''nr = % / ro = % / nr2 = %'',nr,ro,nr2;
RETURN NULL;
END;
' LANGUAGE plpgsql;
CREATE TRIGGER tt_test AFTER INSERT OR UPDATE ON trigtest
FOR EACH STATEMENT
EXECUTE PROCEDURE tt_test_fn();
INSERT INTO trigtest VALUES (1,'a');
INSERT INTO trigtest VALUES (2,'b');
UPDATE trigtest SET b = 'x';
ROLLBACK;
> -----Original Message----- > From: Richard Huxton [mailto:dev@archonet.com] > Sent: 20 January 2005 12:45 > To: D'Arcy J.M. Cain > Cc: Mark Cave-Ayland; jdavis-pgsql@empires.org; > alvherre@dcc.uchile.cl; pgsql-hackers@postgresql.org > Subject: Re: [HACKERS] Much Ado About COUNT(*) > > > D'Arcy J.M. Cain wrote: > > On Thu, 20 Jan 2005 10:12:17 -0000 > > "Mark Cave-Ayland" <m.cave-ayland@webbased.co.uk> wrote: > > > >>Thanks for the information. I seem to remember something similar to > >>this being discussed last year in a similar thread. My only > real issue > >>I can see with this approach is that the trigger is fired for every > >>row, and it is likely that the database I am planning will > have large > >>inserts of several hundred thousand records. Normally the impact of > >>these is minimised by inserting the entire set in one > transaction. Is > >>there any way that your trigger can be modified to fire once per > >>transaction with the number of modified rows as a parameter? > > > > > > I don't believe that such a facility exists but before > dismissing it > > you should test it out. I think that you will find that disk > > buffering (the system's as well as PostgreSQL's) will effectively > > handle this for you anyway. > > Well, it looks like ROW_COUNT isn't set in a statement-level trigger > function (GET DIAGNOSTICS myvar=ROW_COUNT). Which is a shame, > otherwise > it would be easy to handle. It should be possible to expose this > information though, since it gets reported at the command conclusion. Hi Richard, This is more the sort of approach I would be looking for. However I think even in a transaction with ROW_COUNT defined, the trigger will still be called once per insert. I think something like this would require a new syntax like below, and some supporting code that would keep track of the tables touched by a transaction :( CREATE TRIGGER tt_test AFTER TRANSACTION ON trigtest FOR EACH TRANSACTION EXECUTE PROCEDURE tt_test_fn(); I am sure that Jeff's approach will work, however it just seems like writing out one table entry per row is going to slow large bulk inserts right down. Kind regards, Mark. ------------------------ WebBased Ltd South West Technology Centre Tamar Science Park Plymouth PL6 8BT T: +44 (0)1752 791021 F: +44 (0)1752 791023 W: http://www.webbased.co.uk
On Thu, Jan 20, 2005 at 01:33:10PM -0000, Mark Cave-Ayland wrote: > I am sure that Jeff's approach will work, however it just seems like writing > out one table entry per row is going to slow large bulk inserts right down. I don't see how it is any slower than the approach of inserting one entry per row in the narrow table the OP wanted to use. And it will be faster for the scans. -- Alvaro Herrera (<alvherre[@]dcc.uchile.cl>) Officer Krupke, what are we to do? Gee, officer Krupke, Krup you! (West Side Story, "Gee, Officer Krupke")
Mark Cave-Ayland wrote: > > > >>-----Original Message----- >>From: Richard Huxton [mailto:dev@archonet.com] >>Sent: 20 January 2005 12:45 >>To: D'Arcy J.M. Cain >>Cc: Mark Cave-Ayland; jdavis-pgsql@empires.org; >>alvherre@dcc.uchile.cl; pgsql-hackers@postgresql.org >>Subject: Re: [HACKERS] Much Ado About COUNT(*) >> >> >>D'Arcy J.M. Cain wrote: >> >>>On Thu, 20 Jan 2005 10:12:17 -0000 >>>"Mark Cave-Ayland" <m.cave-ayland@webbased.co.uk> wrote: >>> >>> >>>>Thanks for the information. I seem to remember something similar to >>>>this being discussed last year in a similar thread. My only >> >>real issue >> >>>>I can see with this approach is that the trigger is fired for every >>>>row, and it is likely that the database I am planning will >> >>have large >> >>>>inserts of several hundred thousand records. Normally the impact of >>>>these is minimised by inserting the entire set in one >> >>transaction. Is >> >>>>there any way that your trigger can be modified to fire once per >>>>transaction with the number of modified rows as a parameter? >>> >>> >>>I don't believe that such a facility exists but before >> >>dismissing it >> >>>you should test it out. I think that you will find that disk >>>buffering (the system's as well as PostgreSQL's) will effectively >>>handle this for you anyway. >> >>Well, it looks like ROW_COUNT isn't set in a statement-level trigger >>function (GET DIAGNOSTICS myvar=ROW_COUNT). Which is a shame, >>otherwise >>it would be easy to handle. It should be possible to expose this >>information though, since it gets reported at the command conclusion. > > > > Hi Richard, > > This is more the sort of approach I would be looking for. However I think > even in a transaction with ROW_COUNT defined, the trigger will still be > called once per insert. I think something like this would require a new > syntax like below, and some supporting code that would keep track of the > tables touched by a transaction :( Well, a statement-level trigger would be called once per statement, which can be much less than per row. -- Richard Huxton Archonet Ltd