I have just committed changes that alter the representation of
SortClause nodes (making them like GroupClause, instead of the
crufty way they were done before).  This breaks stored rules!
You will need to initdb next time you pull current sources...

The good news is that the optimizer is finally reasonably smart
about avoiding a top-level Sort operation.

			regards, tom lane

Fri, 20 Aug 1999 23:58:29 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Caution: tonight's commits force initdb
Hi 

> -----Original Message-----
> From: owner-pgsql-hackers@postgreSQL.org
> [mailto:owner-pgsql-hackers@postgreSQL.org]On Behalf Of Tom Lane
> Sent: Saturday, August 21, 1999 12:58 PM
> To: pgsql-hackers@postgreSQL.org
> Subject: [HACKERS] Caution: tonight's commits force initdb
> 
> 
> I have just committed changes that alter the representation of
> SortClause nodes (making them like GroupClause, instead of the
> crufty way they were done before).  This breaks stored rules!
> You will need to initdb next time you pull current sources...
> 
> The good news is that the optimizer is finally reasonably smart
> about avoiding a top-level Sort operation.
>

Thanks for your good jobs.

After applying this change,I tested some cases.
For a table t,explain shows

explain select * from t;

	NOTICE:  QUERY PLAN:

	Seq Scan on t  (cost=1716.32 rows=27131 width=612) 

And with ORDER BY clause

explain select * from t order by key;

	NOTICE:  QUERY PLAN:

	Index Scan using t_pkey on t  (cost=2284.55 rows=27131 width=612)

Hmm,Index scan is chosen to select all rows.
AFAIK,sequential scan + sort is much faster than index scan in
most cases.

	cost of index scan < cost of sequential scan + cost of sort

I have felt that the current cost estimation of index scan is too small,
though I have no alternative.

Comments ?

Hiroshi Inoue
Inoue@tpf.co.jp 

Tue, 24 Aug 1999 08:53:13 +0900
"Hiroshi Inoue" <Inoue@tpf.co.jp>
RE: [HACKERS] Caution: tonight's commits force initdb
"Hiroshi Inoue" <Inoue@tpf.co.jp> writes:
> Hmm,Index scan is chosen to select all rows.
> AFAIK,sequential scan + sort is much faster than index scan in
> most cases.
> 	cost of index scan < cost of sequential scan + cost of sort
> I have felt that the current cost estimation of index scan is too small,
> though I have no alternative.

Hmm.  Well, it's still a step forward that the system is able to
consider this query plan --- if it's choosing a plan that's actually
slower, then that indicates we have a problem with our cost estimates.

The current cost estimate for a sort (see optimizer/path/costsize.c) is
basically just P log P disk accesses (P being the estimated relation
size in pages) plus N log N tuple comparisons (N being the estimated
tuple count).  This is fairly bogus --- for one thing it does not
account for the fact that sorts smaller than SortMem kilobytes are done
in-memory without temp files.  I doubt that the amount of I/O for a
larger sort is quite right either.  We need to look at exactly what
usage psort.c makes of temp files and revise the I/O estimates
accordingly.

I am also suspicious that indexscan costs are underestimated.  The
cost of reading the index is probably not too far off, but the cost
of accessing the main table is bogus.  Worst case, for a table whose
tuples are thoroughly scattered, you would have a main-table page fetch
for *each* returned tuple.  In practice it's probably not anywhere near
that bad, since you may have some clustering of tuples (so that the same
page is hit several times in a row), and also the Postgres buffers and
the underlying Unix system's disk cache will save trips to disk if there
is any locality of reference at all.  I have no idea how to estimate
that effect --- anyone?  But cost_index is clearly producing a
ridiculously optimistic estimate at the moment.

			regards, tom lane

