KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > impl > store > access > sort > MergeInserter


1 /*
2
3    Derby - Class org.apache.derby.impl.store.access.sort.MergeInserter
4
5    Licensed to the Apache Software Foundation (ASF) under one or more
6    contributor license agreements. See the NOTICE file distributed with
7    this work for additional information regarding copyright ownership.
8    The ASF licenses this file to you under the Apache License, Version 2.0
9    (the "License"); you may not use this file except in compliance with
10    the License. You may obtain a copy of the License at
11
12       http://www.apache.org/licenses/LICENSE-2.0
13
14    Unless required by applicable law or agreed to in writing, software
15    distributed under the License is distributed on an "AS IS" BASIS,
16    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17    See the License for the specific language governing permissions and
18    limitations under the License.
19
20  */
21
22 package org.apache.derby.impl.store.access.sort;
23
24 import java.util.Vector JavaDoc;
25 import org.apache.derby.iapi.services.sanity.SanityManager;
26 import org.apache.derby.iapi.services.io.Storable;
27 import org.apache.derby.iapi.error.StandardException;
28 import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;
29 import org.apache.derby.iapi.store.access.ColumnOrdering;
30 import org.apache.derby.iapi.store.access.ConglomerateController;
31 import org.apache.derby.iapi.store.access.Qualifier;
32 import org.apache.derby.iapi.store.access.ScanController;
33 import org.apache.derby.iapi.store.access.SortController;
34 import org.apache.derby.iapi.store.access.SortInfo;
35 import org.apache.derby.iapi.store.access.TransactionController;
36
37 import org.apache.derby.iapi.types.DataValueDescriptor;
38
39 import org.apache.derby.iapi.types.RowLocation;
40
41 /**
42
43
44 **/
45
46 public final class MergeInserter implements SortController
47 {
48     /**
49     The sort this inserter is for.
50     **/
51     protected MergeSort sort = null;
52
53     /**
54     The transaction this inserter is in.
55     **/
56     protected TransactionManager tran;
57
58     /**
59     A vector of the conglomerate ids of the merge runs.
60     **/
61     Vector JavaDoc mergeRuns = null;
62
63     /**
64     An in-memory ordered set that is used to sort rows
65     before they're sent to merge runs.
66     **/
67     SortBuffer sortBuffer = null;
68
69     /**
70     Information about memory usage to dynamically tune the
71     in-memory sort buffer size.
72     */
73     long beginFreeMemory;
74     long beginTotalMemory;
75     long estimatedMemoryUsed;
76     boolean avoidMergeRun; // try to avoid merge run if possible
77 int runSize;
78     int totalRunSize;
79
80     protected String JavaDoc stat_sortType;
81     protected int stat_numRowsInput;
82     protected int stat_numRowsOutput;
83     protected int stat_numMergeRuns;
84     protected Vector JavaDoc stat_mergeRunsSize;
85
86
87     /*
88      * Methods of SortController
89      */
90
91     /**
92     Insert a row into the sort.
93     @see SortController#insert
94     **/
95     public void insert(DataValueDescriptor[] row)
96         throws StandardException
97     {
98         if (SanityManager.DEBUG)
99         {
100             // If the sort is null, probably the caller forgot
101 // to call initialize.
102 SanityManager.ASSERT(sort != null);
103         }
104
105         // Check that the inserted row is of the correct type
106 sort.checkColumnTypes(row);
107
108         // Insert the row into the sort buffer, which will
109 // sort it into the right order with the rest of the
110 // rows and remove any duplicates.
111 int insertResult = sortBuffer.insert(row);
112         stat_numRowsInput++;
113         if (insertResult != SortBuffer.INSERT_DUPLICATE)
114             stat_numRowsOutput++;
115         if (insertResult == SortBuffer.INSERT_FULL)
116         {
117             if (avoidMergeRun)
118             {
119                 Runtime JavaDoc jvm = Runtime.getRuntime();
120                 if (SanityManager.DEBUG)
121                 {
122                     if (SanityManager.DEBUG_ON("SortTuning"))
123                     {
124                         jvm.gc();
125                         jvm.gc();
126                         jvm.gc();
127                     }
128                 }
129
130                 long currentFreeMemory = jvm.freeMemory();
131                 long currentTotalMemory = jvm.totalMemory();
132
133                 // before we create an external sort, which is expensive, see if
134 // we can use up more in-memory sort buffer
135 // we see how much memory has been used between now and the
136 // beginning of the sort. Not all of this memory is used by
137 // the sort and GC may have kicked in and release some memory.
138 // But it is a rough guess.
139 estimatedMemoryUsed = (currentTotalMemory-currentFreeMemory) -
140                     (beginTotalMemory-beginFreeMemory);
141
142                 if (SanityManager.DEBUG)
143                 {
144                     if (SanityManager.DEBUG_ON("SortTuning"))
145                     {
146                         SanityManager.DEBUG("SortTuning",
147                             "Growing sortBuffer dynamically, " +
148                             "current sortBuffer capacity= " +
149                                 sortBuffer.capacity() +
150                             " estimatedMemoryUsed = " + estimatedMemoryUsed +
151                             " currentTotalMemory = " + currentTotalMemory +
152                             " currentFreeMemory = " + currentFreeMemory +
153                             " numcolumn = " + row.length +
154                             " real per row memory = " +
155                                 (estimatedMemoryUsed / sortBuffer.capacity()));
156                     }
157                 }
158
159                 // we want to double the sort buffer size if that will result
160 // in the sort to use up no more than 1/2 of all the free
161 // memory (including the sort memory)
162 // or if GC is so effective we are now using less memory than before
163 // or if we are using less than 1Meg of memory and the jvm is
164 // using < 5 meg of memory (this indicates that the JVM can
165 // afford to be more bloated ?)
166 if (estimatedMemoryUsed < 0 ||
167                     ((2*estimatedMemoryUsed) < (estimatedMemoryUsed+currentFreeMemory)/2) ||
168                     (2*estimatedMemoryUsed < ExternalSortFactory.DEFAULT_MEM_USE &&
169                      currentTotalMemory < (5*1024*1024)))
170                 {
171                     // ok, double the sort buffer size
172 sortBuffer.grow(100);
173
174                     if (sortBuffer.insert(row) != SortBuffer.INSERT_FULL)
175                         return;
176                 }
177
178                 avoidMergeRun = false; // once we did it, too late to do in
179 // memory sort
180 }
181
182             // The sort buffer became full. Empty it into a
183 // merge run, and add the merge run to the vector
184 // of merge runs.
185 stat_sortType = "external";
186             long conglomid = sort.createMergeRun(tran, sortBuffer);
187             if (mergeRuns == null)
188                 mergeRuns = new Vector JavaDoc();
189             mergeRuns.addElement(new Long JavaDoc(conglomid));
190
191             stat_numMergeRuns++;
192             // calculate size of this merge run
193 // buffer was too full for last row
194 runSize = stat_numRowsInput - totalRunSize - 1;
195             totalRunSize += runSize;
196             stat_mergeRunsSize.addElement(new Integer JavaDoc(runSize));
197
198             // Re-insert the row into the sort buffer.
199 // This is guaranteed to work since the sort
200 // buffer has just been emptied.
201 sortBuffer.insert(row);
202         }
203     }
204
205     /**
206     Close this sort controller. Closing the sort controller
207     means the caller is done inserting rows. This method
208     must not throw any exceptions since it's called during
209     error processing.
210
211     @see SortController#close
212     **/
213
214     public void close()
215     {
216         // Tell the sort that we're closed, and hand off
217 // the sort buffer and the vector of merge runs.
218 if (sort != null)
219             sort.doneInserting(this, sortBuffer, mergeRuns);
220
221         // if this is an external sort, there will actually
222 // be one last merge run with the contents of the
223 // current sortBuffer. It will be created when the user
224 // reads the result of the sort using openSortScan
225 if (stat_sortType == "external")
226         {
227             stat_numMergeRuns++;
228             stat_mergeRunsSize.addElement(new Integer JavaDoc(stat_numRowsInput - totalRunSize));
229         }
230
231         // close the SortController in the transaction.
232 tran.closeMe(this);
233
234         // Clean up.
235 sort = null;
236         tran = null;
237         mergeRuns = null;
238         sortBuffer = null;
239     }
240
241     /*
242      * Methods of MergeInserter. Arranged alphabetically.
243      */
244
245     /**
246      * Return SortInfo object which contains information about the current
247      * sort.
248      * <p>
249      *
250      * @see SortInfo
251      *
252      * @return The SortInfo object which contains info about current sort.
253      *
254      * @exception StandardException Standard exception policy.
255      **/
256     public SortInfo getSortInfo()
257         throws StandardException
258     {
259         return(new MergeSortInfo(this));
260     }
261
262
263     /**
264     Initialize this inserter.
265     @return true if initialization was successful
266     **/
267     boolean initialize(MergeSort sort, TransactionManager tran)
268     {
269         Runtime JavaDoc jvm = Runtime.getRuntime();
270         if (SanityManager.DEBUG)
271         {
272             if (SanityManager.DEBUG_ON("SortTuning"))
273             {
274                 jvm.gc();
275                 jvm.gc();
276                 jvm.gc();
277             }
278         }
279
280         beginFreeMemory = jvm.freeMemory();
281         beginTotalMemory = jvm.totalMemory();
282         estimatedMemoryUsed = 0;
283         avoidMergeRun = true; // not an external sort
284 stat_sortType = "internal";
285         stat_numMergeRuns = 0;
286         stat_numRowsInput = 0;
287         stat_numRowsOutput = 0;
288         stat_mergeRunsSize = new Vector JavaDoc();
289         runSize = 0;
290         totalRunSize = 0;
291
292
293         if (SanityManager.DEBUG)
294         {
295             if (SanityManager.DEBUG_ON("testSort"))
296             {
297                 avoidMergeRun = false;
298             }
299         }
300
301         this.sort = sort;
302         this.tran = tran;
303         sortBuffer = new SortBuffer(sort);
304         if (sortBuffer.init() == false)
305             return false;
306         return true;
307     }
308
309 }
310
Popular Tags