/ Check-in [39b4cad4a5]
Login

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

Overview
Comment:Fix a bug in RANGE window functions that use "ORDER BY <expr> DESC NULLS FIRST" as the window-frame ORDER BY clause.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 39b4cad4a51bb5116d62ffb16ac36d96a9280321b049eb2d008605392f52a459
User & Date: dan 2019-08-30 16:14:58
Context
2019-08-30
16:46
New test cases for window functions with RANGE BETWEEN and DESC NULLS FIRST. check-in: f7002f86c7 user: drh tags: trunk
16:14
Fix a bug in RANGE window functions that use "ORDER BY <expr> DESC NULLS FIRST" as the window-frame ORDER BY clause. check-in: 39b4cad4a5 user: dan tags: trunk
16:00
The expression "(X IS FALSE) IN (FALSE)" does not imply that X is NOT NULL. Ticket [f8f472cbc77ba9c9] check-in: dd66134817 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/window.c.

1850
1851
1852
1853
1854
1855
1856
1857

1858
1859
1860











1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893

1894
1895
1896
1897
1898
1899















1900
1901
1902
1903
1904




















1905
1906

1907
1908

1909

1910
1911
1912
1913
1914
1915
1916
1917
1918


1919
1920
1921
1922
1923
1924




1925
1926

1927
1928
1929
1930
1931
1932
1933
1934


1935
1936
1937
1938
1939
1940
1941
    sqlite3VdbeAddOp2(v, OP_Goto, 0, addr);
  }
}

/*
** This function is called as part of generating VM programs for RANGE
** offset PRECEDING/FOLLOWING frame boundaries. Assuming "ASC" order for
** the ORDER BY term in the window, it generates code equivalent to:

**
**   if( csr1.peerVal + regVal >= csr2.peerVal ) goto lbl;
**











** A special type of arithmetic is used such that if csr.peerVal is not
** a numeric type (real or integer), then the result of the addition is
** a copy of csr1.peerVal.
*/
static void windowCodeRangeTest(
  WindowCodeArg *p, 
  int op,                          /* OP_Ge, OP_Gt, or OP_Le */
  int csr1, 
  int regVal, 
  int csr2,
  int lbl
){
  Parse *pParse = p->pParse;
  Vdbe *v = sqlite3GetVdbe(pParse);
  int reg1 = sqlite3GetTempReg(pParse);
  int reg2 = sqlite3GetTempReg(pParse);
  int arith = OP_Add;
  int addrGe;
  ExprList *pOrderBy = p->pMWin->pOrderBy;

  int regString = ++pParse->nMem;

  assert( op==OP_Ge || op==OP_Gt || op==OP_Le );
  assert( pOrderBy && pOrderBy->nExpr==1 );
  if( pOrderBy->a[0].sortFlags & KEYINFO_ORDER_DESC ){
    switch( op ){
      case OP_Ge: op = OP_Le; break;
      case OP_Gt: op = OP_Lt; break;
      default: assert( op==OP_Le ); op = OP_Ge; break;
    }
    arith = OP_Subtract;
  }


  windowReadPeerValues(p, csr1, reg1);
  windowReadPeerValues(p, csr2, reg2);

  /* Check if the peer value for csr1 value is a text or blob by comparing
  ** it to the smallest possible string - ''. If it is, jump over the
  ** OP_Add or OP_Subtract operation and proceed directly to the comparison. */















  sqlite3VdbeAddOp4(v, OP_String8, 0, regString, 0, "", P4_STATIC);
  addrGe = sqlite3VdbeAddOp3(v, OP_Ge, regString, 0, reg1);
  VdbeCoverage(v);
  sqlite3VdbeAddOp3(v, arith, regVal, reg1, reg1);
  sqlite3VdbeJumpHere(v, addrGe);




















  if( pOrderBy->a[0].sortFlags & KEYINFO_ORDER_BIGNULL ){
    int addr;

    addr = sqlite3VdbeAddOp1(v, OP_NotNull, reg1); VdbeCoverage(v);
    switch( op ){

      case OP_Ge: sqlite3VdbeAddOp2(v, OP_Goto, 0, lbl); break;

      case OP_Gt: 
        sqlite3VdbeAddOp2(v, OP_NotNull, reg2, lbl); VdbeCoverage(v); 
        break;
      default:
        assert( op==OP_Le );
        sqlite3VdbeAddOp2(v, OP_IsNull, reg2, lbl); VdbeCoverage(v); 
        break;
    }
    sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+2);


    sqlite3VdbeJumpHere(v, addr);
    sqlite3VdbeAddOp2(v, OP_IsNull, reg2, lbl); VdbeCoverage(v);
    if( op==OP_Gt || op==OP_Ge ){
      sqlite3VdbeChangeP2(v, -1, sqlite3VdbeCurrentAddr(v)+1);
    }
  }




  sqlite3VdbeAddOp3(v, op, reg2, lbl, reg1); VdbeCoverage(v);
  sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);

  assert( op==OP_Ge || op==OP_Gt || op==OP_Lt || op==OP_Le );
  testcase(op==OP_Ge); VdbeCoverageIf(v, op==OP_Ge);
  testcase(op==OP_Lt); VdbeCoverageIf(v, op==OP_Lt);
  testcase(op==OP_Le); VdbeCoverageIf(v, op==OP_Le);
  testcase(op==OP_Gt); VdbeCoverageIf(v, op==OP_Gt);

  sqlite3ReleaseTempReg(pParse, reg1);
  sqlite3ReleaseTempReg(pParse, reg2);


}

