It would be nice if total table cardinality could be maintained live.
So (after the initial vacuum) we update the cardinality for each table
in the system table (or perhaps add an entry to the table itself).
There are two reasons why this is an important optimization.  Firstly,
it is a psychological benefit for both benchmarks and customers when
doing a select count(*) from <tablename>.  This is something that pops
up all the time in benchmarks and customers do it too, in order to get a
feel for speed.  By storing the current number and incrementing for
every insert and decrementing for every delete, the count(*) case with
no where clause can return the value instantly.

The far more important reason is for optimizations.  An accurate
cardinality figure can greatly enhance the optimizer's ability to
perform joins in the correct order.

An example of a SQL system that does this sort of thing is Microsoft
SQL*Server.  If you have 100 million rows in a table and do:
SELECT COUNT(*) FROM table_name
it will return the correct number instantly.  The same is true for
Oracle.

It might also be possible to keep an array in memory of:
typedef struct tag_cardinality_list {
	char *table_name;
	unsigned long cardinality;
} cardinality_list;

and keep the data updated there with simple interlocked exchange
operations.  The list would be loaded on Postmaster startup and saved on
shutdown.


Fri, 5 Apr 2002 11:04:13 -0800
"Dann Corbit" <DCorbit@connx.com>
Suggestion for optimization
"Dann Corbit" <DCorbit@connx.com> writes:

> It would be nice if total table cardinality could be maintained live.
> So (after the initial vacuum) we update the cardinality for each table
> in the system table (or perhaps add an entry to the table itself).
> There are two reasons why this is an important optimization.  Firstly,
> it is a psychological benefit for both benchmarks and customers when
> doing a select count(*) from <tablename>.  This is something that pops
> up all the time in benchmarks and customers do it too, in order to get a
> feel for speed.  By storing the current number and incrementing for
> every insert and decrementing for every delete, the count(*) case with
> no where clause can return the value instantly.

How would this work with MVCC?

-Doug
-- 
Doug McNaught       Wireboard Industries      http://www.wireboard.com/

      Custom software development, systems and network consulting.
      Java PostgreSQL Enhydra Python Zope Perl Apache Linux BSD...

05 Apr 2002 14:30:22 -0500
Doug McNaught <doug@wireboard.com>
Re: Suggestion for optimization
Doug McNaught <doug@wireboard.com> writes:
> "Dann Corbit" <DCorbit@connx.com> writes:
>> It would be nice if total table cardinality could be maintained live.

> How would this work with MVCC?

It wouldn't.  That's why it's not there.  Under MVCC, table cardinality
is in the eye of the beholder...

			regards, tom lane

Fri, 05 Apr 2002 14:37:19 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: Suggestion for optimization 
> >> It would be nice if total table cardinality could be maintained live.
> >
> > How would this work with MVCC?
>
> It wouldn't.  That's why it's not there.  Under MVCC, table cardinality
> is in the eye of the beholder...

That makes me curious how oracle implements it. I was under the impression 
that oracle managed to get the two together (MVCC and cardinality).

Also, can't triggers basically solve the problem from a functionaility 
standpoint? I mean, it would be slow for inserts, but I wonder if similar 
principles could be applied without the full overhead of triggers?

What I had in mind was to create a stats table (I guess much like the one 
that already exists, or a separate attribute of the existing one) and all of 
the tables in there, with a rowcount. Once a row is inserted, the trigger 
runs and updates the count (or decrements for delete), making the new count 
visible to the current transaction. Then when the transaction commits, it's 
visible everywhere at the same time as the count. 

Is there anything wrong with that setup, other than the obvious performance 
hit?

By the way, since this discussion has happened before, I actually read a 
similar idea in a previous email (if I remember correctly), but I didn't see 
much talk about it.

Regards,
	Jeff

Fri, 5 Apr 2002 13:09:08 -0800
Jeff Davis <list-pgsql-hackers@dynworks.com>
Re: Suggestion for optimization
> I don't think your idea would work for a concurrent user setup where
> people have different transactions started at different times with
> different amounts of changes inside each transaction.
>
> That's why it would have to be tracked on a "per connection" basis for
> all the tables.

I tried it out with concurrent connections and it seemed to hold up just 
fine. I think MVCC took care of everything. Transactions got a different 
count depending on whether they could see the inserted values or not. Once 
committed all transactions could see the new table count.

Can you provide a case where it wouldn't?

I imagine this causes some major performance issues, not to mention the dead 
tuples would pile up fast, but it seems to work just fine. 

My SQL is below.

Regards,
	Jeff

jdavis=> create table tuple_count(tuples int);
CREATE
jdavis=> create table c1(a int);
CREATE
jdavis=> create function f1() returns opaque as '
jdavis'> BEGIN
jdavis'>      UPDATE tuple_count set tuples=tuples+1;
jdavis'>      RETURN NEW;
jdavis'> END;
jdavis'> ' language 'plpgsql';
CREATE
jdavis=> create function f2() returns opaque as '
jdavis'> BEGIN
jdavis'>      UPDATE tuple_count set tuples=tuples-1;
jdavis'>      RETURN NEW;
jdavis'> END;
jdavis'> ' language 'plpgsql';
CREATE
jdavis=> create trigger t1 after insert on c1 for each row execute procedure 
f1();
CREATE
jdavis=> create trigger t2 after delete on c1 for each row execute procedure 
f2();
CREATE

Fri, 5 Apr 2002 15:22:50 -0800
Jeff Davis <list-pgsql-hackers@dynworks.com>
Re: Suggestion for optimization
Tom Lane wrote:
> 
> Doug McNaught <doug@wireboard.com> writes:
> > "Dann Corbit" <DCorbit@connx.com> writes:
> >> It would be nice if total table cardinality could be maintained live.
> 
> > How would this work with MVCC?
> 
> It wouldn't.  That's why it's not there.  Under MVCC, table cardinality
> is in the eye of the beholder...

This is true, absolutely, but keeping a running total of the number of records
should not change this fact. It may even make it more accurate.

If count() comes back immediately with *a* number, that number was only
accurate at the time of the transaction. If count() does a full table scan, it
still only comes back with something accurate to the time of the transaction,
but it could be more likely less accurate on a busy/large table because many
more things may have changed during the time used by a full table scan.

The issue of a busy table shouldn't make a difference either. If we aready
accept that count() returns the known count at the beginning time of the
transaction, and not the count() at the end of a tansaction (MVCC), then taking
a count() from a counter which is updated when delete/inserts are performed
just as accurate, or at least just as subject to inaccuracies.

Sun, 07 Apr 2002 08:50:41 -0400
mlw <markw@mohawksoft.com>
Re: Suggestion for optimization