/ Check-in [ebf819aa]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Use OP_SorterOpen instead of OP_OpenEphemeral to implement GROUP BY.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | merge-sort
Files: files | file ages | folders
SHA1: ebf819aaa555bd79fddfc0a6f9827a2539095d6c
User & Date: drh 2011-09-01 16:01:27
Context
2011-09-02
10:31
Instead of a temporary b-tree, use a linked-list and merge-sort to sort records in main memory in vdbesort.c. check-in: 7769fb98 user: dan tags: merge-sort
2011-09-01
16:01
Use OP_SorterOpen instead of OP_OpenEphemeral to implement GROUP BY. check-in: ebf819aa user: drh tags: merge-sort
15:32
Experimental code-generator changes to utilize new opcodes for sorting. check-in: bab2e560 user: drh tags: merge-sort
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

  4029   4029       int iBMem;          /* First Mem address for previous GROUP BY */
  4030   4030       int iUseFlag;       /* Mem address holding flag indicating that at least
  4031   4031                           ** one row of the input to the aggregator has been
  4032   4032                           ** processed */
  4033   4033       int iAbortFlag;     /* Mem address which causes query abort if positive */
  4034   4034       int groupBySort;    /* Rows come from source in GROUP BY order */
  4035   4035       int addrEnd;        /* End of processing for this SELECT */
         4036  +    int sortPTab = 0;   /* Pseudotable used to decode sorting results */
         4037  +    int sortOut = 0;    /* Output register from the sorter */
  4036   4038   
  4037   4039       /* Remove any and all aliases between the result set and the
  4038   4040       ** GROUP BY clause.
  4039   4041       */
  4040   4042       if( pGroupBy ){
  4041   4043         int k;                        /* Loop counter */
  4042   4044         struct ExprList_item *pItem;  /* For looping over expression in a list */
................................................................................
  4090   4092         int addrTopOfLoop;  /* Top of the input loop */
  4091   4093         int addrSortingIdx; /* The OP_OpenEphemeral for the sorting index */
  4092   4094         int addrReset;      /* Subroutine for resetting the accumulator */
  4093   4095         int regReset;       /* Return address register for reset subroutine */
  4094   4096   
  4095   4097         /* If there is a GROUP BY clause we might need a sorting index to
  4096   4098         ** implement it.  Allocate that sorting index now.  If it turns out
  4097         -      ** that we do not need it after all, the OpenEphemeral instruction
         4099  +      ** that we do not need it after all, the OP_SorterOpen instruction
  4098   4100         ** will be converted into a Noop.  
  4099   4101         */
  4100   4102         sAggInfo.sortingIdx = pParse->nTab++;
  4101   4103         pKeyInfo = keyInfoFromExprList(pParse, pGroupBy);
  4102         -      addrSortingIdx = sqlite3VdbeAddOp4(v, OP_OpenEphemeral, 
         4104  +      addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen, 
  4103   4105             sAggInfo.sortingIdx, sAggInfo.nSortingColumn, 
  4104   4106             0, (char*)pKeyInfo, P4_KEYINFO_HANDOFF);
  4105   4107   
  4106   4108         /* Initialize memory locations used by GROUP BY aggregate processing
  4107   4109         */
  4108   4110         iUseFlag = ++pParse->nMem;
  4109   4111         iAbortFlag = ++pParse->nMem;
................................................................................
  4176   4178                 sqlite3VdbeAddOp2(v, OP_SCopy, r2, r1);
  4177   4179               }
  4178   4180               j++;
  4179   4181             }
  4180   4182           }
  4181   4183           regRecord = sqlite3GetTempReg(pParse);
  4182   4184           sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nCol, regRecord);
  4183         -        sqlite3VdbeAddOp2(v, OP_IdxInsert, sAggInfo.sortingIdx, regRecord);
         4185  +        sqlite3VdbeAddOp2(v, OP_SorterInsert, sAggInfo.sortingIdx, regRecord);
  4184   4186           sqlite3ReleaseTempReg(pParse, regRecord);
  4185   4187           sqlite3ReleaseTempRange(pParse, regBase, nCol);
  4186   4188           sqlite3WhereEnd(pWInfo);
  4187         -        sqlite3VdbeAddOp2(v, OP_Sort, sAggInfo.sortingIdx, addrEnd);
         4189  +        sortPTab = pParse->nTab++;
         4190  +        sortOut = sqlite3GetTempReg(pParse);
         4191  +        sqlite3VdbeAddOp3(v, OP_OpenPseudo, sortPTab, sortOut, nCol);
         4192  +        sqlite3VdbeAddOp2(v, OP_SorterSort, sAggInfo.sortingIdx, addrEnd);
  4188   4193           VdbeComment((v, "GROUP BY sort"));
  4189   4194           sAggInfo.useSortingIdx = 1;
  4190   4195           sqlite3ExprCacheClear(pParse);
  4191   4196         }
  4192   4197   
  4193   4198         /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
  4194   4199         ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
  4195   4200         ** Then compare the current GROUP BY terms against the GROUP BY terms
  4196   4201         ** from the previous row currently stored in a0, a1, a2...
  4197   4202         */
  4198   4203         addrTopOfLoop = sqlite3VdbeCurrentAddr(v);
  4199   4204         sqlite3ExprCacheClear(pParse);
         4205  +      if( groupBySort ){
         4206  +        sqlite3VdbeAddOp2(v, OP_SorterData, sAggInfo.sortingIdx, sortOut);
         4207  +      }
  4200   4208         for(j=0; j<pGroupBy->nExpr; j++){
  4201   4209           if( groupBySort ){
  4202         -          sqlite3VdbeAddOp3(v, OP_Column, sAggInfo.sortingIdx, j, iBMem+j);
         4210  +          sqlite3VdbeAddOp3(v, OP_Column, sortPTab, j, iBMem+j);
         4211  +          if( j==0 ) sqlite3VdbeChangeP5(v, OPFLAG_CLEARCACHE);
  4203   4212           }else{
  4204   4213             sAggInfo.directMode = 1;
  4205   4214             sqlite3ExprCode(pParse, pGroupBy->a[j].pExpr, iBMem+j);
  4206   4215           }
  4207   4216         }
  4208   4217         sqlite3VdbeAddOp4(v, OP_Compare, iAMem, iBMem, pGroupBy->nExpr,
  4209   4218                             (char*)pKeyInfo, P4_KEYINFO);