/*
** Helper function for sqlite3WindowCodeStep(). Each call to this function
** generates VM code for a single RETURN_ROW, AGGSTEP or AGGINVERSE 
** operation. Refer to the header comment for sqlite3WindowCodeStep() for
** details.







|
>



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




|
|
|
|



|
|
|
|
|
|
<












>



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





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

<
>
|

>
|
>



<
|



|
>
>






>
>
>
>


>





<


>
>







1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892

1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952

1953
1954
1955
1956
1957
1958
1959
1960
1961

1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986

1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
    sqlite3VdbeAddOp2(v, OP_Goto, 0, addr);
  }
}

/*
** This function is called as part of generating VM programs for RANGE
** offset PRECEDING/FOLLOWING frame boundaries. Assuming "ASC" order for
** the ORDER BY term in the window, and that argument op is OP_Ge, it generates
** code equivalent to:
**
**   if( csr1.peerVal + regVal >= csr2.peerVal ) goto lbl;
**
** The value of parameter op may also be OP_Gt or OP_Le. In these cases the
** operator in the above pseudo-code is replaced with ">" or "<=", respectively.
**
** If the sort-order for the ORDER BY term in the window is DESC, then the
** comparison is reversed. Instead of adding regVal to csr1.peerVal, it is
** subtracted. And the comparison operator is inverted to - ">=" becomes "<=",
** ">" becomes "<", and so on. So, with DESC sort order, if the argument op
** is OP_Ge, the generated code is equivalent to:
**
**   if( csr1.peerVal - regVal <= csr2.peerVal ) goto lbl;
**
** A special type of arithmetic is used such that if csr1.peerVal is not
** a numeric type (real or integer), then the result of the addition addition
** or subtraction is a a copy of csr1.peerVal.
*/
static void windowCodeRangeTest(
  WindowCodeArg *p, 
  int op,                          /* OP_Ge, OP_Gt, or OP_Le */
  int csr1,                        /* Cursor number for cursor 1 */
  int regVal,                      /* Register containing non-negative number */
  int csr2,                        /* Cursor number for cursor 2 */
  int lbl                          /* Jump destination if the condition is true */
){
  Parse *pParse = p->pParse;
  Vdbe *v = sqlite3GetVdbe(pParse);
  ExprList *pOrderBy = p->pMWin->pOrderBy;  /* ORDER BY clause for this window */
  int reg1 = sqlite3GetTempReg(pParse);     /* Register for csr1.peerVal+regVal */
  int reg2 = sqlite3GetTempReg(pParse);     /* Regiser for csr2.peerVal */
  int regString = ++pParse->nMem;           /* Register for constant value '' */
  int arith = OP_Add;                       /* OP_Add or OP_Subtract */
  int addrGe;                               /* Jump destination */


  assert( op==OP_Ge || op==OP_Gt || op==OP_Le );
  assert( pOrderBy && pOrderBy->nExpr==1 );
  if( pOrderBy->a[0].sortFlags & KEYINFO_ORDER_DESC ){
    switch( op ){
      case OP_Ge: op = OP_Le; break;
      case OP_Gt: op = OP_Lt; break;
      default: assert( op==OP_Le ); op = OP_Ge; break;
    }
    arith = OP_Subtract;
  }

  /* Read the peer-value from each cursor into a register */
  windowReadPeerValues(p, csr1, reg1);
  windowReadPeerValues(p, csr2, reg2);

  VdbeModuleComment((v, "CodeRangeTest: if( R%d %s R%d %s R%d ) goto lbl",
      reg1, (arith==OP_Add ? "+" : "-"), regVal,
      ((op==OP_Ge) ? ">=" : (op==OP_Le) ? "<=" : (op==OP_Gt) ? ">" : "<"), reg2
  ));

  /* Register reg1 currently contains csr1.peerVal (the peer-value from csr1).
  ** This block adds (or subtracts for DESC) the numeric value in regVal
  ** from it. Or, if reg1 is not numeric (it is a NULL, a text value or a blob),
  ** then leave reg1 as it is. In pseudo-code, this is implemented as:
  **
  **   if( reg1>='' ) goto addrGe;
  **   reg1 = reg1 +/- regVal
  **   addrGe:
  **
  ** Since all strings and blobs are greater-than-or-equal-to an empty string,
  ** the add/subtract is skipped for these, as required. If reg1 is a NULL,
  ** then the arithmetic is performed, but since adding or subtracting from
  ** NULL is always NULL anyway, this case is handled as required too.  */
  sqlite3VdbeAddOp4(v, OP_String8, 0, regString, 0, "", P4_STATIC);
  addrGe = sqlite3VdbeAddOp3(v, OP_Ge, regString, 0, reg1);
  VdbeCoverage(v);
  sqlite3VdbeAddOp3(v, arith, regVal, reg1, reg1);
  sqlite3VdbeJumpHere(v, addrGe);

  /* If the BIGNULL flag is set for the ORDER BY, then it is required to 
  ** consider NULL values to be larger than all other values, instead of 
  ** the usual smaller. The VDBE opcodes OP_Ge and so on do not handle this
  ** (and adding that capability causes a performance regression), so
  ** instead if the BIGNULL flag is set then cases where either reg1 or
  ** reg2 are NULL are handled separately in the following block. The code
  ** generated is equivalent to:
  **
  **   if( reg1 IS NULL ){
  **     if( op==OP_Gt ) goto lbl;
  **     if( op==OP_Ge && reg2 IS NOT NULL ) goto lbl;
  **     if( op==OP_Le && reg2 IS NULL ) goto lbl;
  **   }else if( reg2 IS NULL ){
  **     if( op==OP_Le ) goto lbl;
  **   }
  **
  ** Additionally, if either reg1 or reg2 are NULL but the jump to lbl is 
  ** not taken, control jumps over the comparison operator coded below this
  ** block.  */
  if( pOrderBy->a[0].sortFlags & KEYINFO_ORDER_BIGNULL ){

    /* This block runs if reg1 contains a NULL. */
    int addr = sqlite3VdbeAddOp1(v, OP_NotNull, reg1); VdbeCoverage(v);
    switch( op ){
      case OP_Ge: 
        sqlite3VdbeAddOp2(v, OP_Goto, 0, lbl); 
        break;
      case OP_Gt: 
        sqlite3VdbeAddOp2(v, OP_NotNull, reg2, lbl); VdbeCoverage(v); 
        break;

      default: assert( op==OP_Le );
        sqlite3VdbeAddOp2(v, OP_IsNull, reg2, lbl); VdbeCoverage(v); 
        break;
    }
    sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+3);

    /* This block runs if reg1 is not NULL, but reg2 is. */
    sqlite3VdbeJumpHere(v, addr);
    sqlite3VdbeAddOp2(v, OP_IsNull, reg2, lbl); VdbeCoverage(v);
    if( op==OP_Gt || op==OP_Ge ){
      sqlite3VdbeChangeP2(v, -1, sqlite3VdbeCurrentAddr(v)+1);
    }
  }

  /* Compare registers reg2 and reg1, taking the jump if required. Note that
  ** control skips over this test if the BIGNULL flag is set and either
  ** reg1 or reg2 contain a NULL value.  */
  sqlite3VdbeAddOp3(v, op, reg2, lbl, reg1); VdbeCoverage(v);
  sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);

  assert( op==OP_Ge || op==OP_Gt || op==OP_Lt || op==OP_Le );
  testcase(op==OP_Ge); VdbeCoverageIf(v, op==OP_Ge);
  testcase(op==OP_Lt); VdbeCoverageIf(v, op==OP_Lt);
  testcase(op==OP_Le); VdbeCoverageIf(v, op==OP_Le);
  testcase(op==OP_Gt); VdbeCoverageIf(v, op==OP_Gt);

  sqlite3ReleaseTempReg(pParse, reg1);
  sqlite3ReleaseTempReg(pParse, reg2);

  VdbeModuleComment((v, "CodeRangeTest: end"));
}

