List:Commits« Previous MessageNext Message »
From:Øystein Grøvlen Date:December 2 2010 2:39pm
Subject:Re: bzr commit into mysql-next-mr-bugfixing branch (tor.didriksen:3236)
WL#1393
View as plain text  
Tor,

I am fine with most responses, there is only a very few issues left in 
this thread.  See inline.

On 12/ 2/10 12:23 PM, Tor Didriksen wrote:
> On 2010-11-26 16:14, Øystein Grøvlen wrote:
...
>> Why cannot the cost function go into filesort.h? That file seems to
>> import less than bounded_queue.h, so I would imagine that it should
>> still be possible to unit test it. As for a separate.cc file, you
>> already have one; it just has a misleading name. ;-)
>>
>
> non-template functions should not go in header files (except for very
> small inline functions).
> I could tag it 'static' but then we would get one instance in each
> compilation unit that does
> #include "filesort.h"

What I meant was to put the declaration in filesort.h.  I see you now 
have created a file filesort_utils.h.  That is also fine.

...

>> >> > +
>> >> > + @retval Pointer to the removed element.
>> >>
>> >> But what is returned is Key_type, not Element_Type.
>> >
>> > Tried to clarify.
>> >
>>
>> I still do not get this. One pushes an element, but only gets back
>> a reference the key. How will one be able to retrieve the actual
>> element?
>
> You can copy the element into the key,
> or keep a pointer to it (see unit
> tests).
> You can also let Key_type == Element_type, and use the offset_to_key I
> guess.
> This is entirely up to the keymaker_function.

Which makes me wonder why the keymaker_function is part of Bounded_queue 
interface at all.  Why not just require the user to extract the key 
before calling push()?   The Sort_param argument makes the whole 
Bounded_queue pretty Filesort-specific.

...

>> AH, that made me understand the point about the fall-back strategy.
>> Merge-sort will try with much less memory.
>>
>> However, the first fallback strategy could also be to try again with
>> PQ without addon-data. I think that is more according to the
>> documentation which now says:
>> If we don't have space for <max_rows> records, but we *do* have
>> space for <max_rows> keys, we may rewrite 'table' to sort with
>> references to records instead of additional data.
>>
>>
>
> hmm, this sounds complicated to me. how to test it?

I think it could be done, but I am not saying you should do it now. 
However, the comment cited above should probably be modified a bit then.

...

...

>> >> > + ulong num_available_keys= memavl/(param->rec_length +
>> sizeof(char*));
>> >> > + param->num_keys_per_buffer= (uint) param->max_rows + 1;
>> >> > + if (num_rows< num_available_keys)
>> >> > + {
>> >> > + /* The whole source set fits into memory. */
>> >> > + if (param->max_rows< num_rows/PQ_slowness )
>> >>
>> >> Some comment on PQ_slowness would be good here.
>> >
>> > There is already six lines describing PQ_slowness.
>> > There's
>> > else
>> > {
>> > /* PQ will be slower */
>> > DBUG_RETURN(false);
>> > }
>> >
>> > I don't know what more to say...
>>
>> I am still not convinced that the two usages of PQ_slowness actually
>> represents the same constant. What make PQ_slowness applicable in
>> both contexts? AFAICT, the value of PQ_slowness is based on scenarios
>> where only one of the formulas apply.
>
> please elaborate.

OK. I will try.  Maybe the problem is not PQ_slowness, but the formulas 
where it is used.

What is compared by the unit, is, AFAICT, the cost when all rows fit in 
sort buffer.  In that case, the cost of sort merge is

sm_cost= q*n*log(n)

where n is total number of rows and q is a constant specific to qsort.

The cost of using a priority queue is

pq_cost= p*n*log(n) + q*l*log(l)

where l is the limit value, p is a constant specific to insertion into 
the priority queue and n and q is a before.

So,

pq_cost/sm_cost = p/q + (l*log(l))/(n*log(n))

The priority queue should be preferred when pq_cost/sm_cost < 1, which 
gives:

l/n * log(l)/log(n) < 1 - p/q <=>

n/l * log(n)/log(l) > 1/(1-p/q) <=>

n/l * log(n)/log(l) > q/(q-p)

It seems that in the code the log(n)/log(l) factor is ignored.  Since in 
that case, you get:

n/l > q/(q-p) <=> l < n/PQ_slowness, where PQ_slowness=q/(q-p).

So the main question is then: Is it OK to ignore the log(n)/log(l) factor?

In addition, I am not convinved that q/(q-p) is the appropriate constant 
for the other formula.  However, I will need to investigate this a bit 
further, before I am quite sure.

...

>> >> I do not think this "not interesting" aspect of Bounded_queue is
>> >> documented. Seems a bit awkward.
>> >
>> > you are right, that should be handled by Bounded_queue itself, rather
>> > than the client code.
>> >
>>
>> Thanks, for fixing that. However, I think that change requires a test
>> that verifies that interleaved pushing and popping works correctly.
>>
>
> pop() isn't really necessary for this worklog, it's mainly to understand
> the underlying implementation.
> the interleaved scenario is not really relevant now.
> do you still instist on another unit test?

In that case it should be documented that this can of behavior has not 
been tested.

...

>> >> It seems that this just tests that the cost is positive and
>> >> monotonically increasing. Would it be possible in some other way to
>> >> test that the computed cost is actually reasonable?
>> >
>> > This started out as an over/undeflow test (got NaN for certain input).
>> > Then as a test that it was actually "fast" (the inner loop was very
>> slow).
>> > I really don't know "reasonable cost" is,
>> > and it's hard to test float accuracy anyways ...
>> >
>>
>> I guess unit tests is not the most appropriate for such testing. But
>> it would be good to have some way of verify our cost functions.
>
> I think unit testing *should be* appropriate. I am now testing:
> - no underflow/overflow
> - speed (not measured, just observed manually)
> - cost is monotonically increasing as a function of number of rows.
>
> anything other you can think of would be appreciated.
>

I think the best would be an investigation of real execution times that 
documents that the cost estimates reflects actual execution times.  I 
think for future optimizer features, it should be required that such 
results are included in the worklog.

--
Øystein

Thread
bzr commit into mysql-next-mr-bugfixing branch (tor.didriksen:3236) WL#1393Tor Didriksen11 Nov
  • Re: bzr commit into mysql-next-mr-bugfixing branch (tor.didriksen:3236)WL#1393Øystein Grøvlen19 Nov
    • Re: bzr commit into mysql-next-mr-bugfixing branch (tor.didriksen:3236)WL#1393Tor Didriksen24 Nov
      • Re: bzr commit into mysql-next-mr-bugfixing branch (tor.didriksen:3236)WL#1393Jorgen Loland25 Nov
      • Re: bzr commit into mysql-next-mr-bugfixing branch (tor.didriksen:3236)WL#1393Øystein Grøvlen26 Nov
        • Re: bzr commit into mysql-next-mr-bugfixing branch (tor.didriksen:3236)WL#1393Tor Didriksen2 Dec
          • Re: bzr commit into mysql-next-mr-bugfixing branch (tor.didriksen:3236)WL#1393Øystein Grøvlen2 Dec
            • Re: bzr commit into mysql-next-mr-bugfixing branch (tor.didriksen:3236)WL#1393Øystein Grøvlen3 Dec