SQLite

Check-in [6413e38a17]
Login

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

Overview
Comment:Fix another issue to do with window-functions in aggregate queries.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | exp-window-functions
Files: files | file ages | folders
SHA3-256: 6413e38a174044c28fa9b8b937e6c972d144547a246e6f2882e782538300d042
User & Date: dan 2018-06-12 20:53:38.832
Context
2018-06-13
20:29
Fix problems with "RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING" window frames. (check-in: c34f31dbd7 user: dan tags: exp-window-functions)
2018-06-12
20:53
Fix another issue to do with window-functions in aggregate queries. (check-in: 6413e38a17 user: dan tags: exp-window-functions)
18:40
Fix some problems with using window-functions in aggregate queries. (check-in: fe7081e095 user: dan tags: exp-window-functions)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/btree.c.
5181
5182
5183
5184
5185
5186
5187





5188
5189
5190
5191
5192
5193
5194
    assert( pCur->pgnoRoot==0 || pCur->pPage->nCell==0 );
    *pRes = 1;
    rc = SQLITE_OK;
  }
  return rc;
}






void sqlite3BtreeSkipNext(BtCursor *pCur){
  if( pCur->eState==CURSOR_VALID ){
    pCur->eState = CURSOR_SKIPNEXT;
    pCur->skipNext = 1;
  }
}








>
>
>
>
>







5181
5182
5183
5184
5185
5186
5187
5188
5189
5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
    assert( pCur->pgnoRoot==0 || pCur->pPage->nCell==0 );
    *pRes = 1;
    rc = SQLITE_OK;
  }
  return rc;
}

/*
** This function is a no-op if cursor pCur does not point to a valid row.
** Otherwise, if pCur is valid, configure it so that the next call to
** sqlite3BtreeNext() is a no-op.
*/
void sqlite3BtreeSkipNext(BtCursor *pCur){
  if( pCur->eState==CURSOR_VALID ){
    pCur->eState = CURSOR_SKIPNEXT;
    pCur->skipNext = 1;
  }
}

Changes to src/window.c.
125
126
127
128
129
130
131





132
133
134
135
136
137
138
**   window frame is sometimes modified before the SELECT statement is
**   rewritten. For example, regardless of the specified window frame, the
**   row_number() function always uses:
**
**     ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
**
**   See sqlite3WindowUpdate() for details.





*/

/*
** Implementation of built-in window function row_number(). Assumes that the
** window frame has been coerced to:
**
**   ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW







>
>
>
>
>







125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
**   window frame is sometimes modified before the SELECT statement is
**   rewritten. For example, regardless of the specified window frame, the
**   row_number() function always uses:
**
**     ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
**
**   See sqlite3WindowUpdate() for details.
**
**   As well as some of the built-in window functions, aggregate window
**   functions min() and max() are implemented using VDBE instructions if
**   the start of the window frame is declared as anything other than 
**   UNBOUNDED PRECEDING.
*/

