SQLite

Check-in [336de43a47]
Login

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

Overview
Comment:Avoid redundant ORDER BY operations when rewriting SELECT statements that contain window functions.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | exp-window-functions
Files: files | file ages | folders
SHA3-256: 336de43a47e206fe7629072e5b8c80d4ede17ead8ef4dcf5d8da6833ff22d2f9
User & Date: dan 2018-06-27 19:48:50.544
Context
2018-06-27
20:24
Add missing VdbeCoverage() and VdbeCoverageNeverTaken() macros to window.c. (check-in: 4383cb68a1 user: dan tags: exp-window-functions)
19:48
Avoid redundant ORDER BY operations when rewriting SELECT statements that contain window functions. (check-in: 336de43a47 user: dan tags: exp-window-functions)
2018-06-26
20:19
Merge latest trunk changes. (check-in: d9f814b443 user: dan tags: exp-window-functions)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/select.c.
5480
5481
5482
5483
5484
5485
5486
5487
5488
5489
5490
5491
5492
5493
5494
5495
    /* If ORDER BY makes no difference in the output then neither does
    ** DISTINCT so it can be removed too. */
    sqlite3ExprListDelete(db, p->pOrderBy);
    p->pOrderBy = 0;
    p->selFlags &= ~SF_Distinct;
  }
  sqlite3SelectPrep(pParse, p, 0);
  memset(&sSort, 0, sizeof(sSort));
  sSort.pOrderBy = p->pOrderBy;
  if( pParse->nErr || db->mallocFailed ){
    goto select_end;
  }
  assert( p->pEList!=0 );
#if SELECTTRACE_ENABLED
  if( sqlite3SelectTrace & 0x104 ){
    SELECTTRACE(0x104,pParse,p, ("after name resolution:\n"));







<
<







5480
5481
5482
5483
5484
5485
5486


5487
5488
5489
5490
5491
5492
5493
    /* If ORDER BY makes no difference in the output then neither does
    ** DISTINCT so it can be removed too. */
    sqlite3ExprListDelete(db, p->pOrderBy);
    p->pOrderBy = 0;
    p->selFlags &= ~SF_Distinct;
  }
  sqlite3SelectPrep(pParse, p, 0);


  if( pParse->nErr || db->mallocFailed ){
    goto select_end;
  }
  assert( p->pEList!=0 );
#if SELECTTRACE_ENABLED
  if( sqlite3SelectTrace & 0x104 ){
    SELECTTRACE(0x104,pParse,p, ("after name resolution:\n"));
5510
5511
5512
5513
5514
5515
5516


5517
5518
5519
5520
5521
5522
5523
    SELECTTRACE(0x104,pParse,p, ("after window rewrite:\n"));
    sqlite3TreeViewSelect(0, p, 0);
  }
#endif
#endif /* SQLITE_OMIT_WINDOWFUNC */
  pTabList = p->pSrc;
  isAgg = (p->selFlags & SF_Aggregate)!=0;



  /* Try to various optimizations (flattening subqueries, and strength
  ** reduction of join operators) in the FROM clause up into the main query
  */
#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
  for(i=0; !p->pPrior && i<pTabList->nSrc; i++){
    struct SrcList_item *pItem = &pTabList->a[i];







>
>







5508
5509
5510
5511
5512
5513
5514
5515
5516
5517
5518
5519
5520
5521
5522
5523
    SELECTTRACE(0x104,pParse,p, ("after window rewrite:\n"));
    sqlite3TreeViewSelect(0, p, 0);
  }
#endif
#endif /* SQLITE_OMIT_WINDOWFUNC */
  pTabList = p->pSrc;
  isAgg = (p->selFlags & SF_Aggregate)!=0;
  memset(&sSort, 0, sizeof(sSort));
  sSort.pOrderBy = p->pOrderBy;

  /* Try to various optimizations (flattening subqueries, and strength
  ** reduction of join operators) in the FROM clause up into the main query
  */
