package Ġorg . vit riv r . cott ont ail . database . queries . planning . nodes . physical . sort Ċ Ċ import Ġorg . vit riv r . cott ont ail . database . column . Column Def Ċ import Ġorg . vit riv r . cott ont ail . database . queries . Operator Node Ċ import Ġorg . vit riv r . cott ont ail . database . queries . Query Context Ċ import Ġorg . vit riv r . cott ont ail . database . queries . planning . cost . Cost Ċ import Ġorg . vit riv r . cott ont ail . database . queries . planning . nodes . physical . Unary Physical Operator Node Ċ import Ġorg . vit riv r . cott ont ail . database . queries . sort . SortOrder Ċ import Ġorg . vit riv r . cott ont ail . execution . Transaction Context Ċ import Ġorg . vit riv r . cott ont ail . execution . operators . basics . Operator Ċ import Ġorg . vit riv r . cott ont ail . execution . operators . sort . Limit ing Heap Sort Operator Ċ import Ġorg . vit riv r . cott ont ail . execution . operators . sort . Merge Limit ing Heap Sort Operator Ċ import Ġorg . vit riv r . cott ont ail . model . exceptions . Query Exception Ċ import Ġkotlin . math . min Ċ Ċ /** Ċ Ġ* ĠA Ġ[ Unary Physical Operator Node ] Ġthat Ġrepresents Ġsorting Ġthe Ġinput Ġby Ġa Ġset Ġof Ġspecified Ġ[ Column Def ] s Ġbut Ġlimiting Ġthe Ġoutput Ġto Ġthe Ċ Ġ* Ġtop ĠK Ġentries . ĠThis Ġis Ġsemantic ally Ġequivalent Ġto Ġa ĠORDER ĠBY ĠXY ĠLIMIT ĠZ . ĠIntern ally , Ġa Ġheap Ġsort Ġalgorithm Ġis Ġemploy ed Ġfor Ġsorting . Ċ Ġ* Ċ Ġ* Ġ@ author ĠR alph ĠG asser Ċ Ġ* Ġ@ version Ġ 2 . 1 . 0 Ċ Ġ*/ Ċ class ĠLimit ing Sort Physical Operator Node ( input : ĠPhysical ? Ġ= Ġnull , Ġsort On : ĠArray < Pair < Column Def <* >, ĠSort Order >>, Ġval Ġlimit : ĠLong , Ġval Ġskip : ĠLong ) Ġ: ĠUnary Physical Operator Node ( input ) Ġ{ ĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠNODE _ NAME Ġ= Ġ" Order And Limit " ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĠThe Ġname Ġof Ġthis Ġ[ Sort Physical Operator Node ]. Ġ*/ ĊĠĠĠ Ġoverride Ġval Ġname : ĠString ĊĠĠĠĠĠĠĠ Ġget () Ġ= ĠNODE _ NAME ĊĊĠĠĠ Ġ/** ĠThe Ġ[ Limit ing Sort Physical Operator Node ] Ġrequires Ġall Ġ[ Column Def ] s Ġused Ġon Ġthe ĠORDER ĠBY Ġclause . Ġ*/ ĊĠĠĠ Ġoverride Ġval Ġrequires : ĠArray < Column Def <* >> Ġ= Ġsort On . map Ġ{ Ġit . first Ġ}. to Typed Array () ĊĊĠĠĠ Ġ/** ĠThe Ġsize Ġof Ġthe Ġoutput Ġproduced Ġby Ġthis Ġ[ Sort Physical Operator Node ]. Ġ*/ ĊĠĠĠ Ġoverride Ġval Ġoutput Size : ĠLong Ġ= Ġmin (( super . output Size Ġ- Ġthis . skip ), Ġthis . limit ) ĊĊĠĠĠ Ġ/** ĠThe Ġ[ Cost ] Ġinc urred Ġby Ġthis Ġ[ Sort Physical Operator Node ]. Ġ*/ ĊĠĠĠ Ġoverride Ġval Ġcost : ĠCost ĊĠĠĠĠĠĠĠ Ġget () Ġ= ĠCost ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcpu Ġ= Ġ 2 Ġ* Ġ( this . input ?. output Size Ġ?: Ġ 0 ) Ġ* Ġthis . order . size Ġ* ĠCost . CO ST _ MEMORY _ ACCESS , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmemory Ġ= Ġ( this . columns . sum Of Ġ{ Ġthis . statistics [ it ]. avg Width Ġ} Ġ* Ġthis . output Size ). toFloat () ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠ Ġ/** ĠA Ġ[ Sort Physical Operator Node ] Ġorders Ġthe Ġinput Ġin Ġby Ġthe Ġspecified Ġ[ Column Def ] s . Ġ*/ ĊĠĠĠ Ġoverride Ġval Ġorder Ġ= Ġsort On ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( this . order . isEmpty ()) Ġthrow ĠQuery Exception . Query Syntax Exception (" At Ġleast Ġone Ġcolumn Ġmust Ġbe Ġspecified Ġfor Ġsorting .") ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCreates Ġand Ġreturns Ġa Ġcopy Ġof Ġthis Ġ[ Limit ing Sort Physical Operator Node ] Ġwithout Ġany Ġchildren Ġor Ġparents . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ return ĠCopy Ġof Ġthis Ġ[ Limit ing Sort Physical Operator Node ]. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġfun Ġcopy () Ġ= ĠLimit ing Sort Physical Operator Node ( sort On Ġ= Ġthis . order , Ġlimit Ġ= Ġthis . limit , Ġskip Ġ= Ġthis . skip ) ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠPart itions Ġthis Ġ[ Limit ing Sort Physical Operator Node ]. ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġp ĠThe Ġnumber Ġof Ġpartitions Ġto Ġcreate . ĊĠĠĠĠ Ġ* Ġ@ return ĠList Ġof Ġ[ Operator Node . Physical ], Ġeach Ġrepresenting Ġa Ġpartition Ġof Ġthe Ġoriginal Ġtree . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġfun Ġpartition ( p : ĠInt ): ĠList < Physical > Ġ= ĊĠĠĠĠĠĠĠ Ġthis . input ?. partition ( p )?. map Ġ{ ĠLimit ing Sort Physical Operator Node ( it , Ġthis . order , Ġthis . limit , Ġthis . skip ) Ġ} Ġ?: Ġthrow ĠIllegalStateException (" Cannot Ġpartition Ġdisconnected ĠOperator Node Ġ( node Ġ= Ġ$ this )") ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConverts Ġthis Ġ[ Limit ing Sort Physical Operator Node ] Ġto Ġa Ġ[ Limit ing Heap Sort Operator ]. ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġtx ĠThe Ġ[ Transaction Context ] Ġused Ġfor Ġexecution . ĊĠĠĠĠ Ġ* Ġ@ param Ġctx ĠThe Ġ[ Query Context ] Ġused Ġfor Ġthe Ġconversion Ġ( e . g . Ġlate Ġbinding ). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġfun Ġto Operator ( tx : ĠTransaction Context , Ġctx : ĠQuery Context ): ĠOperator Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġp Ġ= Ġthis . total Cost . parallel isation () ĊĠĠĠĠĠĠĠ Ġval Ġinput Ġ= Ġthis . input Ġ?: Ġthrow ĠIllegalStateException (" Cannot Ġconvert Ġdisconnected ĠOperator Node Ġto ĠOperator Ġ( node Ġ= Ġ$ this )") ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( p Ġ> Ġ 1 Ġ&& Ġthis . input ?. can Be Partition ed Ġ== Ġtrue ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpartitions Ġ= Ġinput . partition ( p ). map Ġ{ Ġit . to Operator ( tx , Ġctx ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠMerge Limit ing Heap Sort Operator ( partitions , Ġthis . order , Ġthis . limit ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠLimit ing Heap Sort Operator ( input . to Operator ( tx , Ġctx ), Ġthis . order , Ġthis . limit , Ġthis . skip ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĠGenerates Ġand Ġreturns Ġa Ġ[ String ] Ġrepresentation Ġof Ġthis Ġ[ Sort Physical Operator Node ]. Ġ*/ ĊĠĠĠ Ġoverride Ġfun ĠtoString () Ġ= Ġ"${ super . toString ()} [ ${ this . order . join ToString (",") Ġ{ Ġ"${ it . first . name } Ġ${ it . second }" Ġ}}, ${ this . skip }, ${ this . limit }] " ĊĊĠĠĠ Ġoverride Ġfun Ġequals ( other : ĠAny ?): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( this Ġ=== Ġother ) Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġif Ġ( other Ġ! is ĠLimit ing Sort Physical Operator Node ) Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġif Ġ( skip Ġ!= Ġother . skip ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġif Ġ( limit Ġ!= Ġother . limit ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġif Ġ(! order . content Equals ( other . order )) Ġreturn Ġfalse ĊĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠhashCode (): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġresult Ġ= Ġskip . hashCode () ĊĠĠĠĠĠĠĠ Ġresult Ġ= Ġ 3 1 Ġ* Ġresult Ġ+ Ġlimit . hashCode () ĊĠĠĠĠĠĠĠ Ġresult Ġ= Ġ 3 1 Ġ* Ġresult Ġ+ Ġorder . content HashCode () ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} Ċ }