You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafodion.apache.org by sa...@apache.org on 2016/10/11 21:03:00 UTC
[3/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
[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/3cd201a6
Tree: http://git-wip-us.apache.org/repos/asf/incubator-trafodion/tree/3cd201a6
Diff: http://git-wip-us.apache.org/repos/asf/incubator-trafodion/diff/3cd201a6
Branch: refs/heads/master
Commit: 3cd201a6eb98ec412e33af44f106b69b215e2dcf
Parents: 12f602c
Author: Prashant Vasudev <pr...@esgyn.com>
Authored: Tue Oct 4 05:45:43 2016 +0000
Committer: Prashant Vasudev <pr...@esgyn.com>
Committed: Mon Oct 10 17:49:34 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/3cd201a6/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/3cd201a6/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/3cd201a6/core/sql/generator/GenRelMisc.cpp
----------------------------------------------------------------------
diff --git a/core/sql/generator/GenRelMisc.cpp b/core/sql/generator/GenRelMisc.cpp
index 6b4b074..4db4711 100644
--- a/core/sql/generator/GenRelMisc.cpp
+++ b/core/sql/generator/GenRelMisc.cpp
@@ -3184,6 +3184,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/3cd201a6/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/3cd201a6/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/3cd201a6/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/3cd201a6/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/3cd201a6/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/3cd201a6/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/3cd201a6/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/3cd201a6/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/3cd201a6/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/3cd201a6/core/sql/sqlcomp/DefaultConstants.h
----------------------------------------------------------------------
diff --git a/core/sql/sqlcomp/DefaultConstants.h b/core/sql/sqlcomp/DefaultConstants.h
index be53281..df0b27c 100644
--- a/core/sql/sqlcomp/DefaultConstants.h
+++ b/core/sql/sqlcomp/DefaultConstants.h
@@ -1675,6 +1675,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/3cd201a6/core/sql/sqlcomp/nadefaults.cpp
----------------------------------------------------------------------
diff --git a/core/sql/sqlcomp/nadefaults.cpp b/core/sql/sqlcomp/nadefaults.cpp
index 7b65e0d..c03d05f 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"),