Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb0ccd78

Browse files
committed
Don't limit number of tuples in leftist trees!
Use qsort to sort array of tuples for nextrun when currentrun is done and put into leftist tree from sorted array!It's much faster and creates non-bushy tree - this is ve-e-ery goodfor perfomance!
1 parent8f1e1b4 commitb0ccd78

File tree

1 file changed

+54
-81
lines changed

1 file changed

+54
-81
lines changed

‎src/backend/utils/sort/psort.c

Lines changed: 54 additions & 81 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
*
88
*
99
* IDENTIFICATION
10-
* $Header: /cvsroot/pgsql/src/backend/utils/sort/Attic/psort.c,v 1.23 1997/09/1805:37:31 vadim Exp $
10+
* $Header: /cvsroot/pgsql/src/backend/utils/sort/Attic/psort.c,v 1.24 1997/09/1814:41:56 vadim Exp $
1111
*
1212
* NOTES
1313
*Sorts the first relation into the second relation.
@@ -147,8 +147,6 @@ psort_begin(Sort * node, int nkeys, ScanKey key)
147147
PS(node)->treeContext.sortMem=SortMem*1024;
148148

149149
PS(node)->Tuples=NULL;
150-
PS(node)->lasttuple=NULL;
151-
PS(node)->lt_tupcount=0;
152150
PS(node)->tupcount=0;
153151