Tue, 24 Aug 1999 10:58:50 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Sorting costs (was Caution: tonight's commits force initdb)
Tom Lane wrote:
> 
> "Hiroshi Inoue" <Inoue@tpf.co.jp> writes:
> > Hmm,Index scan is chosen to select all rows.
> > AFAIK,sequential scan + sort is much faster than index scan in
> > most cases.
> >       cost of index scan < cost of sequential scan + cost of sort
> > I have felt that the current cost estimation of index scan is too small,
> > though I have no alternative.

can the optimizer make use of LIMIT, or some other hint that reaction 
time is preferred over speed of full query ?

In web apps the index scan may often be fastre than seq scan + sort as
one 
may not actually need all the tuples but only a small fraction from near 
the beginning.

Getting the beginning fast also gives better responsiveness for other 
interactive uses.

> I am also suspicious that indexscan costs are underestimated.  The
> cost of reading the index is probably not too far off, but the cost
> of accessing the main table is bogus.  Worst case, for a table whose
> tuples are thoroughly scattered, you would have a main-table page fetch
> for *each* returned tuple.  In practice it's probably not anywhere near
> that bad, since you may have some clustering of tuples (so that the same
> page is hit several times in a row), and also the Postgres buffers and
> the underlying Unix system's disk cache will save trips to disk if there
> is any locality of reference at all.  I have no idea how to estimate
> that effect --- anyone?  But cost_index is clearly producing a
> ridiculously optimistic estimate at the moment.

The one way to find out would be actual benchmarking - if current 
optimizer prefers index scans it is possible to do a query using 
index scan, dro the index, somehow flush disk cache and then do the 
same query using seqscan+sort. 

If the latter is preferred anyway we would have no way to test ...

------------------
Hannu

Tue, 24 Aug 1999 22:10:41 +0300
Hannu Krosing <hannu@trust.ee>
Re: [HACKERS] Sorting costs (was Caution: tonight's commits force
	initdb)
Hannu Krosing <hannu@trust.ee> writes:
> can the optimizer make use of LIMIT, or some other hint that reaction 
> time is preferred over speed of full query ?

That is on the to-do list.  I think the hard part is working out the
details of when a top-level LIMIT applies to the costs of a lower-level
scan (for example, it does not if there's going to be a Sort in
between), and then figuring out how to transmit that information around.
The optimizer does most of its cost estimation bottom-up, so it might
be hard to do much in any but the simplest cases.

> The one way to find out would be actual benchmarking - if current 
> optimizer prefers index scans it is possible to do a query using 
> index scan, dro the index, somehow flush disk cache and then do the 
> same query using seqscan+sort. 

> If the latter is preferred anyway we would have no way to test ...

You can benchmark with and without index usage by starting your client
with PGOPTIONS="-fs" or PGOPTIONS="-fi" respectively --- that basically
puts a very heavy thumb on the scales when the optimizer is choosing
which to use ;-).  However, I am not sure that I'd trust a small number
of benchmark results as a general guide to costs.  I think the critical
factor for indexscan costs is how scattered the tuples are with respect
to the index order, and without some idea about that factor you'd have
no way to know if a particular benchmark result is high, low, or average.

			regards, tom lane

Tue, 24 Aug 1999 17:14:12 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: [HACKERS] Sorting costs (was Caution: tonight's commits force
	initdb)
> -----Original Message-----
> From: hannu@kodu.home.ee [mailto:hannu@kodu.home.ee]On Behalf Of Hannu
> Krosing
> Sent: Wednesday, August 25, 1999 4:11 AM
> To: Tom Lane
> Cc: Hiroshi Inoue; pgsql-hackers
> Subject: Re: [HACKERS] Sorting costs (was Caution: tonight's commits
> force initdb)
>
>
> Tom Lane wrote:
> >
> > "Hiroshi Inoue" <Inoue@tpf.co.jp> writes:
> > > Hmm,Index scan is chosen to select all rows.
> > > AFAIK,sequential scan + sort is much faster than index scan in
> > > most cases.
> > >       cost of index scan < cost of sequential scan + cost of sort
> > > I have felt that the current cost estimation of index scan is
> too small,
> > > though I have no alternative.
>
> can the optimizer make use of LIMIT, or some other hint that reaction
> time is preferred over speed of full query ?
>
> In web apps the index scan may often be fastre than seq scan + sort as
> one
> may not actually need all the tuples but only a small fraction from near
> the beginning.
>
> Getting the beginning fast also gives better responsiveness for other
> interactive uses.
>

I kow there are many cases that the response to get first rows is necessary.
It's the reason that I provided a patch for descending ORDER BY cases.
I think that LIMIT is the hint to tell optimizer that the response is
necessary.
We would be able to use "LIMIT ALL" only to tell the hint if LIMIT is taken
into account.

> > I am also suspicious that indexscan costs are underestimated.  The
> > cost of reading the index is probably not too far off, but the cost
> > of accessing the main table is bogus.  Worst case, for a table whose
> > tuples are thoroughly scattered, you would have a main-table page fetch
> > for *each* returned tuple.  In practice it's probably not anywhere near
> > that bad, since you may have some clustering of tuples (so that the same
> > page is hit several times in a row), and also the Postgres buffers and
> > the underlying Unix system's disk cache will save trips to disk if there
> > is any locality of reference at all.  I have no idea how to estimate
> > that effect --- anyone?  But cost_index is clearly producing a
> > ridiculously optimistic estimate at the moment.
>
> The one way to find out would be actual benchmarking - if current
> optimizer prefers index scans it is possible to do a query using
> index scan, dro the index, somehow flush disk cache and then do the
> same query using seqscan+sort.
>

Probably this case was benchmarked by someone(Vadim ?).

I have thought that generally index scan is 5~10 times slower than
sequential scan to select all rows.
I know the case that index scan is more than 500 times slower than
sequential scan.  After clustering,the performance was dramatically
improved. Unfortunately,I don't know how to estimate such a case.

Regards.

Hiroshi Inoue
Inoue@tpf.co.jp



Wed, 25 Aug 1999 09:17:03 +0900
"Hiroshi Inoue" <Inoue@tpf.co.jp>
RE: [HACKERS] Sorting costs (was Caution: tonight's commits force
	initdb)