Issue 5399

Title
Better threshold between rebuild and update MPTT
Priority
feature
Status
resolved
Nosy list
ced, roundup-bot
Assigned to
ced
Keywords
review

Created on 2016-03-14.19:17:05 by ced, last changed 81 months ago by roundup-bot.

Messages

New changeset 4e541a3e260a by C?dric Krier in branch 'default':
Improve threshold between rebuild and update MPTT
http://hg.tryton.org/trytond/rev/4e541a3e260a
Author: [hidden] (ced) Tryton committer Tryton translator
Date: 2016-03-14.19:24:24
Here is review20861002
Author: [hidden] (ced) Tryton committer Tryton translator
Date: 2016-03-14.19:17:04
For now, the threshold is: len(ids) < count / 4
This number comes from the number of queries each method will generate:

rebuild: 2 queries per node -> 2*count
update: 8 queries per new node -> 8*len(ids)

But the number of query is not a very good measure of the cost because some queries in 'update' could potentially write on all nodes. So indeed we should compute the number of nodes modified:

rebuild: 1 write and 1 select on each node-> 2*count
update: (1 write + 3 select  + 2 write on average ½ all nodes + 1 write on child of id) on each ids

The ½ all nodes come from medium between all nodes (if inserted at the beginning) and 0 nodes (if inserted at the end).

So the threshold should be expressed as:

2*count < (4 + 2*count/2 + 1 * x) * len(ids)

2*count < (4 + count + x) * len(ids)

I think we can remove from the right: x because we can not evaluate it and it normally quite smaller than count.
we can also remove (4 * lend(ids)) compare to count because it will be the same on very small tree where the difference between rebuild or update doesn't matter.

So the threshold become:

2*count < count * len(ids)
2 < len(ids)

So we must do an rebuild as far as two records are created/modified.
History
Date User Action Args
2016-03-21 23:43:36roundup-botsetstatus: testing -> resolved
nosy: + roundup-bot
messages: + msg25209
2016-03-14 19:30:10reviewbotsetreviews: 20861002
keyword: + review
2016-03-14 19:24:24cedsetstatus: in-progress -> testing
messages: + msg25019
2016-03-14 19:17:05cedcreate