/*
** Implementation of built-in window function row_number(). Assumes that the
** window frame has been coerced to:
**
**   ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
467
468
469
470
471
472
473

















474
475
476
477
478
479
480
481
482
483
484
485
    WINDOWFUNC(first_value, 1, 0),
    WINDOWFUNC(lead, 1, 0), WINDOWFUNC(lead, 2, 0), WINDOWFUNC(lead, 3, 0),
    WINDOWFUNC(lag, 1, 0),  WINDOWFUNC(lag, 2, 0),  WINDOWFUNC(lag, 3, 0),
  };
  sqlite3InsertBuiltinFuncs(aWindowFuncs, ArraySize(aWindowFuncs));
}


















void sqlite3WindowUpdate(
  Parse *pParse, 
  Window *pList, 
  Window *pWin, 
  FuncDef *pFunc
){
  if( pWin->zName ){
    Window *p;
    for(p=pList; p; p=p->pNextWin){
      if( sqlite3StrICmp(p->zName, pWin->zName)==0 ) break;
    }
    if( p==0 ){







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


|
|
|







472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
    WINDOWFUNC(first_value, 1, 0),
    WINDOWFUNC(lead, 1, 0), WINDOWFUNC(lead, 2, 0), WINDOWFUNC(lead, 3, 0),
    WINDOWFUNC(lag, 1, 0),  WINDOWFUNC(lag, 2, 0),  WINDOWFUNC(lag, 3, 0),
  };
  sqlite3InsertBuiltinFuncs(aWindowFuncs, ArraySize(aWindowFuncs));
}

/*
** This function is called immediately after resolving the function name
** for a window function within a SELECT statement. Argument pList is a
** linked list of WINDOW definitions for the current SELECT statement.
** Argument pFunc is the function definition just resolved and pWin
** is the Window object representing the associated OVER clause. This
** function updates the contents of pWin as follows:
**
**   * If the OVER clause refered to a named window (as in "max(x) OVER win"),
**     search list pList for a matching WINDOW definition, and update pWin
**     accordingly. If no such WINDOW clause can be found, leave an error
**     in pParse.
**
**   * If the function is a built-in window function that requires the
**     window to be coerced (see "BUILT-IN WINDOW FUNCTIONS" at the top
**     of this file), pWin is updated here.
*/
void sqlite3WindowUpdate(
  Parse *pParse, 
  Window *pList,                  /* List of named windows for this SELECT */
  Window *pWin,                   /* Window frame to update */
  FuncDef *pFunc                  /* Window function definition */
){
  if( pWin->zName ){
    Window *p;
    for(p=pList; p; p=p->pNextWin){
      if( sqlite3StrICmp(p->zName, pWin->zName)==0 ) break;
    }
    if( p==0 ){
519
520
521
522
523
524
525




526
527
528
529
530
531

532
533
534
535


536
537
538
539
540
541
542
      pWin->eStart = TK_UNBOUNDED;
      pWin->eEnd = TK_CURRENT;
    }
  }
  pWin->pFunc = pFunc;
}





typedef struct WindowRewrite WindowRewrite;
struct WindowRewrite {
  Window *pWin;
  ExprList *pSub;
};


static int selectWindowRewriteSelectCb(Walker *pWalker, Select *pSelect){
  return WRC_Prune;
}



static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){
  struct WindowRewrite *p = pWalker->u.pRewrite;
  Parse *pParse = pWalker->pParse;

  switch( pExpr->op ){

    case TK_FUNCTION:







>
>
>
>






>
|
<
<
|
>
>







541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559


560
561
562
563
564
565
566
567
568
569
      pWin->eStart = TK_UNBOUNDED;
      pWin->eEnd = TK_CURRENT;
    }
  }
  pWin->pFunc = pFunc;
}

/*
** Context object passed through sqlite3WalkExprList() to
** selectWindowRewriteExprCb() by selectWindowRewriteEList().
*/
typedef struct WindowRewrite WindowRewrite;
struct WindowRewrite {
  Window *pWin;
  ExprList *pSub;
};

/*
** Callback function used by selectWindowRewriteEList(). If necessary,


** this function appends to the output expression-list and updates 
** expression (*ppExpr) in place.
*/
static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){
  struct WindowRewrite *p = pWalker->u.pRewrite;
  Parse *pParse = pWalker->pParse;

  switch( pExpr->op ){

    case TK_FUNCTION:
574
575
576
577
578
579
580


581















582
583
584
585
586
587
588

    default: /* no-op */
      break;
  }

  return WRC_Continue;
}


















static int selectWindowRewriteEList(
  Parse *pParse, 
  Window *pWin,
  ExprList *pEList,               /* Rewrite expressions in this list */
  ExprList **ppSub                /* IN/OUT: Sub-select expression-list */
){
  Walker sWalker;







>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632

    default: /* no-op */
      break;
  }

  return WRC_Continue;
}
static int selectWindowRewriteSelectCb(Walker *pWalker, Select *pSelect){
  return WRC_Prune;
}


