Consider the intermediate case:
* You have so much data that you need tmp table on disk, and
* N keys will fit in an in-memory priority queue.
In a single pass over the tmp table you could collect the N smallest
keys and puttting them in a priority queue headed by the max of them.
Yes, this is backwards. But that is what you need -- if a small key is
found, you need to bump out the max from the queue and insert the new
key. When finished, a qsort (or whatever) would be needed to re-sort
the N rows, smallest first.
Rick James
MySQL Geeks - Consulting & Review
> -----Original Message-----
> From: Eric Jensen [mailto:ej@stripped]
> Sent: Friday, March 13, 2009 10:32 AM
> To: internals@stripped
> Subject: proposed design for UNION Order By optimization
>
>
> I still feel more comfortable doing the temp table version
> first, but
> you should ask him for the patch so that we can base version 2 on it.
>
> thanks,
> eric
>
> On Mar 13, 2009, at 9:54 AM, Igor Babaev wrote:
>
> >
> >
> > Eric Jensen wrote:
> >> below
> >> On Mar 13, 2009, at 4:46 AM, Sergei Golubchik wrote:
> >>>
> >>>> 4. make st_select_lex_unit::exec use k-way merge logic
> relying on
> >>>> this
> >>>> one-result-at-a-time fetching to retrive up to LIMIT n results
> >>>> treating our temp table with its ordered index as a heap
> >>>
> >>> Wouldn't it be better to use a heap as a heap, not btree
> as a heap ?
> >>> Heap is faster than btree, and MySQL has a heap implementation in
> >>> mysys/queues.c
> >> would be better indeed! however, i could not find another
> example
> >> of a select result class that reads results from a heap.
> from what
> >> i remember, much of the logic for reading from an intermediate
> >> result set is specific to reading from a temporary table. for
> >> example, i don't know where to find all the proper comparators to
> >> execute an arbitrary order by in the heap. the heap seems like
> >> version two to me, unless i'm mistaken about the difficulty of
> >> storing intermediate row results in it, performing comparisons on
> >> them, and feeding them back to the user there a select
> result class
> >> that behaves like the ones that read from temporary tables.
> >
> > Eric,
> >
> > Somewhere in 2005 ago Evgeny Potemkin (eugene@stripped)
> implemented
> > ORDER BY <list> LIMIT N employing priority queue (heap) from mysys/
> > queues.c.
> > I'm pretty sure he still has that patch in his archives.
> > Would you like to contact Evgeny or you'd prefer me to ask him for
> > that patch?
> > The patch most probably will help you.
> >
> > Regards,
> > Igor.
> >
> >
> > --
> > MySQL Internals Mailing List
> > For list archives: http://lists.mysql.com/internals
> > To unsubscribe: http://lists.mysql.com/internals?
> > unsub=ej@stripped
> >
>
>
>
> --
> MySQL Internals Mailing List
> For list archives: http://lists.mysql.com/internals
> To unsubscribe:
> http://lists.mysql.com/internals?unsub=1
>
>
