Re: Mark/Restore and avoiding RandomAccess sorts

Bruce Momjian wrote:
> I saw no replies to this.

Sounds like a good idea to me.

(further comments below)

> Simon Riggs wrote:
>> Implementing the variable mark/restore buffer as a dumb Tuplestore would
>> mean that the space usage of the Sort could in worst case go as high as
>> x2 total space. The worst case is where the inner scan is all a single
>> value. The best case is where the inner scan is sufficiently unique over
>> all its values that it never writes back to disk at all.
>>
>> So a further refinement of this idea would be to simply defer the final
>> merge operation for the sort until the history required for the Mark
>> operation exceeded, say, 10% of the sort size. That would then be
>> sufficient to improve performance for most common cases, without risking
>> massive space overflow for large and highly non-unique data. There's no
>> problem with running the final merge slightly later than before;
>> everything's still there to allow it. Reusing space in the tuplestore is
>> also straightforward since that's exactly what the final merge already
>> does, so some rework of that code should be sufficient.

Should definitely be done by reusing the space in the tuplestore, we
don't want to use double the space we do now in the degenerate case.

>> This is a separate, but related idea of being able to avoid
>> mark/restores completely when the outer scan is provably unique.

We probably wouldn't need to try to avoid the mark/restore completely,
if the buffering scheme has low-enough overhead when restore is not called.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com