/*
** Iterate through each expression in expression-list pEList. For each:
**
**   * TK_COLUMN,
**   * aggregate function, or
**   * window function with a Window object that is not a member of the 
**     linked list passed as the second argument (pWin)
**
** Append the node to output expression-list (*ppSub). And replace it
** with a TK_COLUMN that reads the (N-1)th element of table 
** pWin->iEphCsr, where N is the number of elements in (*ppSub) after
** appending the new one.
*/
static int selectWindowRewriteEList(
  Parse *pParse, 
  Window *pWin,
  ExprList *pEList,               /* Rewrite expressions in this list */
  ExprList **ppSub                /* IN/OUT: Sub-select expression-list */
){
  Walker sWalker;
602
603
604
605
606
607
608




609
610
611
612
613
614
615

  rc = sqlite3WalkExprList(&sWalker, pEList);

  *ppSub = sRewrite.pSub;
  return rc;
}





static ExprList *exprListAppendList(
  Parse *pParse,          /* Parsing context */
  ExprList *pList,        /* List to which to append. Might be NULL */
  ExprList *pAppend       /* List of values to append. Might be NULL */
){
  if( pAppend ){
    int i;







>
>
>
>







646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663

  rc = sqlite3WalkExprList(&sWalker, pEList);

  *ppSub = sRewrite.pSub;
  return rc;
}

/*
** Append a copy of each expression in expression-list pAppend to
** expression list pList. Return a pointer to the result list.
*/
static ExprList *exprListAppendList(
  Parse *pParse,          /* Parsing context */
  ExprList *pList,        /* List to which to append. Might be NULL */
  ExprList *pAppend       /* List of values to append. Might be NULL */
){
  if( pAppend ){
    int i;
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
  return pList;
}

/*
** If the SELECT statement passed as the second argument does not invoke
** any SQL window functions, this function is a no-op. Otherwise, it 
** rewrites the SELECT statement so that window function xStep functions
** are invoked in the correct order. The simplest version of the 
** transformation is:
**
**   SELECT win(args...) OVER (<list1>) FROM <src> ORDER BY <list2>
**
** to
**
**   SELECT win(args...) FROM (
**     SELECT args... FROM <src> ORDER BY <list1>
**   ) ORDER BY <list2>
**
** where <src> may contain WHERE, GROUP BY and HAVING clauses, and <list1>
** is the concatenation of the PARTITION BY and ORDER BY clauses in the
** OVER clause.
**
*/
int sqlite3WindowRewrite(Parse *pParse, Select *p){
  int rc = SQLITE_OK;
  if( p->pWin ){
    Vdbe *v = sqlite3GetVdbe(pParse);
    int i;
    sqlite3 *db = pParse->db;







|
<
<
<
<
|
<
<
<
<
<
<
<
<
<







671
672
673
674
675
676
677
678




679









680
681
682
683
684
685
686
  return pList;
}

/*
** If the SELECT statement passed as the second argument does not invoke
** any SQL window functions, this function is a no-op. Otherwise, it 
** rewrites the SELECT statement so that window function xStep functions
** are invoked in the correct order as described under "SELECT REWRITING"




** at the top of this file.









*/
int sqlite3WindowRewrite(Parse *pParse, Select *p){
  int rc = SQLITE_OK;
  if( p->pWin ){
    Vdbe *v = sqlite3GetVdbe(pParse);
    int i;
    sqlite3 *db = pParse->db;
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

    sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pMWin->iEphCsr, pSublist->nExpr);
  }

  return rc;
}




void sqlite3WindowDelete(sqlite3 *db, Window *p){
  if( p ){
    sqlite3ExprDelete(db, p->pFilter);
    sqlite3ExprListDelete(db, p->pPartition);
    sqlite3ExprListDelete(db, p->pOrderBy);
    sqlite3ExprDelete(db, p->pEnd);
    sqlite3ExprDelete(db, p->pStart);
    sqlite3DbFree(db, p->zName);
    sqlite3DbFree(db, p);
  }
}




void sqlite3WindowListDelete(sqlite3 *db, Window *p){
  while( p ){
    Window *pNext = p->pNextWin;
    sqlite3WindowDelete(db, p);
    p = pNext;
  }
}




Window *sqlite3WindowAlloc(
  Parse *pParse, 
  int eType,
  int eStart, Expr *pStart,
  int eEnd, Expr *pEnd
){
  Window *pWin = (Window*)sqlite3DbMallocZero(pParse->db, sizeof(Window));







>
>
>












>
>
>








>
>
>







757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799

    sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pMWin->iEphCsr, pSublist->nExpr);
  }

  return rc;
}