/*
** Helper function for sqlite3WindowCodeStep(). Each call to this function
** generates VM code for a single RETURN_ROW, AGGSTEP or AGGINVERSE 
** operation. Refer to the header comment for sqlite3WindowCodeStep() for
** details.

Changes to test/window8.tcl.

242
243
244
245
246
247
248












249
250
251
252
253
254
255
...
325
326
327
328
329
330
331

332
333
334
335
336
  ) FROM t1 ORDER BY 1 NULLS FIRST;
}
execsql_test 4.4.4 {
  SELECT sum(b) OVER (
    ORDER BY a DESC NULLS LAST ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING
  ) FROM t1 ORDER BY 1 NULLS LAST;
}













==========

execsql_test 5.0 {
  INSERT INTO t3 VALUES
    (NULL, 'bb', 355), (NULL, 'cc', 158), (NULL, 'aa', 399), 
    ('JJ', NULL, 839), ('FF', NULL, 618), ('BB', NULL, 393), 
................................................................................
execsql_test 6.2 {
  SELECT string_agg(a, '.') OVER (
    ORDER BY b DESC NULLS LAST RANGE BETWEEN 7 PRECEDING AND 2 PRECEDING
  )
  FROM t2
}




finish_test









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







 







>





242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
...
337
338
339
340
341
342
343
344
345
346
347
348
349
  ) FROM t1 ORDER BY 1 NULLS FIRST;
}
execsql_test 4.4.4 {
  SELECT sum(b) OVER (
    ORDER BY a DESC NULLS LAST ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING
  ) FROM t1 ORDER BY 1 NULLS LAST;
}

execsql_test 4.5.1 {
  SELECT sum(b) OVER (
    ORDER BY a ASC  NULLS LAST RANGE BETWEEN UNBOUNDED PRECEDING AND 10 FOLLOWING
  ) FROM t1 ORDER BY 1 NULLS LAST;
}
execsql_test 4.5.2 {
  SELECT sum(b) OVER (
    ORDER BY a DESC NULLS FIRST RANGE 
    BETWEEN UNBOUNDED PRECEDING AND 10 FOLLOWING
  ) FROM t1 ORDER BY 1 NULLS LAST;
}

==========

execsql_test 5.0 {
  INSERT INTO t3 VALUES
    (NULL, 'bb', 355), (NULL, 'cc', 158), (NULL, 'aa', 399), 
    ('JJ', NULL, 839), ('FF', NULL, 618), ('BB', NULL, 393), 
................................................................................
execsql_test 6.2 {
  SELECT string_agg(a, '.') OVER (
    ORDER BY b DESC NULLS LAST RANGE BETWEEN 7 PRECEDING AND 2 PRECEDING
  )
  FROM t2
}

==========


finish_test


Changes to test/window8.test.

3574
3575
3576
3577
3578
3579
3580













3581
3582
3583
3584
3585
3586
3587
....
6185
6186
6187
6188
6189
6190
6191
6192


6193
} {5   6   8   9   10}

do_execsql_test 4.4.4 {
  SELECT sum(b) OVER (
    ORDER BY a DESC NULLS LAST ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING
  ) FROM t1 ORDER BY 1 NULLS LAST;
} {5   6   8   9   10}














#==========================================================================

do_execsql_test 5.0 {
  INSERT INTO t3 VALUES
    (NULL, 'bb', 355), (NULL, 'cc', 158), (NULL, 'aa', 399), 
    ('JJ', NULL, 839), ('FF', NULL, 618), ('BB', NULL, 393), 
................................................................................

do_execsql_test 6.2 {
  SELECT group_concat(a, '.') OVER (
    ORDER BY b DESC NULLS LAST RANGE BETWEEN 7 PRECEDING AND 2 PRECEDING
  )
  FROM t2
} {{}   A.B   A.B}



finish_test







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







 








>
>

3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591
3592
3593
3594
3595
3596
3597
3598
3599
3600
....
6198
6199
6200
6201
6202
6203
6204
6205
6206
6207
6208
} {5   6   8   9   10}

do_execsql_test 4.4.4 {
  SELECT sum(b) OVER (
    ORDER BY a DESC NULLS LAST ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING
  ) FROM t1 ORDER BY 1 NULLS LAST;
} {5   6   8   9   10}

do_execsql_test 4.5.1 {
  SELECT sum(b) OVER (
    ORDER BY a ASC  NULLS LAST RANGE BETWEEN UNBOUNDED PRECEDING AND 10 FOLLOWING
  ) FROM t1 ORDER BY 1 NULLS LAST;
} {9   9   15   15   15}

do_execsql_test 4.5.2 {
  SELECT sum(b) OVER (
    ORDER BY a DESC NULLS FIRST RANGE 
    BETWEEN UNBOUNDED PRECEDING AND 10 FOLLOWING
  ) FROM t1 ORDER BY 1 NULLS LAST;
} {6   6   6   15   15}

#==========================================================================

do_execsql_test 5.0 {
  INSERT INTO t3 VALUES
    (NULL, 'bb', 355), (NULL, 'cc', 158), (NULL, 'aa', 399), 
    ('JJ', NULL, 839), ('FF', NULL, 618), ('BB', NULL, 393), 
................................................................................

do_execsql_test 6.2 {
  SELECT group_concat(a, '.') OVER (
    ORDER BY b DESC NULLS LAST RANGE BETWEEN 7 PRECEDING AND 2 PRECEDING
  )
  FROM t2
} {{}   A.B   A.B}

#==========================================================================

finish_test