................................................................................
  4234   4243         updateAccumulator(pParse, &sAggInfo);
  4235   4244         sqlite3VdbeAddOp2(v, OP_Integer, 1, iUseFlag);
  4236   4245         VdbeComment((v, "indicate data in accumulator"));
  4237   4246   
  4238   4247         /* End of the loop
  4239   4248         */
  4240   4249         if( groupBySort ){
  4241         -        sqlite3VdbeAddOp2(v, OP_Next, sAggInfo.sortingIdx, addrTopOfLoop);
         4250  +        sqlite3VdbeAddOp2(v, OP_SorterNext, sAggInfo.sortingIdx, addrTopOfLoop);
  4242   4251         }else{
  4243   4252           sqlite3WhereEnd(pWInfo);
  4244   4253           sqlite3VdbeChangeToNoop(v, addrSortingIdx, 1);
  4245   4254         }
  4246   4255   
  4247   4256         /* Output the final row of result
  4248   4257         */

Changes to test/distinct.test.

    41     41     uplevel [list do_test $tn [list is_distinct_noop $sql] 0]
    42     42   }
    43     43   
    44     44   proc do_temptables_test {tn sql temptables} {
    45     45     uplevel [list do_test $tn [subst -novar {
    46     46       set ret ""
    47     47       db eval "EXPLAIN [set sql]" {
    48         -      if {$opcode == "OpenEphemeral"} { 
           48  +      if {$opcode == "OpenEphemeral" || $opcode == "SorterOpen"} { 
    49     49           if {$p5 != "10" && $p5!="00"} { error "p5 = $p5" }
    50     50           if {$p5 == "10"} {
    51     51             lappend ret hash
    52     52           } else {
    53     53             lappend ret btree
    54     54           }
    55     55         }