#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
  for(i=0; !p->pPrior && i<pTabList->nSrc; i++){
    struct SrcList_item *pItem = &pTabList->a[i];
Changes to src/window.c.
716
717
718
719
720
721
722












723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
    Window *pMWin = p->pWin;      /* Master window object */
    Window *pWin;                 /* Window object iterator */

    p->pSrc = 0;
    p->pWhere = 0;
    p->pGroupBy = 0;
    p->pHaving = 0;













    /* Assign a cursor number for the ephemeral table used to buffer rows.
    ** The OpenEphemeral instruction is coded later, after it is known how
    ** many columns the table will have.  */
    pMWin->iEphCsr = pParse->nTab++;

    selectWindowRewriteEList(pParse, pMWin, p->pEList, &pSublist);
    selectWindowRewriteEList(pParse, pMWin, p->pOrderBy, &pSublist);
    pMWin->nBufferCol = (pSublist ? pSublist->nExpr : 0);

    /* Create the ORDER BY clause for the sub-select. This is the concatenation
    ** of the window PARTITION and ORDER BY clauses. Append the same 
    ** expressions to the sub-select expression list. They are required to
    ** figure out where boundaries for partitions and sets of peer rows.  */
    pSort = sqlite3ExprListDup(db, pMWin->pPartition, 0);
    if( pMWin->pOrderBy ){
      pSort = exprListAppendList(pParse, pSort, pMWin->pOrderBy);
    }
    pSublist = exprListAppendList(pParse, pSublist, pSort);

    /* Append the arguments passed to each window function to the
    ** sub-select expression list. Also allocate two registers for each
    ** window function - one for the accumulator, another for interim
    ** results.  */
    for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
      pWin->iArgCol = (pSublist ? pSublist->nExpr : 0);







>
>
>
>
>
>
>
>
>
>
>
>










<
|
|
|
<
<
|
<
|







716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744

745
746
747


748

749
750
751
752
753
754
755
756
    Window *pMWin = p->pWin;      /* Master window object */
    Window *pWin;                 /* Window object iterator */

    p->pSrc = 0;
    p->pWhere = 0;
    p->pGroupBy = 0;
    p->pHaving = 0;

    /* Create the ORDER BY clause for the sub-select. This is the concatenation
    ** of the window PARTITION and ORDER BY clauses. Then, if this makes it
    ** redundant, remove the ORDER BY from the parent SELECT.  */
    pSort = sqlite3ExprListDup(db, pMWin->pPartition, 0);
    pSort = exprListAppendList(pParse, pSort, pMWin->pOrderBy);
    if( pSort && p->pOrderBy ){
      if( sqlite3ExprListCompare(pSort, p->pOrderBy, -1)==0 ){
        sqlite3ExprListDelete(db, p->pOrderBy);
        p->pOrderBy = 0;
      }
    }

    /* Assign a cursor number for the ephemeral table used to buffer rows.
    ** The OpenEphemeral instruction is coded later, after it is known how
    ** many columns the table will have.  */
    pMWin->iEphCsr = pParse->nTab++;

    selectWindowRewriteEList(pParse, pMWin, p->pEList, &pSublist);
    selectWindowRewriteEList(pParse, pMWin, p->pOrderBy, &pSublist);
    pMWin->nBufferCol = (pSublist ? pSublist->nExpr : 0);


    /* Append the PARTITION BY and ORDER BY expressions to the to the 
    ** sub-select expression list. They are required to figure out where 
    ** boundaries for partitions and sets of peer rows lie.  */


    pSublist = exprListAppendList(pParse, pSublist, pMWin->pPartition);

    pSublist = exprListAppendList(pParse, pSublist, pMWin->pOrderBy);

    /* Append the arguments passed to each window function to the
    ** sub-select expression list. Also allocate two registers for each
    ** window function - one for the accumulator, another for interim
    ** results.  */
    for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
      pWin->iArgCol = (pSublist ? pSublist->nExpr : 0);