On Thu, Feb 8, 2018 at 2:44 AM, Kyotaro HORIGUCHI <horiguchi.kyot...@lab.ntt.co.jp> wrote: > Hello, I looked this a bit closer. > > In upthread[1] Robert mentioned the exponentially increasing size > of additional segments. > >>> Hmm, I had imagined making all of the segments the same size rather >>> than having the size grow exponentially. The whole point of this is >>> to save memory, and even in the worst case you don't end up with that >>> many segments as long as you pick a reasonable base size (e.g. 64MB). >> >> Wastage is bound by a fraction of the total required RAM, that is, >> it's proportional to the amount of required RAM, not the amount >> allocated. So it should still be fine, and the exponential strategy >> should improve lookup performance considerably. > > It seems that you are getting him wrong. (Anyway I'm not sure > what you meant by the above. not-yet-allocated memory won't be a > waste.) The conclusive number of dead tuples in a heap scan is > undeteminable until the scan ends. If we had a new dead tuple > required a, say 512MB new segment and the scan ends just after, > the wastage will be almost the whole of the segment.
And the segment size is bound by a fraction of total needed memory. When I said "allocated", I meant m_w_m. Wastage is not proportional to m_w_m. > On the other hand, I don't think the exponential strategy make > things considerably better. bsearch iterations in > lazy_tid_reaped() are distributed between segment search and tid > search. Intuitively more or less the increased segment size just > moves some iterations of the former to the latter. > > I made a calculation[2]. With maintemance_work_mem of 4096MB, the > number of segments is 6 and expected number of bsearch iteration > is about 20.8 for the exponential strategy. With 64MB fixed size > segments, we will have 64 segments (that is not so many) and the > expected iteration is 20.4. (I suppose the increase comes from > the imbalanced size among segments.) Addition to that, as Robert > mentioned, the possible maximum memory wastage of the exponential > strategy is about 2GB and 64MB in fixed size strategy. That calculation has a slight bug in that it should be log2, and that segment size is limited to 1GB at the top end. But in any case, the biggest issue is that it's ignoring the effect of cache locality. The way in which the exponential strategy helps, is by keeping the segment list small and comfortably fitting in fast cache memory, while also keeping wastage at a minimum for small lists. 64MB segments with 4G mwm would be about 2kb of segment list. It fits in L1, if there's nothing else contending for it, but it's already starting to get big, and it would be expected settings larger than 4G mwm could be used. I guess I could tune the starting/ending sizes a bit. Say, with an upper limit of 256M (instead of 1G), and after fixing the other issues, we get: exponential sized strategy ... #18 : segsize=64MB total=4096MB, (tuples = 715827882, min tsize=18.8GB), iterseg(18)=4.169925, iteritem(11184810) = 23.415037, expected iter=29.491213 fixed sized strategy ... #64 : segsize=64MB total=4096MB, (tuples = 715827882, min tsize=18.2GB), interseg(64)=6.000000, iteritem(11184810) = 23.415037, expected iter=29.415037 Almost identical, and we get all the benefits of cache locality with the exponential strategy. The fixed strategy might fit in the L1, but it's less likely the bigger the mwm is. The scaling factor could also be tuned I guess, but I'm wary of using anything other than a doubling strategy, since it might cause memory fragmentation.
