I am thinking about redefining and simplifying the planner's interface
to index-type-dependent estimation routines.

Currently, each defined index type is supposed to supply two routines:
an "amopselect" routine and an "amopnpages" routine.  (The existing
actual routines of this kind are btreesel, btreenpages, etc in
src/backend/utils/adt/selfuncs.c.)  These things are called by
index_selectivity() in src/backend/optimizer/util/plancat.c.  amopselect
tries to determine the selectivity of an indexqual (the fraction of
main-table tuples it will select) and amopnpages tries to determine
the number of index pages that will be read to do it.

Now, this collection of code is largely redundant with
optimizer/path/clausesel.c, which also tries to estimate the selectivity
of qualification conditions.  Furthermore, the interface to these
routines is fundamentally misdesigned, because there is no way to deal
with interrelated qualification conditions --- for example, if we have
a range query like "... WHERE x > 10 AND x < 20", the code estimates
the selectivity as the product of the selectivities of the two terms
independently, but the actual selectivity is very different from that.
I am working on fixing clausesel.c to be smarter about correlated
conditions, but it won't do much good to fix that code without fixing
the index-related code.

What I'm thinking about doing is replacing these two per-index-type
routines with a single routine, which is called once per proposed
indexscan rather than once per qual clause.  It would receive the
whole indexqual list as a parameter, instead of just one qual.
A typical implementation would just call clausesel.c's general-purpose
code to estimate the selectivity, and then do a little bit of extra
work to derive the estimated number of index pages from that number.

I suppose the original reason for having amopselect at all was to allow
exploitation of index-specific knowledge during selectivity estimation
--- but none of the existing index types actually provide any such
knowledge in their amopselect routines.  Still, this redesign preserves
the flexibility for an index type to do something specialized.

A possible objection to this scheme is that the inputs and outputs
of these routines would be structs that aren't full-fledged SQL types
(and no, I'm not willing to promote parser expression trees into an
SQL type ;-)).  But I don't think that's a real problem.  No one is
going to be inventing new index types without doing a lot of C coding,
so having to write the amopselect routines in C doesn't seem like a
big drawback.

Comments, objections, better ideas?

			regards, tom lane

Wed, 05 Jan 2000 23:25:08 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Proposed cleanup of index-related planner estimation procedures
Tom Lane wrote:
> 
> I am thinking about redefining and simplifying the planner's interface
> to index-type-dependent estimation routines.

Good Idea. I looked at that code quite closely in the past year, and I
agree that, though harmless, much of it seems bogus --- or at least not
well motivated by thorough analysis.  One reason for this is that the
problem of
computing index search costs is very difficult, the theoretical papers
that I could find on the subject are not terribly satisfactory. 
Currently only equals operators for hash and linear comparison operators
for nbtree really implement anything, the other access method operator
classes merely copy the nbtree operator algorithms.

> 
> What I'm thinking about doing is replacing these two per-index-type
> routines with a single routine, which is called once per proposed
> indexscan rather than once per qual clause.  It would receive the
> whole indexqual list as a parameter, instead of just one qual.
> A typical implementation would just call clausesel.c's general-purpose
> code to estimate the selectivity, and then do a little bit of extra
> work to derive the estimated number of index pages from that number.
> 
> I suppose the original reason for having amopselect at all was to allow
> exploitation of index-specific knowledge during selectivity estimation
> --- but none of the existing index types actually provide any such
> knowledge in their amopselect routines.  Still, this redesign preserves
> the flexibility for an index type to do something specialized.
>

Good, I have a special access method that needs to subvert the normal
optimizer in a way that ensures an index scan is used for every heap
access predicated on a particular attribute.  The reason for this is
that the data (representations of cells in a partition of a high
dimensional space) that would normally sit in heap tuples are actually
distributed through the index structure.  A query predicated on a
property of my special attributes needs to be executed with an index
scan, so I subvert the optimizer by coding amopselect and amopnpages to
always give zero cost for an index scan.  Since index scans are always
considered first, this hairy hack works. I would certainly breath more
easily at each new release of PostgreSQl if the ability of the system to
support this type of hack were a recognized feature.