/*
** Free the Window object passed as the second argument.
*/
void sqlite3WindowDelete(sqlite3 *db, Window *p){
  if( p ){
    sqlite3ExprDelete(db, p->pFilter);
    sqlite3ExprListDelete(db, p->pPartition);
    sqlite3ExprListDelete(db, p->pOrderBy);
    sqlite3ExprDelete(db, p->pEnd);
    sqlite3ExprDelete(db, p->pStart);
    sqlite3DbFree(db, p->zName);
    sqlite3DbFree(db, p);
  }
}

/*
** Free the linked list of Window objects starting at the second argument.
*/
void sqlite3WindowListDelete(sqlite3 *db, Window *p){
  while( p ){
    Window *pNext = p->pNextWin;
    sqlite3WindowDelete(db, p);
    p = pNext;
  }
}

/*
** Allocate and return a new Window object.
*/
Window *sqlite3WindowAlloc(
  Parse *pParse, 
  int eType,
  int eStart, Expr *pStart,
  int eEnd, Expr *pEnd
){
  Window *pWin = (Window*)sqlite3DbMallocZero(pParse->db, sizeof(Window));
764
765
766
767
768
769
770



771
772
773
774
775
776
777
    sqlite3ExprDelete(pParse->db, pEnd);
    sqlite3ExprDelete(pParse->db, pStart);
  }

  return pWin;
}




void sqlite3WindowAttach(Parse *pParse, Expr *p, Window *pWin){
  if( p ){
    p->pWin = pWin;
    if( pWin ) pWin->pOwner = p;
  }else{
    sqlite3WindowDelete(pParse->db, pWin);
  }







>
>
>







808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
    sqlite3ExprDelete(pParse->db, pEnd);
    sqlite3ExprDelete(pParse->db, pStart);
  }

  return pWin;
}

/*
** Attach window object pWin to expression p.
*/
void sqlite3WindowAttach(Parse *pParse, Expr *p, Window *pWin){
  if( p ){
    p->pWin = pWin;
    if( pWin ) pWin->pOwner = p;
  }else{
    sqlite3WindowDelete(pParse->db, pWin);
  }
Changes to test/window4.tcl.
144
145
146
147
148
149
150








151
152
153
154
  INSERT INTO ttt VALUES(8, 2, 4);
  INSERT INTO ttt VALUES(9, 3, 5);
}

execsql_test 4.1 {
  SELECT max(c), max(b) OVER (ORDER BY b) FROM ttt GROUP BY b;
}










finish_test








>
>
>
>
>
>
>
>




144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
  INSERT INTO ttt VALUES(8, 2, 4);
  INSERT INTO ttt VALUES(9, 3, 5);
}

execsql_test 4.1 {
  SELECT max(c), max(b) OVER (ORDER BY b) FROM ttt GROUP BY b;
}

execsql_test 4.2 {
  SELECT max(b) OVER (ORDER BY max(c)) FROM ttt GROUP BY b;
}

execsql_test 4.3 {
  SELECT abs(max(b) OVER (ORDER BY b)) FROM ttt GROUP BY b;
}


finish_test

Changes to test/window4.test.
226
227
228
229
230
231
232








233
234
  INSERT INTO ttt VALUES(8, 2, 4);
  INSERT INTO ttt VALUES(9, 3, 5);
} {}

do_execsql_test 4.1 {
  SELECT max(c), max(b) OVER (ORDER BY b) FROM ttt GROUP BY b;
} {3 1   4 2   5 3}









finish_test







>
>
>
>
>
>
>
>


226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
  INSERT INTO ttt VALUES(8, 2, 4);
  INSERT INTO ttt VALUES(9, 3, 5);
} {}

do_execsql_test 4.1 {
  SELECT max(c), max(b) OVER (ORDER BY b) FROM ttt GROUP BY b;
} {3 1   4 2   5 3}

do_execsql_test 4.2 {
  SELECT max(b) OVER (ORDER BY max(c)) FROM ttt GROUP BY b;
} {1   2   3}

do_execsql_test 4.3 {
  SELECT abs(max(b) OVER (ORDER BY b)) FROM ttt GROUP BY b;
} {1   2   3}

finish_test