LogMergePolicy.cs

Go to the documentation of this file.

/* 
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

using System;
using System.Collections.Generic;

namespace Lucene.Net.Index
{
    
    
    public abstract class LogMergePolicy : MergePolicy
    {
        
        public const double LEVEL_LOG_SPAN = 0.75;
        
        public const int DEFAULT_MERGE_FACTOR = 10;
        
        public static readonly int DEFAULT_MAX_MERGE_DOCS = System.Int32.MaxValue;

        public static double DEFAULT_NO_CFS_RATIO = 0.1;
        
        private int mergeFactor = DEFAULT_MERGE_FACTOR;
        
        internal long minMergeSize;
        internal long maxMergeSize;
        internal int maxMergeDocs = DEFAULT_MAX_MERGE_DOCS;

        protected double internalNoCFSRatio = DEFAULT_NO_CFS_RATIO;
        
        /* TODO 3.0: change this default to true */
        protected internal bool internalCalibrateSizeByDeletes = true;
        
        private bool useCompoundFile = true;
        private bool useCompoundDocStore = true;

        protected LogMergePolicy(IndexWriter writer):base(writer)
        {
        }
        
        protected internal virtual bool Verbose()
        {
            return writer != null && writer.Verbose;
        }

        public double NoCFSRatio
        {
            get { return internalNoCFSRatio; }
            set
            {
                if (value < 0.0 || value > 1.0)
                {
                    throw new ArgumentException("noCFSRatio must be 0.0 to 1.0 inclusive; got " + value);
                }
                this.internalNoCFSRatio = value;
            }
        }

        /* If a merged segment will be more than this percentage
         *  of the total size of the index, leave the segment as
         *  non-compound file even if compound file is enabled.
         *  Set to 1.0 to always use CFS regardless of merge
         *  size. */
        private void  Message(System.String message)
        {
            if (Verbose())
                writer.Message("LMP: " + message);
        }


        public virtual int MergeFactor
        {
            get { return mergeFactor; }
            set
            {
                if (value < 2)
                    throw new System.ArgumentException("mergeFactor cannot be less than 2");
                this.mergeFactor = value;
            }
        }

        public override bool UseCompoundFile(SegmentInfos infos, SegmentInfo info)
        {
            return useCompoundFile;
        }
        
        public virtual void  SetUseCompoundFile(bool useCompoundFile)
        {
            this.useCompoundFile = useCompoundFile;
        }

        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1024:UsePropertiesWhereAppropriate")]
        public virtual bool GetUseCompoundFile()
        {
            return useCompoundFile;
        }
        
        // Javadoc inherited
        public override bool UseCompoundDocStore(SegmentInfos infos)
        {
            return useCompoundDocStore;
        }
        
        public virtual void  SetUseCompoundDocStore(bool useCompoundDocStore)
        {
            this.useCompoundDocStore = useCompoundDocStore;
        }
        
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1024:UsePropertiesWhereAppropriate")]
        public virtual bool GetUseCompoundDocStore()
        {
            return useCompoundDocStore;
        }

        public virtual bool CalibrateSizeByDeletes
        {
            set { this.internalCalibrateSizeByDeletes = value; }
            get { return internalCalibrateSizeByDeletes; }
        }

        abstract protected internal long Size(SegmentInfo info);
        
        protected internal virtual long SizeDocs(SegmentInfo info)
        {
            if (internalCalibrateSizeByDeletes)
            {
                int delCount = writer.NumDeletedDocs(info);
                return (info.docCount - (long) delCount);
            }
            else
            {
                return info.docCount;
            }
        }
        
        protected internal virtual long SizeBytes(SegmentInfo info)
        {
            long byteSize = info.SizeInBytes();
            if (internalCalibrateSizeByDeletes)
            {
                int delCount = writer.NumDeletedDocs(info);
                float delRatio = (info.docCount <= 0?0.0f:((float) delCount / (float) info.docCount));
                return (info.docCount <= 0?byteSize:(long) (byteSize * (1.0f - delRatio)));
            }
            else
            {
                return byteSize;
            }
        }
        
        private bool IsOptimized(SegmentInfos infos, int maxNumSegments, ISet<SegmentInfo> segmentsToOptimize)
        {
            int numSegments = infos.Count;
            int numToOptimize = 0;
            SegmentInfo optimizeInfo = null;
            for (int i = 0; i < numSegments && numToOptimize <= maxNumSegments; i++)
            {
                SegmentInfo info = infos.Info(i);
                if (segmentsToOptimize.Contains(info))
                {
                    numToOptimize++;
                    optimizeInfo = info;
                }
            }
            
            return numToOptimize <= maxNumSegments && (numToOptimize != 1 || IsOptimized(optimizeInfo));
        }
        
        private bool IsOptimized(SegmentInfo info)
        {
            bool hasDeletions = writer.NumDeletedDocs(info) > 0;
            return !hasDeletions && !info.HasSeparateNorms() && info.dir == writer.Directory &&
                (info.GetUseCompoundFile() == useCompoundFile || internalNoCFSRatio < 1.0);
        }
        
        public override MergeSpecification FindMergesForOptimize(SegmentInfos infos, int maxNumSegments, ISet<SegmentInfo> segmentsToOptimize)
        {
            MergeSpecification spec;
            
            System.Diagnostics.Debug.Assert(maxNumSegments > 0);
            
            if (!IsOptimized(infos, maxNumSegments, segmentsToOptimize))
            {
                
                // Find the newest (rightmost) segment that needs to
                // be optimized (other segments may have been flushed
                // since optimize started):
                int last = infos.Count;
                while (last > 0)
                {
                    SegmentInfo info = infos.Info(--last);
                    if (segmentsToOptimize.Contains(info))
                    {
                        last++;
                        break;
                    }
                }
                
                if (last > 0)
                {
                    
                    spec = new MergeSpecification();
                    
                    // First, enroll all "full" merges (size
                    // mergeFactor) to potentially be run concurrently:
                    while (last - maxNumSegments + 1 >= mergeFactor)
                    {
                        spec.Add(MakeOneMerge(infos, infos.Range(last - mergeFactor, last)));
                        last -= mergeFactor;
                    }
                    
                    // Only if there are no full merges pending do we
                    // add a final partial (< mergeFactor segments) merge:
                    if (0 == spec.merges.Count)
                    {
                        if (maxNumSegments == 1)
                        {
                            
                            // Since we must optimize down to 1 segment, the
                            // choice is simple:
                            if (last > 1 || !IsOptimized(infos.Info(0)))
                                spec.Add(MakeOneMerge(infos, infos.Range(0, last)));
                        }
                        else if (last > maxNumSegments)
                        {
                            
                            // Take care to pick a partial merge that is
                            // least cost, but does not make the index too
                            // lopsided.  If we always just picked the
                            // partial tail then we could produce a highly
                            // lopsided index over time:
                            
                            // We must merge this many segments to leave
                            // maxNumSegments in the index (from when
                            // optimize was first kicked off):
                            int finalMergeSize = last - maxNumSegments + 1;
                            
                            // Consider all possible starting points:
                            long bestSize = 0;
                            int bestStart = 0;
                            
                            for (int i = 0; i < last - finalMergeSize + 1; i++)
                            {
                                long sumSize = 0;
                                for (int j = 0; j < finalMergeSize; j++)
                                    sumSize += Size(infos.Info(j + i));
                                if (i == 0 || (sumSize < 2 * Size(infos.Info(i - 1)) && sumSize < bestSize))
                                {
                                    bestStart = i;
                                    bestSize = sumSize;
                                }
                            }

                            spec.Add(MakeOneMerge(infos, infos.Range(bestStart, bestStart + finalMergeSize)));
                        }
                    }
                }
                else
                    spec = null;
            }
            else
                spec = null;
            
            return spec;
        }
        
        public override MergeSpecification FindMergesToExpungeDeletes(SegmentInfos segmentInfos)
        {
            int numSegments = segmentInfos.Count;
            
            if (Verbose())
                Message("findMergesToExpungeDeletes: " + numSegments + " segments");
            
            MergeSpecification spec = new MergeSpecification();
            int firstSegmentWithDeletions = - 1;
            for (int i = 0; i < numSegments; i++)
            {
                SegmentInfo info = segmentInfos.Info(i);
                int delCount = writer.NumDeletedDocs(info);
                if (delCount > 0)
                {
                    if (Verbose())
                        Message("  segment " + info.name + " has deletions");
                    if (firstSegmentWithDeletions == - 1)
                        firstSegmentWithDeletions = i;
                    else if (i - firstSegmentWithDeletions == mergeFactor)
                    {
                        // We've seen mergeFactor segments in a row with
                        // deletions, so force a merge now:
                        if (Verbose())
                            Message("  add merge " + firstSegmentWithDeletions + " to " + (i - 1) + " inclusive");
                        spec.Add(MakeOneMerge(segmentInfos, segmentInfos.Range(firstSegmentWithDeletions, i)));
                        firstSegmentWithDeletions = i;
                    }
                }
                else if (firstSegmentWithDeletions != - 1)
                {
                    // End of a sequence of segments with deletions, so,
                    // merge those past segments even if it's fewer than
                    // mergeFactor segments
                    if (Verbose())
                        Message("  add merge " + firstSegmentWithDeletions + " to " + (i - 1) + " inclusive");
                    spec.Add(MakeOneMerge(segmentInfos, segmentInfos.Range(firstSegmentWithDeletions, i)));
                    firstSegmentWithDeletions = - 1;
                }
            }
            
            if (firstSegmentWithDeletions != - 1)
            {
                if (Verbose())
                    Message("  add merge " + firstSegmentWithDeletions + " to " + (numSegments - 1) + " inclusive");
                spec.Add(MakeOneMerge(segmentInfos, segmentInfos.Range(firstSegmentWithDeletions, numSegments)));
            }
            
            return spec;
        }
        
        public override MergeSpecification FindMerges(SegmentInfos infos)
        {
            
            int numSegments = infos.Count;
            if (Verbose())
                Message("findMerges: " + numSegments + " segments");
            
            // Compute levels, which is just log (base mergeFactor)
            // of the size of each segment
            float[] levels = new float[numSegments];
            float norm = (float) System.Math.Log(mergeFactor);
            
            for (int i = 0; i < numSegments; i++)
            {
                SegmentInfo info = infos.Info(i);
                long size = Size(info);
                
                // Floor tiny segments
                if (size < 1)
                    size = 1;
                levels[i] = (float) System.Math.Log(size) / norm;
            }
            
            float levelFloor;
            if (minMergeSize <= 0)
                levelFloor = (float) 0.0;
            else
            {
                levelFloor = (float) (System.Math.Log(minMergeSize) / norm);
            }
            
            // Now, we quantize the log values into levels.  The
            // first level is any segment whose log size is within
            // LEVEL_LOG_SPAN of the max size, or, who has such as
            // segment "to the right".  Then, we find the max of all
            // other segments and use that to define the next level
            // segment, etc.
            
            MergeSpecification spec = null;
            
            int start = 0;
            while (start < numSegments)
            {
                
                // Find max level of all segments not already
                // quantized.
                float maxLevel = levels[start];
                for (int i = 1 + start; i < numSegments; i++)
                {
                    float level = levels[i];
                    if (level > maxLevel)
                        maxLevel = level;
                }
                
                // Now search backwards for the rightmost segment that
                // falls into this level:
                float levelBottom;
                if (maxLevel < levelFloor)
                // All remaining segments fall into the min level
                    levelBottom = - 1.0F;
                else
                {
                    levelBottom = (float) (maxLevel - LEVEL_LOG_SPAN);
                    
                    // Force a boundary at the level floor
                    if (levelBottom < levelFloor && maxLevel >= levelFloor)
                        levelBottom = levelFloor;
                }
                
                int upto = numSegments - 1;
                while (upto >= start)
                {
                    if (levels[upto] >= levelBottom)
                    {
                        break;
                    }
                    upto--;
                }
                if (Verbose())
                    Message("  level " + levelBottom + " to " + maxLevel + ": " + (1 + upto - start) + " segments");
                
                // Finally, record all merges that are viable at this level:
                int end = start + mergeFactor;
                while (end <= 1 + upto)
                {
                    bool anyTooLarge = false;
                    for (int i = start; i < end; i++)
                    {
                        SegmentInfo info = infos.Info(i);
                        anyTooLarge |= (Size(info) >= maxMergeSize || SizeDocs(info) >= maxMergeDocs);
                    }
                    
                    if (!anyTooLarge)
                    {
                        if (spec == null)
                            spec = new MergeSpecification();
                        if (Verbose())
                            Message("    " + start + " to " + end + ": add this merge");
                        spec.Add(MakeOneMerge(infos, infos.Range(start, end)));
                    }
                    else if (Verbose())
                        Message("    " + start + " to " + end + ": contains segment over maxMergeSize or maxMergeDocs; skipping");
                    
                    start = end;
                    end = start + mergeFactor;
                }
                
                start = 1 + upto;
            }
            
            return spec;
        }
        
        protected OneMerge MakeOneMerge(SegmentInfos infos, SegmentInfos infosToMerge)
        {
            bool doCFS;
            if (!useCompoundFile)
            {
                doCFS = false;
            }
            else if (internalNoCFSRatio == 1.0)
            {
                doCFS = true;
            }
            else
            {
                long totSize = 0;
                foreach(SegmentInfo info in infos)
                {
                    totSize += Size(info);
                }
                long mergeSize = 0;
                foreach(SegmentInfo info in infosToMerge)
                {
                    mergeSize += Size(info);
                }

                doCFS = mergeSize <= internalNoCFSRatio * totSize;
            }

            return new OneMerge(infosToMerge, doCFS);
        }

        public virtual int MaxMergeDocs
        {
            set { this.maxMergeDocs = value; }
            get { return maxMergeDocs; }
        }
    }
}