154152
PS(node)->using_tape_files= false;
@@ -434,45 +432,14 @@ createfirstrun(Sort *node)
434432
if (LACKMEM (node) )/* in-memory sort is impossible */
435433
{
436434
registerintt;
437-
registerintf;
438-
FILE*file;
439435

440436
Assert (!foundeor);
441437
inittapes(node);
442-
file=PS(node)->Tape->tp_file;
443-
444-
/* put extra tuples into tape file */
445-
if (t_last>SortTuplesInTree )
446-
{
447-
registerHeapTuplelasttuple;
448-
449-
t=t_last-SortTuplesInTree;
450-
for (f=0,lasttuple=NULL;f<t;f++)
451-
{
452-
if (lasttuple )
453-
{
454-
FREEMEM(node,lasttuple->t_len);
455-
FREE(lasttuple);
456-
TRACEMEM(createfirstrun);
457-
}
458-
lasttuple=memtuples[f];
459-
PUTTUP(node,lasttuple,file);
460-
TRACEOUT(createfirstrun,lasttuple);
461-
}
462-
PS(node)->lasttuple=lasttuple;
463-
}
464-
else
465-
{
466-
PS(node)->lasttuple=NULL;
467-
f=0;
468-
}
469-
470-
/* put rest of tuples into leftist tree for createrun */
471-
for (t=t_last-1 ;t >=f;t--)
438+
/* put tuples into leftist tree for createrun */
439+
for (t=t_last-1 ;t >=0;t--)
472440
puttuple(&PS(node)->Tuples,memtuples[t],0,&PS(node)->treeContext);
473-
PS(node)->lt_tupcount=t_last-f;
474441
pfree (memtuples);
475-
foundeor= !createrun (node,file);
442+
foundeor= !createrun (node,PS(node)->Tape->tp_file);
476443
}
477444
else
478445
{
@@ -497,50 +464,41 @@ createfirstrun(Sort *node)
497464
staticbool
498465
createrun(Sort*node,FILE*file)
499466
{
500-
registerHeapTuplelasttuple;
501-
registerHeapTupletup;
502-
structleftist*nextrun;
503-
boolfoundeor;
504-
shortjunk;
505-
intcurr_tupcount= (PS(node)->Tuples!=NULL) ?PS(node)->lt_tupcount :0;
506-
intnext_tupcount=0;
507-
508-
intcr_tuples=0;/* Count tuples grabbed from plannode */
509-
TupleTableSlot*cr_slot;
467+
registerHeapTuplelasttuple;
468+
registerHeapTupletup;
469+
TupleTableSlot*cr_slot;
470+
HeapTuple*memtuples;
471+
intt_last=-1;
472+
intt_free=1000;
473+
boolfoundeor= false;
474+
shortjunk;
510475

511476
Assert(node!= (Sort*)NULL);
512477
Assert(PS(node)!= (Psortstate*)NULL);
478+
Assert (PS(node)->using_tape_files);
513479

514-
lasttuple=PS(node)->lasttuple;/* !NULL if called from createfirstrun */
515-
nextrun=NULL;
516-
foundeor= false;
480+
lasttuple=NULL;
481+
memtuples=palloc(t_free*sizeof(HeapTuple));
482+
517483
for (;;)
518484
{
519-
if ((LACKMEM(node)&&PS(node)->Tuples!=NULL)||curr_tupcount>SortTuplesInTree)
485+
while (LACKMEM(node)&&PS(node)->Tuples!=NULL)
520486
{
521-
do
487+
if (lasttuple!=NULL)
522488
{
523-
if (lasttuple!=NULL)
524-
{
525-
FREEMEM(node,lasttuple->t_len);
526-
FREE(lasttuple);
527-
TRACEMEM(createrun);
528-
}
529-
lasttuple=tup=gettuple(&PS(node)->Tuples,&junk,
489+
FREEMEM(node,lasttuple->t_len);
490+
FREE(lasttuple);
491+
TRACEMEM(createrun);
492+
}
493+
lasttuple=gettuple(&PS(node)->Tuples,&junk,
530494
&PS(node)->treeContext);
531-
Assert (PS(node)->using_tape_files);
532-
PUTTUP(node,tup,file);
533-
TRACEOUT(createrun,tup);
534-
curr_tupcount--;
535-
}while (LACKMEM(node)&&PS(node)->Tuples!=NULL);
495+
PUTTUP(node,lasttuple,file);
496+
TRACEOUT(createrun,lasttuple);
536497
}
537498

538499
if (LACKMEM(node))
539500
break;
540501

541-
if (next_tupcount >=SortTuplesInTree )
542-
break;
543-
544502
/*
545503
* About to call ExecProcNode, it can mess up the state if it
546504
* eventually calls another Sort node. So must stow it away here
@@ -560,7 +518,6 @@ createrun(Sort * node, FILE * file)
560518
tup=tuplecopy(cr_slot->val);
561519
ExecClearTuple(cr_slot);
562520
PS(node)->tupcount++;
563-
cr_tuples++;
564521
}
565522

566523
IncrProcessed();
@@ -569,14 +526,18 @@ createrun(Sort * node, FILE * file)
569526
if (lasttuple!=NULL&&tuplecmp(tup,lasttuple,
570527
&PS(node)->treeContext))
571528
{
572-
puttuple(&nextrun,tup,0,&PS(node)->treeContext);
573-
next_tupcount++;
529+
if (t_free <=0 )
530+
{
531+
t_free=1000;
532+
memtuples=repalloc (memtuples,
533+
(t_last+t_free+1)*sizeof (HeapTuple));
534+
}
535+
t_last++;
536+
t_free--;
537+
memtuples[t_last]=tup;
574538
}
575539
else
576-
{
577540
puttuple(&PS(node)->Tuples,tup,0,&PS(node)->treeContext);
578-
curr_tupcount++;
579-
}
580541
}
581542
if (lasttuple!=NULL)
582543
{
@@ -585,13 +546,26 @@ createrun(Sort * node, FILE * file)
585546
TRACEMEM(createrun);
586547
}
587548
dumptuples(file,node);
588-
ENDRUN(file);
589-
/* delimit the end of the run */
590-
PS(node)->Tuples=nextrun;
591-
PS(node)->lt_tupcount=next_tupcount;
592-
PS(node)->lasttuple=NULL;
549+
ENDRUN(file);/* delimit the end of the run */
550+
551+
t_last++;
552+
/* put tuples for the next run into leftist tree */
553+
if (t_last >=1 )
554+
{
555+
registerintt;
556+
557+
PsortTupDesc=PS(node)->treeContext.tupDesc;
558+
PsortKeys=PS(node)->treeContext.scanKeys;
559+
PsortNkeys=PS(node)->treeContext.nKeys;
560+
qsort (memtuples,t_last,sizeof (HeapTuple),
561+
(int (*)(constvoid*,constvoid*))_psort_cmp);
562+
for (t=t_last-1 ;t >=0;t--)
563+
puttuple(&PS(node)->Tuples,memtuples[t],0,&PS(node)->treeContext);
564+
}
565+
566+
pfree (memtuples);
593567

594-
return ((bool) !foundeor);/* XXX - works iff bool is {0,1} */
568+
return (!foundeor);
595569
}
596570

597571
/*
@@ -774,8 +748,7 @@ dumptuples(FILE * file, Sort * node)
774748
newp=tp->lt_left;
775749
else
776750
newp=lmerge(tp->lt_left,tp->lt_right,context);
777-
FREEMEM(node,sizeof(structleftist));
778-
FREE(tp);
751+
pfree(tp);
779752
PUTTUP(node,tup,file);
780753
FREEMEM(node,tup->t_len);
781754
FREE(tup);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp