Re: [PERFORM] not using index for select min(...)

Tom Lane wrote:
> Josh Berkus <josh(at)agliodbs(dot)com> writes:
> > For example, the following query is not possible to
> > "workaround" in PostgreSQL:
>
> > select teams_desc.team_id, team_name, team_code, notes,
> > min(teams_tree.treeno) as lnode, max(teams_tree.treeno) as rnode,
> > parent.team_id as parent_id, count(*)/2 as tlevel
> > from teams_desc JOIN teams_tree USING (team_id)
> > join teams_tree parent ON parent.treeno < teams_tree.treeno
> > join teams_tree parents on parents.treeno < teams_tree.treeno
> > WHERE parent.treeno = (SELECT max(p1.treeno) from teams_tree p1
> > where p1.treeno < teams_tree.treeno
> > and exists (select treeno from teams_tree p2
> > where p2.treeno > teams_tree.treeno
> > and p2.team_id = p1.team_id))
> > AND EXISTS (select parents2.team_id from teams_tree parents2
> > where parents2.treeno > teams_tree.treeno
> > AND parents2.team_id = parents.team_id)
> > group by teams_desc.team_id, team_name, team_code, notes, parent.team_id;
>
> > While one would hardly expect the above query to be fast, it is dissapointing
> > that it takes about 8-10 times as long to execute on PostgreSQL as on MSSQL,
> > since MSSQL seems to be able to use indexes to evaluate all three MIN() and
> > MAX() expressions.
>
> I think you are leaping to conclusions about why there's a speed
> difference. Or maybe I'm too dumb to see how an index could be used
> to speed these min/max operations --- but I don't see that one would
> be useful. Certainly not an index on treeno alone. Would you care to
> explain exactly how it's done?

Intuitively, it seems that an index on treeno is exactly what would
make the difference -- but min() and max() have to be smart enough to
use them when necessary.

I have a strong suspicion that min() and max() in MSSQL and other
databases are integrated into the parser, planner, and executor
directly. It's the only way I can think of that would make it
possible for those functions to make use of indexes and other
advantages to the fullest extent possible. For instance, in the above
query, the max() operation in the subselect would tell the planner and
executor to use the index on p1.treeno for two comparisons
simultaneously: p1.treeno < teams_tree.treeno and max(p1.treeno).
That means that the executor would descend the tree of the (btree)
index and instead of just comparing whether a branch is less than
teams_tree.treeno and following *all* of the branches that qualify, it
would follow the *largest* branch that qualified and nothing else.
That's a very significant optimization of the search, because instead
of eliminating an average of 50% of the branches to follow at each
node, it eliminates all but one. But it's not something that a naive
aggregate function would be able to do: the min() and max() aggregates
would (I expect) have to become first class objects in the parser,
planner, and executor just as the WHERE clause and its conditions are.

There may be other aggregate functions that can make use of indexes to
the same extent that min() and max() should be able to, but I don't
know what they are offhand, and I certainly doubt that they would be
used nearly as often as min() and max().

Even with our type system, I'd think that min() and max() would be
relatively straightforward as first class objects (well, as
straightforward as any first class object that gets implemented in all
three stages, at any rate!): they work efficiently (that is, can use
an index scan) when the column in question has a btree index on it,
and fall back to sequential scans (and use the appropriate operator,
">" or "<") when the column in question doesn't. It might even be
reasonable to allow a type to "overload" these functions so that the
planner and executor use the type-provided functions when available
(with the limitation that such type-provided functions would always
require a sequential scan as they do now) and fall back to the builtin
ones when the type doesn't provide them. I imagine this might
complicate the parser, planner, and executor quite a bit, however.

So the interesting question that arises from the above is: are there
any types that define a min() and max() but which *do not* define "<"
and ">"? I can't think of such types myself but can imagine that some
esoteric data types might qualify. For the purposes of optimizing the
common case, however, such esoteric types could easily be ignored, but
it's for their sake that it would be useful to be able to use a
type-defined function in place of min() or max().

--
Kevin Brown kevin(at)sysexperts(dot)com