trafodion-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sand...@apache.org
Subject [1/7] incubator-trafodion git commit: [TRAFODION-2259] TopN sort changes. This includes first of changes related to sort implementation in executor. cqd gen_sort_topn_size 'N' forces sort to use topn. Subsequent changes in compiler will be able to push d
Date Tue, 11 Oct 2016 21:02:58 GMT
Repository: incubator-trafodion
Updated Branches:
  refs/heads/master a9f34a6a1 -> 75048b0f3


[TRAFODION-2259] TopN sort changes.
This includes first of changes related to sort implementation in executor.
cqd gen_sort_topn_size 'N' forces sort to use topn.
Subsequent changes in compiler will be able to push down topn to sort.


Project: http://git-wip-us.apache.org/repos/asf/incubator-trafodion/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-trafodion/commit/61cc7b5b
Tree: http://git-wip-us.apache.org/repos/asf/incubator-trafodion/tree/61cc7b5b
Diff: http://git-wip-us.apache.org/repos/asf/incubator-trafodion/diff/61cc7b5b

Branch: refs/heads/master
Commit: 61cc7b5b26d760839e6515b3e7cc94d8ed5ed879
Parents: b8dc6da
Author: Prashant Vasudev <prashanth.vasudev@esgyn.com>
Authored: Tue Oct 4 05:45:43 2016 +0000
Committer: Prashant Vasudev <prashanth.vasudev@esgyn.com>
Committed: Tue Oct 4 05:45:43 2016 +0000

----------------------------------------------------------------------
 core/sql/comexe/ComTdbSort.h        |   9 +-
 core/sql/executor/ex_sort.cpp       |   1 +
 core/sql/generator/GenRelMisc.cpp   |   3 +
 core/sql/nskgmake/sort/Makefile     |   3 +-
 core/sql/sort/Qsort.h               |   5 +-
 core/sql/sort/Record.cpp            |  14 +-
 core/sql/sort/Record.h              |   8 +
 core/sql/sort/SortUtil.cpp          |  22 +-
 core/sql/sort/SortUtilCfg.cpp       |  42 ----
 core/sql/sort/SortUtilCfg.h         |  13 +-
 core/sql/sort/Topn.cpp              | 337 +++++++++++++++++++++++++++++++
 core/sql/sort/Topn.h                |  89 ++++++++
 core/sql/sqlcomp/DefaultConstants.h |   1 +
 core/sql/sqlcomp/nadefaults.cpp     |   1 +
 14 files changed, 490 insertions(+), 58 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/comexe/ComTdbSort.h
----------------------------------------------------------------------
diff --git a/core/sql/comexe/ComTdbSort.h b/core/sql/comexe/ComTdbSort.h
index 5ddc950..93a1a81 100644
--- a/core/sql/comexe/ComTdbSort.h
+++ b/core/sql/comexe/ComTdbSort.h
@@ -204,8 +204,9 @@ protected:
   Float32 bmoCitizenshipFactor_;                        // 68-71
   Int32  pMemoryContingencyMB_;                        // 72-75
   UInt16 sortGrowthPercent_;                            // 76-77
-  
-  char fillersComTdbSort_[18];                          // 78-95
+  char   filler2_[2];                                   // 78-79
+  ULng32 topNSize_;                                     // 80-83
+  char fillersComTdbSort_[12];                          // 84-95
 
 public:
 
@@ -326,6 +327,10 @@ public:
     {  pMemoryContingencyMB_ = mCMB;} 
   Int32 getMemoryContingencyMB(void)
     { return pMemoryContingencyMB_; }