> 
> A possible objection to this scheme is that the inputs and outputs
> of these routines would be structs that aren't full-fledged SQL types
> (and no, I'm not willing to promote parser expression trees into an
> SQL type ;-)).  But I don't think that's a real problem.  No one is
> going to be inventing new index types without doing a lot of C coding,

Yes, a lot of C-code, I have 10K lines in my access method.  What is
remarkable about Postgresql is that the interface between index access
methods and the rest of the system is so clean that this sort of project
is feasible. 

> so having to write the amopselect routines in C doesn't seem like a
> big drawback.

One thing that I have on my `really cool ideas' list would be to link
somehing like a Python interpreter and compiler into the backend.  one
would use the scripting language to write and debug stuff like this, and
then compile and dynamically link the debugged code into the backend. 
What I ended up doing in my index scheme was to code all the
mathematical algorithms in MATLAB and get them working there, and then
hand translate the MATLAB code to C (there is a lot of linear algebra in
the algorithms).  Debugging was a major pain.  With my idea you could
write the whole access method in a high-level language, and the low
level backend interfaces to things like buffer locking, MVCC and
postgresql memory management would be encapsulated by interfaces in the
high-level language. If there were something like that in PostgreSQL I
bet a lot more people would be rolling their own access methods.  I am
not sure that people who value stability over new features would see
this as a step in the right direction. ;-)

> 
> Comments, objections, better ideas?
> 
>                         regards, tom lane
> 
> ************

Thu, 06 Jan 2000 13:03:04 -0500
Bernard Adrian Frankpitt <frankpit@pop.dn.net>
Re: [HACKERS] Proposed cleanup of index-related planner estimation
	procedures
> -----Original Message-----
> From: owner-pgsql-hackers@postgreSQL.org
> [mailto:owner-pgsql-hackers@postgreSQL.org]On Behalf Of Tom Lane
> 
> I am thinking about redefining and simplifying the planner's interface
> to index-type-dependent estimation routines.
> 
> Currently, each defined index type is supposed to supply two routines:
> an "amopselect" routine and an "amopnpages" routine.  (The existing
> actual routines of this kind are btreesel, btreenpages, etc in
> src/backend/utils/adt/selfuncs.c.)  These things are called by
> index_selectivity() in src/backend/optimizer/util/plancat.c.  amopselect
> tries to determine the selectivity of an indexqual (the fraction of
> main-table tuples it will select) and amopnpages tries to determine
> the number of index pages that will be read to do it.
> 
> Now, this collection of code is largely redundant with
> optimizer/path/clausesel.c, which also tries to estimate the selectivity
> of qualification conditions.  Furthermore, the interface to these
> routines is fundamentally misdesigned, because there is no way to deal
> with interrelated qualification conditions --- for example, if we have
> a range query like "... WHERE x > 10 AND x < 20", the code estimates
> the selectivity as the product of the selectivities of the two terms
> independently, but the actual selectivity is very different from that.
> I am working on fixing clausesel.c to be smarter about correlated
> conditions, but it won't do much good to fix that code without fixing
> the index-related code.
> 
> What I'm thinking about doing is replacing these two per-index-type
> routines with a single routine, which is called once per proposed
> indexscan rather than once per qual clause.  It would receive the
> whole indexqual list as a parameter, instead of just one qual.
> A typical implementation would just call clausesel.c's general-purpose
> code to estimate the selectivity, and then do a little bit of extra
> work to derive the estimated number of index pages from that number.
>

Seems good to me.

I have also been suspicious about per qual selectivity and have
another exmaple.
For the following query
	select * from .. where col1=val1 and col2=val2;

the selectivity is selectivity of (col1=val1) * selectivity of (col2=val2)
currently. But it's not right in many cases.

Though it's almost impossible to hold disbursions for all combination
of columns,it may be possible to hold multi-column disbursions for
multi-columns indexes,

Regards.

Hiroshi Inoue
Inoue@tpf.co.jp

Fri, 7 Jan 2000 09:09:58 +0900
"Hiroshi Inoue" <Inoue@tpf.co.jp>
RE: [HACKERS] Proposed cleanup of index-related planner estimation
	procedures