--- /dev/null
+/*\r
+\r
+ Derby - Class org.apache.derby.impl.store.access.sort.MergeInserter\r
+\r
+ Licensed to the Apache Software Foundation (ASF) under one or more\r
+ contributor license agreements. See the NOTICE file distributed with\r
+ this work for additional information regarding copyright ownership.\r
+ The ASF licenses this file to you under the Apache License, Version 2.0\r
+ (the "License"); you may not use this file except in compliance with\r
+ the License. You may obtain a copy of the License at\r
+\r
+ http://www.apache.org/licenses/LICENSE-2.0\r
+\r
+ Unless required by applicable law or agreed to in writing, software\r
+ distributed under the License is distributed on an "AS IS" BASIS,\r
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+ See the License for the specific language governing permissions and\r
+ limitations under the License.\r
+\r
+ */\r
+\r
+package org.apache.derby.impl.store.access.sort;\r
+\r
+import java.util.Vector;\r
+import org.apache.derby.iapi.services.sanity.SanityManager;\r
+import org.apache.derby.iapi.error.StandardException;\r
+import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;\r
+import org.apache.derby.iapi.store.access.SortController;\r
+import org.apache.derby.iapi.store.access.SortInfo;\r
+\r
+import org.apache.derby.iapi.types.DataValueDescriptor;\r
+\r
+/**\r
+\r
+\r
+**/\r
+\r
+final class MergeInserter implements SortController\r
+{\r
+ /**\r
+ The sort this inserter is for.\r
+ **/\r
+ private MergeSort sort;\r
+\r
+ /**\r
+ The transaction this inserter is in.\r
+ **/\r
+ private TransactionManager tran;\r
+\r
+ /**\r
+ A vector of the conglomerate ids of the merge runs.\r
+ **/\r
+ private Vector mergeRuns;\r
+\r
+ /**\r
+ An in-memory ordered set that is used to sort rows\r
+ before they're sent to merge runs.\r
+ **/\r
+ private SortBuffer sortBuffer;\r
+\r
+ /**\r
+ Information about memory usage to dynamically tune the\r
+ in-memory sort buffer size.\r
+ */\r
+ private long beginFreeMemory;\r
+ private long beginTotalMemory;\r
+ private long estimatedMemoryUsed;\r
+ private boolean avoidMergeRun; // try to avoid merge run if possible\r
+ private int runSize;\r
+ private int totalRunSize;\r
+\r
+ String stat_sortType;\r
+ int stat_numRowsInput;\r
+ int stat_numRowsOutput;\r
+ int stat_numMergeRuns;\r
+ Vector stat_mergeRunsSize;\r
+\r
+\r
+ /*\r
+ * Methods of SortController\r
+ */\r
+\r
+ /**\r
+ Insert a row into the sort.\r
+ @see SortController#insert\r
+ **/\r
+ public void insert(DataValueDescriptor[] row)\r
+ throws StandardException\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ // If the sort is null, probably the caller forgot\r
+ // to call initialize.\r
+ SanityManager.ASSERT(sort != null);\r
+ }\r
+\r
+ // Check that the inserted row is of the correct type\r
+ sort.checkColumnTypes(row);\r
+\r
+ // Insert the row into the sort buffer, which will\r
+ // sort it into the right order with the rest of the\r
+ // rows and remove any duplicates.\r
+ int insertResult = sortBuffer.insert(row);\r
+ stat_numRowsInput++;\r
+ if (insertResult != SortBuffer.INSERT_DUPLICATE)\r
+ stat_numRowsOutput++;\r
+ if (insertResult == SortBuffer.INSERT_FULL)\r
+ {\r
+ if (avoidMergeRun)\r
+ {\r
+ Runtime jvm = Runtime.getRuntime();\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ if (SanityManager.DEBUG_ON("SortTuning"))\r
+ {\r
+ jvm.gc();\r
+ jvm.gc();\r
+ jvm.gc();\r
+ }\r
+ }\r
+\r
+ long currentFreeMemory = jvm.freeMemory();\r
+ long currentTotalMemory = jvm.totalMemory();\r
+\r
+ // before we create an external sort, which is expensive, see if\r
+ // we can use up more in-memory sort buffer\r
+ // we see how much memory has been used between now and the\r
+ // beginning of the sort. Not all of this memory is used by\r
+ // the sort and GC may have kicked in and release some memory.\r
+ // But it is a rough guess.\r
+ estimatedMemoryUsed = (currentTotalMemory-currentFreeMemory) -\r
+ (beginTotalMemory-beginFreeMemory);\r
+\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ if (SanityManager.DEBUG_ON("SortTuning"))\r
+ {\r
+ SanityManager.DEBUG("SortTuning",\r
+ "Growing sortBuffer dynamically, " +\r
+ "current sortBuffer capacity= " + \r
+ sortBuffer.capacity() +\r
+ " estimatedMemoryUsed = " + estimatedMemoryUsed +\r
+ " currentTotalMemory = " + currentTotalMemory +\r
+ " currentFreeMemory = " + currentFreeMemory +\r
+ " numcolumn = " + row.length +\r
+ " real per row memory = " + \r
+ (estimatedMemoryUsed / sortBuffer.capacity()));\r
+ }\r
+ }\r
+\r
+ // we want to double the sort buffer size if that will result\r
+ // in the sort to use up no more than 1/2 of all the free\r
+ // memory (including the sort memory)\r
+ // or if GC is so effective we are now using less memory than before\r
+ // or if we are using less than 1Meg of memory and the jvm is\r
+ // using < 5 meg of memory (this indicates that the JVM can\r
+ // afford to be more bloated ?)\r
+ if (estimatedMemoryUsed < 0 ||\r
+ ((2*estimatedMemoryUsed) < (estimatedMemoryUsed+currentFreeMemory)/2) ||\r
+ (2*estimatedMemoryUsed < ExternalSortFactory.DEFAULT_MEM_USE &&\r
+ currentTotalMemory < (5*1024*1024)))\r
+ {\r
+ // ok, double the sort buffer size\r
+ sortBuffer.grow(100);\r
+\r
+ if (sortBuffer.insert(row) != SortBuffer.INSERT_FULL)\r
+ return;\r
+ }\r
+\r
+ avoidMergeRun = false; // once we did it, too late to do in\r
+ // memory sort\r
+ }\r
+\r
+ // The sort buffer became full. Empty it into a\r
+ // merge run, and add the merge run to the vector\r
+ // of merge runs.\r
+ stat_sortType = "external";\r
+ long conglomid = sort.createMergeRun(tran, sortBuffer);\r
+ if (mergeRuns == null)\r
+ mergeRuns = new Vector();\r
+ mergeRuns.addElement(new Long(conglomid));\r
+\r
+ stat_numMergeRuns++;\r
+ // calculate size of this merge run\r
+ // buffer was too full for last row\r
+ runSize = stat_numRowsInput - totalRunSize - 1;\r
+ totalRunSize += runSize;\r
+ stat_mergeRunsSize.addElement(new Integer(runSize));\r
+\r
+ // Re-insert the row into the sort buffer.\r
+ // This is guaranteed to work since the sort\r
+ // buffer has just been emptied.\r
+ sortBuffer.insert(row);\r
+ }\r
+ }\r
+\r
+ /**\r
+ * Called when the caller has completed\r
+ * inserting rows into the sorter.\r
+\r
+ @see SortController#completedInserts\r
+ **/\r
+\r
+ public void completedInserts()\r
+ {\r
+ // Tell the sort that we're closed, and hand off\r
+ // the sort buffer and the vector of merge runs.\r
+ if (sort != null)\r
+ sort.doneInserting(this, sortBuffer, mergeRuns);\r
+\r
+ // if this is an external sort, there will actually\r
+ // be one last merge run with the contents of the\r
+ // current sortBuffer. It will be created when the user\r
+ // reads the result of the sort using openSortScan\r
+ if (stat_sortType == "external")\r
+ {\r
+ stat_numMergeRuns++;\r
+ stat_mergeRunsSize.addElement(new Integer(stat_numRowsInput - totalRunSize));\r
+ }\r
+\r
+ // close the SortController in the transaction.\r
+ tran.closeMe(this);\r
+\r
+ // Clean up.\r
+ sort = null;\r
+ tran = null;\r
+ mergeRuns = null;\r
+ sortBuffer = null;\r
+ }\r
+\r
+ /*\r
+ * Methods of MergeInserter. Arranged alphabetically.\r
+ */\r
+\r
+ /**\r
+ * Return SortInfo object which contains information about the current\r
+ * sort.\r
+ * <p>\r
+ *\r
+ * @see SortInfo\r
+ *\r
+ * @return The SortInfo object which contains info about current sort.\r
+ *\r
+ * @exception StandardException Standard exception policy.\r
+ **/\r
+ public SortInfo getSortInfo()\r
+ throws StandardException\r
+ {\r
+ return(new MergeSortInfo(this));\r
+ }\r
+\r
+\r
+ /**\r
+ Initialize this inserter.\r
+ @return true if initialization was successful\r
+ **/\r
+ boolean initialize(MergeSort sort, TransactionManager tran)\r
+ {\r
+ Runtime jvm = Runtime.getRuntime();\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ if (SanityManager.DEBUG_ON("SortTuning"))\r
+ {\r
+ jvm.gc();\r
+ jvm.gc();\r
+ jvm.gc();\r
+ }\r
+ }\r
+\r
+ beginFreeMemory = jvm.freeMemory();\r
+ beginTotalMemory = jvm.totalMemory();\r
+ estimatedMemoryUsed = 0;\r
+ avoidMergeRun = true; // not an external sort\r
+ stat_sortType = "internal";\r
+ stat_numMergeRuns = 0;\r
+ stat_numRowsInput = 0;\r
+ stat_numRowsOutput = 0;\r
+ stat_mergeRunsSize = new Vector();\r
+ runSize = 0;\r
+ totalRunSize = 0;\r
+\r
+\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ if (SanityManager.DEBUG_ON("testSort"))\r
+ {\r
+ avoidMergeRun = false;\r
+ }\r
+ }\r
+\r
+ this.sort = sort;\r
+ this.tran = tran;\r
+ sortBuffer = new SortBuffer(sort);\r
+ if (sortBuffer.init() == false)\r
+ return false;\r
+ return true;\r
+ }\r
+\r
+}\r