+  void setTopNSize(UInt32 size)
+  	{  topNSize_ = size; }
+  ULng32 getTopNSize(void)
+	{  return topNSize_; }
 
   void setSortMemEstInMbPerCpu(Float32 s) {sortMemEstInMbPerCpu_=s;}
   Float32 getSortMemEstInMbPerCpu() {return sortMemEstInMbPerCpu_;}

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/executor/ex_sort.cpp
----------------------------------------------------------------------
diff --git a/core/sql/executor/ex_sort.cpp b/core/sql/executor/ex_sort.cpp
index c200737..e655abd 100644
--- a/core/sql/executor/ex_sort.cpp
+++ b/core/sql/executor/ex_sort.cpp
@@ -242,6 +242,7 @@ ExSortTcb::ExSortTcb(const ExSortTdb & sort_tdb,
   sortCfg_->setIntermediateScratchCleanup(st->sortOptions_->intermediateScratchCleanup());
   sortCfg_->setResizeCifRecord(st->sortOptions_->resizeCifRecord());
   sortCfg_->setConsiderBufferDefrag(st->sortOptions_->considerBufferDefrag());
+  sortCfg_->setTopNSize(st->getTopNSize());
 
   switch(st->getOverFlowMode())
   {

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/generator/GenRelMisc.cpp
----------------------------------------------------------------------
diff --git a/core/sql/generator/GenRelMisc.cpp b/core/sql/generator/GenRelMisc.cpp
index d37a8e6..a12186f 100644
--- a/core/sql/generator/GenRelMisc.cpp
+++ b/core/sql/generator/GenRelMisc.cpp
@@ -3224,6 +3224,9 @@ short Sort::generateTdb(Generator * generator,
 
   sort_tdb->setSortFromTop(sortFromTop());
   sort_tdb->setOverflowMode(generator->getOverflowMode());
+  
+  sort_tdb->setTopNSize((ULng32)getDefault(GEN_SORT_TOPN_SIZE));
+  
 
   if (generator->getUserSidetreeInsert())
     sort_tdb->setUserSidetreeInsert(TRUE);

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/nskgmake/sort/Makefile
----------------------------------------------------------------------
diff --git a/core/sql/nskgmake/sort/Makefile b/core/sql/nskgmake/sort/Makefile
index 9aa1504..b0b7401 100755
--- a/core/sql/nskgmake/sort/Makefile
+++ b/core/sql/nskgmake/sort/Makefile
@@ -36,7 +36,8 @@ CPPSRC := CommonUtil.cpp \
 	SortUtilCfg.cpp \
 	Statistics.cpp \
 	TourTree.cpp \
-	TreeNode.cpp
+	TreeNode.cpp \
+	Topn.cpp
 
 CPPSRC += vers_libsort.cpp
 

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/sort/Qsort.h
----------------------------------------------------------------------
diff --git a/core/sql/sort/Qsort.h b/core/sql/sort/Qsort.h
index 00aeb3f..af1c7e6 100644
--- a/core/sql/sort/Qsort.h
+++ b/core/sql/sort/Qsort.h
@@ -112,10 +112,7 @@ class ExBMOStats;
 // to be used for quicksort.
 //----------------------------------------------------------------------
 
-struct RecKeyBuffer   {
-  char* key_;
-  Record* rec_;
-};
+
 void heapSort(RecKeyBuffer keysToSort[], Int32 runsize);
 void siftDown(RecKeyBuffer keysToSort[], Int32 root, Int32 bottom);
 

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/sort/Record.cpp
----------------------------------------------------------------------
diff --git a/core/sql/sort/Record.cpp b/core/sql/sort/Record.cpp
index 4184d69..2437575 100644
--- a/core/sql/sort/Record.cpp
+++ b/core/sql/sort/Record.cpp
@@ -55,11 +55,23 @@ Record::Record(ULng32 size, NABoolean doNotallocRec, CollHeap* heap)
   }
 }
 
+Record::Record(void *rec, ULng32 reclen, void* tupp, CollHeap* heap, SortError* sorterror)
+{
+	 recSize_   = reclen;
+	 sortError_ = sorterror;
+	 heap_      = heap;
+	 tupp_      = tupp;
+	 allocatedRec_ = FALSE_L; 
+	 rec_ =(char *) rec;
+}
+
+
 //----------------------------------------------------------------------
 // Record Destructor.
 //----------------------------------------------------------------------
 Record::~Record(void)
-{
+{    
+
   if (allocatedRec_ && rec_ != NULL) {
      NADELETEBASIC(rec_, heap_);
     rec_ = NULL;

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/sort/Record.h
----------------------------------------------------------------------
diff --git a/core/sql/sort/Record.h b/core/sql/sort/Record.h
index 4b66f63..8928d45 100644
--- a/core/sql/sort/Record.h
+++ b/core/sql/sort/Record.h
@@ -47,11 +47,19 @@
 #include "NABasicObject.h"
 #include "SortError.h"
 
+class Record;
+
+struct RecKeyBuffer   {
+	  char* key_;
+	  Record* rec_;
+	};
+	
 class Record   {
   public :
 
     Record();
     Record(ULng32 size, NABoolean doNotallocRec, CollHeap* heap);
+    Record(void *rec, ULng32 reclen, void* tupp, CollHeap* heap, SortError* sorterror);
     ~Record(void);
 
     void initialize(ULng32 recsize, NABoolean doNotallocRec, 

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/sort/SortUtil.cpp
----------------------------------------------------------------------
diff --git a/core/sql/sort/SortUtil.cpp b/core/sql/sort/SortUtil.cpp
index 64fb793..433e815 100644
--- a/core/sql/sort/SortUtil.cpp
+++ b/core/sql/sort/SortUtil.cpp
@@ -45,6 +45,7 @@
 #include "ex_sort.h"
 #include "SortUtil.h"
 #include "Qsort.h"
+#include "Topn.h"
 #include "ComCextdecs.h"
 #include "logmxevent.h"
 #include "ExStats.h"
@@ -158,7 +159,10 @@ NABoolean SortUtil::sortInitialize(SortUtilConfig& config)
   //---------------------------------------------------------------
   doCleanUp();
   
-  sortAlgo_ =
+  //if topNSize_ is set, then use TopN.
+  if(!config.topNSize_)
+  {
+    sortAlgo_ =
 	new (config.heapAddr_) Qsort(config.runSize_,
 								 config.maxMem_,
 								 config.recSize_,
@@ -170,6 +174,22 @@ NABoolean SortUtil::sortInitialize(SortUtilConfig& config)
 								 &sortError_,
 								 explainNodeId_,
 								 this);
+  }
+  else
+  {
+	  sortAlgo_ =
+			new (config.heapAddr_) TopN(config.topNSize_,
+										 config.maxMem_,
+										 config.recSize_,
+										 config.sortType_.doNotAllocRec_,
+										 config.keySize_,
+										 scratch_,
+										 TRUE,
+										 config.heapAddr_,
+										 &sortError_,
+										 explainNodeId_,
+										 this);
+  }
 	if (sortAlgo_ == NULL)
 	{
 		sortError_.setErrorInfo( EScrNoMemory   //sort error

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/sort/SortUtilCfg.cpp
----------------------------------------------------------------------
diff --git a/core/sql/sort/SortUtilCfg.cpp b/core/sql/sort/SortUtilCfg.cpp
index 81ed8ab..25bca77 100644
--- a/core/sql/sort/SortUtilCfg.cpp
+++ b/core/sql/sort/SortUtilCfg.cpp
@@ -225,48 +225,6 @@ NABoolean SortUtilConfig::setKeyInfo(ULng32 keysize)
   return SORT_SUCCESS;
 }
 
-
-
-//----------------------------------------------------------------------
-// Name         : setTemps
-// 
-// Parameters   : ...
-//
-// Description  : 
-//
-// Return Value :
-//   SORT_SUCCESS if everything goes on well.
-//   SORT_FAILURE if any error encounterd. 
-//
-//----------------------------------------------------------------------
-NABoolean SortUtilConfig::setTemps(ULng32 runsize=100L,
-                                   ULng32 mergeorder=10L)
-{
-  runSize_    = runsize;
-  mergeOrder_ = mergeorder;
- 
-  return SORT_SUCCESS;
-}
-
-
-//----------------------------------------------------------------------
-// Name         : getTemps
-// 
-// Parameters   : ...
-//
-// Description  : 
-//
-// Return Value :
-//   SORT_SUCCESS if everything goes on well.
-//   SORT_FAILURE if any error encounterd. 
-//
-//----------------------------------------------------------------------
-NABoolean SortUtilConfig::getTemps() const
-{
- return SORT_SUCCESS;
-}
-
-
 void SortUtilConfig::setUseBuffered(NABoolean torf)
 {
   useBufferedWrites_ = torf;

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/sort/SortUtilCfg.h
----------------------------------------------------------------------
diff --git a/core/sql/sort/SortUtilCfg.h b/core/sql/sort/SortUtilCfg.h
index 3a0e946..be7ad9a 100644
--- a/core/sql/sort/SortUtilCfg.h
+++ b/core/sql/sort/SortUtilCfg.h
@@ -87,11 +87,7 @@ public:
       ULng32 getRecSize() const;
 
       NABoolean  setKeyInfo(ULng32 keysize);
-      
-
-      NABoolean setTemps(ULng32 runsize, ULng32 mergesize);
-      NABoolean getTemps() const;
-
+            
       void setUseBuffered(NABoolean torf);
       NABoolean getUseBuffered() ;
 
@@ -152,7 +148,10 @@ public:
      {
        return numEsps_;
      }
-
+     void setTopNSize(ULng32 size)
+     {
+    	 topNSize_ = size;
+     }
      void setEventHandler(ExSubtask *eh)	
      {
       ioEventHandler_ = eh;
@@ -319,7 +318,7 @@ private:
       ULng32 mergeOrder_; // Need to modify this to do automatically.
       ULng32 minMem_;  // Minimum sort heap  memory
       ULng32 maxMem_;  // Maximum sort heap memory
-      ULng32 initialRunSize_; // unused :to be set by the executor
+      ULng32 topNSize_; // TopN size set by the executor
       ULng32 runSizeIncr_; // unused :how much to increment the run size by.
       ULng32 maxNumBuffers_; // Max buffer space as set by the compiler
       unsigned short scratchThreshold_; // percent of disk usage after which a disk will
be discarded for use

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/sort/Topn.cpp
----------------------------------------------------------------------
diff --git a/core/sql/sort/Topn.cpp b/core/sql/sort/Topn.cpp
new file mode 100644
index 0000000..417a795
--- /dev/null
+++ b/core/sql/sort/Topn.cpp
@@ -0,0 +1,337 @@
+/**********************************************************************
+// @@@ START COPYRIGHT @@@
+//
+// 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.
+//
+// @@@ END COPYRIGHT @@@
+**********************************************************************/
+/* -*-C++-*-
+******************************************************************************
+*
+* File:         TopN.cpp
+*                               
+* Description:  This file contains the implementation of all member functions
+*               of the class TopN.
+*               
+* 1. Sort would initially maintain Top N array of elements to being with.
+* 2. Read records into TopN array. 
+* 3. Once TopN array is full, heapify the array into max heap. Top node in the heap is always
the highest node.
+* 4. Subsequent record read either gets discarded( if greater than top node) or replace top
node( if lesser then top node) . if replaced top node, re-balance the heap.
+* 5. Repeat steps 4 until last record is read.
+* 6. sort the final heap using heap sort.
+*******************************************************************************/
+
+#include <iostream>
+#include <fstream>
+
+#ifndef DEBUG
+#undef NDEBUG
+#define NDEBUG
+#endif
+#include "ex_stdh.h"
+#include "Topn.h"
+#include "ScratchSpace.h"
+#include "logmxevent.h"
+#include "SortUtil.h"
+#include "ex_ex.h"
+#include "ExStats.h"
+
+//------------------------------------------------------------------------
+// Class Constructor.
+//------------------------------------------------------------------------
+TopN::TopN(ULng32 runsize, ULng32 sortmaxmem, ULng32  recsize,
+             NABoolean doNotallocRec, ULng32  keysize, 
+             SortScratchSpace* scratch, NABoolean iterSort,
+             CollHeap* heap, SortError* sorterror, Lng32 explainNodeId, SortUtil* sortutil):
+             SortAlgo(runsize, recsize, doNotallocRec, keysize, scratch, explainNodeId),
+             loopIndex_(0), heap_(heap), sortError_(sorterror),
+             sortUtil_(sortutil)
+{
+   //runsize is TopN size. Fixed.
+   allocRunSize_ = runsize;
+   
+   //Actual run size after all elements read.
+   runSize_ = 0;   
+   
+   isHeapified_ = FALSE;
+   
+  //allocateMemory failureIsFatal is defaulted to TRUE means allocation failure results in

+  //longjump to jump handler defined in ex_sort.cpp. Only applicable on NSK.
+  topNKeys_  = (RecKeyBuffer *)heap_->allocateMemory(sizeof(RecKeyBuffer) * allocRunSize_);
 
+ 
+  // Below asserts useful in debug mode. Also asserts if longjmp did not happen.
+  //ex_assert(rootRecord_!= NULL, "Sort: Initial rootRecord_ allocation failed"); 
+  ex_assert(topNKeys_  != NULL, "Sort: Initial topNKeys_ allocation failed");  
+
+  recNum_ = 0;
+  ExOperStats *stat = sortUtil_->config()->getCallingTcb()->getStatsEntry();
+  if (stat)
+    bmoStats_ = stat->castToExBMOStats();
+  else
+    bmoStats_ = NULL;
+  if (bmoStats_)
+    bmoStats_->updateBMOHeapUsage((NAHeap *)heap_);
+}
+
+ 
+//------------------------------------------------------------------------
+// Class Destructor: Delete all the heap space pointed by pointers in Qsort
+//------------------------------------------------------------------------
+TopN::~TopN(void)
+{
+
+  for (int i = 0; i < runSize_; i++)
+	  topNKeys_[i].rec_->releaseTupp();
+
+  
+  if (topNKeys_ != NULL) {
+    NADELETEBASIC(topNKeys_, heap_);
+    topNKeys_ = NULL;
+  }
+  if (bmoStats_)
+    bmoStats_->updateBMOHeapUsage((NAHeap *)heap_);
+
+}
+
+Lng32 TopN::sortSend(void *rec, ULng32 len, void* tupp)		                        
+{
+  //if heap not built means, TopN array has more slots 
+  //available to fill. 
+  if(! isHeapified_)
+  {
+	  ex_assert(loopIndex_ >= 0, "TopN::sortSend: loopIndex_ is < 0");
+	  ex_assert(loopIndex_ < allocRunSize_, "TopN::sortSend: loopIndex_ > allocRunSize_");
+	  ex_assert(rec != NULL, "TopN::sortSend: rec is NULL");
+	
+	  Record * insertRec = new Record(rec, len, tupp, heap_, sortError_);
+	  
+	  topNKeys_[loopIndex_].key_ = insertRec->extractKey(keySize_, sortUtil_->config()->numberOfBytesForRecordSize());
+	  topNKeys_[loopIndex_].rec_ = insertRec;
+	  if (++loopIndex_  == allocRunSize_)
+	  {
+		 //Reaching here means, we have filled up the array. 
+		 //Now heapify the array to start accepting/eliminating new elements from now on.
+		 
+         //Note lookIndex_ contains the current number of filled elements.
+		  
+		 buildHeap();
+	  }
+	  return SORT_SUCCESS;
+  }
+  
+  //Reaching here means, heap is already build. 
+  //Check if the new rec belongs to this heap by comparing the
+  //new rec key with the root node of the heap ( root node is always the greatest).
+  insertRec(rec, len, tupp);
+  return SORT_SUCCESS;
+ }
+
+
+void TopN::buildHeap() 
+{
+	if(!isHeapified_)
+	{
+		//loopIndex_ is now <= TopN
+		runSize_ = loopIndex_;
+	
+		satisfyHeap();
+	
+		isHeapified_ = TRUE;
+	}
+}
+
+//Satisfy Heap makes sure the heap is balanced maxHeap.
+//Note this does not mean heap is sorted. It just makes sure
+//the higher level nodes are greater than lower level nodes.
+//Topmost node or root will be the highest.
+void TopN::satisfyHeap() 
+{
+	for (int i = (runSize_/2 ); i >= 0; i--)
+	    siftDown(topNKeys_, i, runSize_-1);
+}
+
+
+void TopN::insertRec(void *rec, ULng32 len, void* tupp) 
+{
+	ex_assert(isHeapified_, "TopN::insertRec: not heapified");
+
+	int root = 0; //Always, root node is the zero'th element in array.
+	
+	Record * insertRec = new Record(rec, len, tupp, heap_, sortError_);
+	insertRecKey_.key_ = insertRec->extractKey(keySize_, sortUtil_->config()->numberOfBytesForRecordSize());
+	insertRecKey_.rec_ = insertRec;
+
+	if (compare(topNKeys_[root].key_ ,insertRecKey_.key_) == KEY1_IS_GREATER)
+    {
+      swap( &topNKeys_[root],&insertRecKey_);
+
+      
+      //After swap, satisfy or rebalance the heap.
+      satisfyHeap();
+      
+    }
+	
+	//Once swapped, or not swapped, delete the unneeded record.
+	//This step is very important to discard the unwanted record.
+	//Note releaseTupp() also deletes the tupp allocated in sql 
+	//buffer. This makes space for new records read in.
+	insertRecKey_.rec_->releaseTupp();
+    delete insertRecKey_.rec_;
+        
+}
+
+Lng32 TopN::sortSendEnd()
+{
+  Lng32 retcode = SORT_SUCCESS;
+  ex_assert(loopIndex_ >= 0, "TopN::sortSendEnd: loopIndex_ is < 0");
+  
+  buildHeap();
+  sortHeap();
+  
+  return retcode;
+}
+
+void TopN::sortHeap()
+{
+	for (int i = runSize_-1; i >= 1; i--)
+	{
+	  swap(&topNKeys_[0],&topNKeys_[i]);
+	  siftDown(topNKeys_, 0, i-1);
+	}
+}
+
+Lng32 TopN::sortReceive(void *rec, ULng32& len)
+{
+  return SORT_FAILURE;
+}
+
+Lng32 TopN::sortReceive(void*& rec, ULng32& len, void*& tupp)
+{
+  //---------------------------------------------------------------
+  // We use Qsort to receive records only in case of internal sort
+  // for merging.
+  //---------------------------------------------------------------
+  if (recNum_ < runSize_) {
+	  topNKeys_[recNum_].rec_->getRecordTupp(rec, recSize_, tupp);
+    len = recSize_;
+    recNum_++;
+  }
+  else {
+    len = 0;
+  }
+
+  return SORT_SUCCESS;
+}
+/*
+//----------------------------------------------------------------------
+// Name         : heapSort
+//
+// Parameters   : ...
+//
+// Description  : This member function implements the heap sort
+// Return Value :
+//   SORT_SUCCESS if everything goes on well.
+//   SORT_FAILURE if any error encounterd.
+//
+// NOTE: For this implementation no extra buffer is required. It is done all
+// in place. This is the algorithm used if SORT_ITERATIVE_ALGO is set.
+// requirement. If the performance of heapSort is not as good we may switch
+// back to quickSort or iterativeQuickSort.
+
+//----------------------------------------------------------------------
+void TopN::heapSort(RecKeyBuffer keysToSort[], Int64 runsize)
+{
+  Int64 i;
+
+  for (i = (runsize/2 ); i >= 0; i--)
+    siftDown(keysToSort, i, runsize-1);
+
+  for (i = runsize-1; i >= 1; i--)
+  {
+    
+    swap(&keysToSort[0],&keysToSort[i]);
+    siftDown(keysToSort, 0, i-1);
+  }
+}
+*/
+
+void TopN::siftDown(RecKeyBuffer keysToSort[], Int64 root, Int64 bottom)
+{
+  Int64 done, maxChild;
+
+  done = 0;
+  while ((root*2 <= bottom) && (!done))
+  {
+    if (root*2 == bottom)
+      maxChild = root * 2;
+    else if (compare(keysToSort[root * 2].key_ ,
+                     keysToSort[root * 2 + 1].key_) >= KEY1_IS_GREATER)
+      maxChild = root * 2;
+    else
+      maxChild = root * 2 + 1;
+
+    if (compare(keysToSort[root].key_ ,keysToSort[maxChild].key_) <=KEY1_IS_SMALLER)
+    {
+      
+      swap( &keysToSort[root],&keysToSort[maxChild]);
+      root = maxChild;
+      
+    }
+    else
+      done = 1;
+  }
+}
+
+//----------------------------------------------------------------------
+// Name         : swap
+// 
+// Parameters   : ..
+//
+// Description  : Swaps two elements from the QuickSort workspace. May
+//                consider making this inline rather than a seperate
+//                procedure call for performance reasons.
+//                 
+// Recompareturn Value :
+//   SORT_SUCCESS if everything goes on well.
+//   SORT_FAILURE if any error encounterd. 
+//
+//----------------------------------------------------------------------
+
+NABoolean TopN::swap(RecKeyBuffer* recKeyOne, RecKeyBuffer* recKeyTwo)
+{
+	 char* tempKey;
+	 Record* tempRec;
+	
+	
+	 tempKey = recKeyOne->key_;
+	 tempRec = recKeyOne->rec_;
+	
+	
+	 recKeyOne->key_ = recKeyTwo->key_;
+	 recKeyOne->rec_ = recKeyTwo->rec_;
+	
+	
+	 recKeyTwo->key_ = tempKey;
+	 recKeyTwo->rec_ = tempRec;
+	 return SORT_SUCCESS;
+}
+
+UInt32 TopN::getOverheadPerRecord(void)
+{
+  return (sizeof(RecKeyBuffer) + sizeof(Record)); 
+}

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/sort/Topn.h
----------------------------------------------------------------------
diff --git a/core/sql/sort/Topn.h b/core/sql/sort/Topn.h
new file mode 100644
index 0000000..a683536
--- /dev/null
+++ b/core/sql/sort/Topn.h
@@ -0,0 +1,89 @@
+/**********************************************************************
+// @@@ START COPYRIGHT @@@
+//
+// 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.
+//
+// @@@ END COPYRIGHT @@@
+**********************************************************************/
+#ifndef TOPN_H
+#define TOPN_H
+
+/* -*-C++-*-
+******************************************************************************
+*
+* File:         Topn.h
+*
+*
+******************************************************************************
+*/
+
+#include "SortAlgo.h"
+#include "Record.h"
+#include "Const.h"
+#include "NABasicObject.h"
+#include "SortError.h"
+
+
+class SortUtil;
+class ExBMOStats;
+
+
+class TopN : public SortAlgo { //SortAlgo inherits from NABasicObject
+
+public:
+
+   TopN(ULng32 recmax,ULng32 sortmaxmem, ULng32 recsize, NABoolean doNotallocRec, 
+        ULng32 keysize, SortScratchSpace* scratch,NABoolean iterQuickSort,
+        CollHeap* heap, SortError* sorterror, Lng32 explainNodeId, SortUtil* sortutil);
+  ~TopN(void);
+
+  Lng32 sortSend(void* rec, ULng32 len, void* tupp);
+  
+  Lng32 sortClientOutOfMem(void){ return 0;}  
+  
+  Lng32 sortSendEnd();
+
+  Lng32 sortReceive(void* rec, ULng32& len);
+  Lng32 sortReceive(void*& rec, ULng32& len, void*& tupp);
+  UInt32 getOverheadPerRecord(void);
+  Lng32 generateInterRuns(){ return 0;}
+  
+    
+private:
+  void buildHeap();
+  void satisfyHeap();
+  void insertRec(void *rec, ULng32 len, void* tupp);
+  void sortHeap();
+  void siftDown(RecKeyBuffer keysToSort[], Int64 root, Int64 bottom);
+  NABoolean swap(RecKeyBuffer* recKeyOne, RecKeyBuffer* recKeyTwo);
+   
+  ULng32 loopIndex_;
+  ULng32 recNum_;
+  ULng32 allocRunSize_;
+  NABoolean isHeapified_;
+  RecKeyBuffer insertRecKey_;
+  RecKeyBuffer* topNKeys_;
+  SortError* sortError_;
+  CollHeap* heap_;
+  SortUtil* sortUtil_;
+  ExBMOStats *bmoStats_;
+};
+
+#endif
+
+

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/sqlcomp/DefaultConstants.h
----------------------------------------------------------------------
diff --git a/core/sql/sqlcomp/DefaultConstants.h b/core/sql/sqlcomp/DefaultConstants.h
index a6270c9..69078f9 100644
--- a/core/sql/sqlcomp/DefaultConstants.h
+++ b/core/sql/sqlcomp/DefaultConstants.h
@@ -1676,6 +1676,7 @@ enum DefaultConstants
   DO_RUNTIME_SPACE_OPTIMIZATION,
 
   GEN_SORT_MAX_NUM_BUFFERS,
+  GEN_SORT_TOPN_SIZE,
 
   SORT_ALGO,            // Sort algorithm choice
   // Not used anymore. OVERRIDE_SYSKEY takes its place.

http://git-wip-us.apache.org/repos/asf/incubator-trafodion/blob/61cc7b5b/core/sql/sqlcomp/nadefaults.cpp
----------------------------------------------------------------------
diff --git a/core/sql/sqlcomp/nadefaults.cpp b/core/sql/sqlcomp/nadefaults.cpp
index d001ce6..149cca2 100644
--- a/core/sql/sqlcomp/nadefaults.cpp
+++ b/core/sql/sqlcomp/nadefaults.cpp
@@ -1629,6 +1629,7 @@ SDDkwd__(EXE_DIAGNOSTIC_EVENTS,		"OFF"),
   DDui1__(GEN_SORT_NUM_BUFFERS,			"4"),
   DDui1__(GEN_SORT_SIZE_DOWN,			"2"),
   DDui1__(GEN_SORT_SIZE_UP,			"1024"),
+  DDui___(GEN_SORT_TOPN_SIZE,		"0"),
   DDui1__(GEN_SPLB_BUFFER_SIZE,			"2"),
   DDui1__(GEN_SPLB_NUM_BUFFERS,			"1"),
   DDui1__(GEN_SPLB_SIZE_DOWN,			"2"),


Mime
View raw message