Re: count of occurences PLUS optimisation - Mailing list pgsql-general

Sorry about the size of this message!, it covers several optimisation
areas.

Yes we are talking about a limited situation of ORDER BY (that does not
match the GROUP BY order) plus LIMIT, but one that is easy to identify.

It also has the advantage that the number to be LIMITed will 9 times out
of 10 be known at query plan time (as LIMIT seems to mostly be used with
a constant), so making it an optimization that rarely needs to estimate.

It could even be tested for at the query run stage rather than the query
plan stage in those cases where the limit is not known in advance,
although that would make the explain less accurate.  Probably for
planning we should just assume that if a LIMIT is present that it is
likely to be for a smallish number.  The planner currently estimates
that 10% of the tuples will be returned in these cases.

The level up to which building a shorter list is better than a sort and
keep/discard should be evaluated.  It would perhaps depend on what
proportion the LIMIT is of the estimated set returned by the GROUP BY.
One point to note is that, IIRC, an ordered lists efficiency drops
faster than that of most decent sorts once the data must be paged
to/from disk.

For larger LIMITs we should still get some benefits if we get the first
LIMIT items, then sort just them and compare each new item against the
lowest item in this list.  Maybe form a batch of new items, then merge
the new batch in to produce a new LIMIT n long sorted list and repeat.
One major advantage to this is that as the new batch is being fetched we
no longer need to keep the existing list in ram.  I should think that
each new batch should be no longer than we can fit in ram or the amount
of ram that is best to enable an efficient list merge phase.

We could kick into this second mode when we the LIMIT exceeds the cutoff
or available ram.

I have just noticed while looking through the planner and executor that
the 'unique' node (SELECT DISTINCT [ON]) comes between the sort and
limit nodes and is run seperately.  Would it not be more efficient, in
the normal case of distinct on ORDER BY order (or start of ORDER BY),
for uniqueness to be handled within the the sorting as these routines
are already comparing the tuples?  Also if the unique node is seperate
then it makes the merging of sort and limit impossible if DISTINCT is
present.
However there is still the case of distinct where a sort is not
requested,  needed (index scan instead?) or is not suitable for the
distinct, so a seperate distinct node executor is still required.

Taking all these into account it seems that quite a lot of code would
need changing to implement this optimisation. Specifically the SORT,
UNIQUE and LIMIT nodes (and their planners) and the sort utils would
need a seperate variant and the current nodes would need altering.
It is a pity as I would expect fairly large benefits in those cases of
LIMITing to a small subset of a large dataset.

Martijn van Oosterhout wrote:
>
> On Thu, Sep 13, 2001 at 05:38:56PM +0100, Thurstan R. McDougle wrote:
> > What I am talking about is WHEN the sort is required we could make the
> > sort more efficient as inserting into a SHORT ordered list should be
> > better than building a BIG list and sorting it, then only keeping a
> > small part of the list.
>
> For a plain SORT, it would be possible. Anything to avoid materialising the
> entire table in memory. Unfortunatly it won't help if there is a GROUP
> afterwards because the group can't really know when to stop.
>
> But yes, if you had LIMIT<SORT<...>> you could do that. I can't imagine it
> would be too hard to arrange.
>
> > In the example in question there would be perhaps 400 records, but only
> > 10 are needed.  From the questions on these lists it seems quite common
> > for only a very low proportion of the records to be required (less then
> > 10%/upto 100 typically), in these cases it would seem to be a usefull
> > optimisation.
>
> Say you have a query:
>
> select id, count(*) from test group by id order by count desc limit 10;
>
> This becomes:
>
> LIMIT < SORT < GROUP < SORT < test > > > >
>
> The inner sort would still have to scan the whole table, unless you have an
> index on id. In that case your optimisation would be cool.
>
> Have I got it right now?
>
> --
> Martijn van Oosterhout <kleptog@svana.org>
> http://svana.org/kleptog/
> > Magnetism, electricity and motion are like a three-for-two special offer:
> > if you have two of them, the third one comes free.
>
> ---------------------------(end of broadcast)---------------------------
> TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org

--
This is the identity that I use for NewsGroups. Email to
this will just sit there. If you wish to email me replace
the domain with knightpiesold . co . uk (no spaces).