/ Check-in [39b4cad4]
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: f7002f86 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: 39b4cad4 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: dd661348 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/window.c.

  1850   1850       sqlite3VdbeAddOp2(v, OP_Goto, 0, addr);
  1851   1851     }
  1852   1852   }
  1853   1853   
  1854   1854   /*
  1855   1855   ** This function is called as part of generating VM programs for RANGE
  1856   1856   ** offset PRECEDING/FOLLOWING frame boundaries. Assuming "ASC" order for
  1857         -** the ORDER BY term in the window, it generates code equivalent to:
         1857  +** the ORDER BY term in the window, and that argument op is OP_Ge, it generates
         1858  +** code equivalent to:
  1858   1859   **
  1859   1860   **   if( csr1.peerVal + regVal >= csr2.peerVal ) goto lbl;
  1860   1861   **
  1861         -** A special type of arithmetic is used such that if csr.peerVal is not
  1862         -** a numeric type (real or integer), then the result of the addition is
  1863         -** a copy of csr1.peerVal.
         1862  +** The value of parameter op may also be OP_Gt or OP_Le. In these cases the
         1863  +** operator in the above pseudo-code is replaced with ">" or "<=", respectively.
         1864  +**
         1865  +** If the sort-order for the ORDER BY term in the window is DESC, then the
         1866  +** comparison is reversed. Instead of adding regVal to csr1.peerVal, it is
         1867  +** subtracted. And the comparison operator is inverted to - ">=" becomes "<=",
         1868  +** ">" becomes "<", and so on. So, with DESC sort order, if the argument op
         1869  +** is OP_Ge, the generated code is equivalent to:
         1870  +**
         1871  +**   if( csr1.peerVal - regVal <= csr2.peerVal ) goto lbl;
         1872  +**
         1873  +** A special type of arithmetic is used such that if csr1.peerVal is not
         1874  +** a numeric type (real or integer), then the result of the addition addition
         1875  +** or subtraction is a a copy of csr1.peerVal.
  1864   1876   */
  1865   1877   static void windowCodeRangeTest(
  1866   1878     WindowCodeArg *p, 
  1867   1879     int op,                          /* OP_Ge, OP_Gt, or OP_Le */
  1868         -  int csr1, 
  1869         -  int regVal, 
  1870         -  int csr2,
  1871         -  int lbl
         1880  +  int csr1,                        /* Cursor number for cursor 1 */
         1881  +  int regVal,                      /* Register containing non-negative number */
         1882  +  int csr2,                        /* Cursor number for cursor 2 */
         1883  +  int lbl                          /* Jump destination if the condition is true */
  1872   1884   ){
  1873   1885     Parse *pParse = p->pParse;
  1874   1886     Vdbe *v = sqlite3GetVdbe(pParse);
  1875         -  int reg1 = sqlite3GetTempReg(pParse);
  1876         -  int reg2 = sqlite3GetTempReg(pParse);
  1877         -  int arith = OP_Add;
  1878         -  int addrGe;
  1879         -  ExprList *pOrderBy = p->pMWin->pOrderBy;
  1880         -
  1881         -  int regString = ++pParse->nMem;
         1887  +  ExprList *pOrderBy = p->pMWin->pOrderBy;  /* ORDER BY clause for this window */
         1888  +  int reg1 = sqlite3GetTempReg(pParse);     /* Register for csr1.peerVal+regVal */
         1889  +  int reg2 = sqlite3GetTempReg(pParse);     /* Regiser for csr2.peerVal */
         1890  +  int regString = ++pParse->nMem;           /* Register for constant value '' */
         1891  +  int arith = OP_Add;                       /* OP_Add or OP_Subtract */
         1892  +  int addrGe;                               /* Jump destination */
  1882   1893   
  1883   1894     assert( op==OP_Ge || op==OP_Gt || op==OP_Le );
  1884   1895     assert( pOrderBy && pOrderBy->nExpr==1 );
  1885   1896     if( pOrderBy->a[0].sortFlags & KEYINFO_ORDER_DESC ){
  1886   1897       switch( op ){
  1887   1898         case OP_Ge: op = OP_Le; break;
  1888   1899         case OP_Gt: op = OP_Lt; break;
  1889   1900         default: assert( op==OP_Le ); op = OP_Ge; break;
  1890   1901       }
  1891   1902       arith = OP_Subtract;
  1892   1903     }
  1893   1904   
         1905  +  /* Read the peer-value from each cursor into a register */
  1894   1906     windowReadPeerValues(p, csr1, reg1);
  1895   1907     windowReadPeerValues(p, csr2, reg2);
  1896   1908   
  1897         -  /* Check if the peer value for csr1 value is a text or blob by comparing
  1898         -  ** it to the smallest possible string - ''. If it is, jump over the
  1899         -  ** OP_Add or OP_Subtract operation and proceed directly to the comparison. */
         1909  +  VdbeModuleComment((v, "CodeRangeTest: if( R%d %s R%d %s R%d ) goto lbl",
         1910  +      reg1, (arith==OP_Add ? "+" : "-"), regVal,
         1911  +      ((op==OP_Ge) ? ">=" : (op==OP_Le) ? "<=" : (op==OP_Gt) ? ">" : "<"), reg2
         1912  +  ));
         1913  +
         1914  +  /* Register reg1 currently contains csr1.peerVal (the peer-value from csr1).
         1915  +  ** This block adds (or subtracts for DESC) the numeric value in regVal
         1916  +  ** from it. Or, if reg1 is not numeric (it is a NULL, a text value or a blob),
         1917  +  ** then leave reg1 as it is. In pseudo-code, this is implemented as:
         1918  +  **
         1919  +  **   if( reg1>='' ) goto addrGe;
         1920  +  **   reg1 = reg1 +/- regVal
         1921  +  **   addrGe:
         1922  +  **
         1923  +  ** Since all strings and blobs are greater-than-or-equal-to an empty string,
         1924  +  ** the add/subtract is skipped for these, as required. If reg1 is a NULL,
         1925  +  ** then the arithmetic is performed, but since adding or subtracting from
         1926  +  ** NULL is always NULL anyway, this case is handled as required too.  */
  1900   1927     sqlite3VdbeAddOp4(v, OP_String8, 0, regString, 0, "", P4_STATIC);
  1901   1928     addrGe = sqlite3VdbeAddOp3(v, OP_Ge, regString, 0, reg1);
  1902   1929     VdbeCoverage(v);
  1903   1930     sqlite3VdbeAddOp3(v, arith, regVal, reg1, reg1);
  1904   1931     sqlite3VdbeJumpHere(v, addrGe);
         1932  +
         1933  +  /* If the BIGNULL flag is set for the ORDER BY, then it is required to 
         1934  +  ** consider NULL values to be larger than all other values, instead of 
         1935  +  ** the usual smaller. The VDBE opcodes OP_Ge and so on do not handle this
         1936  +  ** (and adding that capability causes a performance regression), so
         1937  +  ** instead if the BIGNULL flag is set then cases where either reg1 or
         1938  +  ** reg2 are NULL are handled separately in the following block. The code
         1939  +  ** generated is equivalent to:
         1940  +  **
         1941  +  **   if( reg1 IS NULL ){
         1942  +  **     if( op==OP_Gt ) goto lbl;
         1943  +  **     if( op==OP_Ge && reg2 IS NOT NULL ) goto lbl;
         1944  +  **     if( op==OP_Le && reg2 IS NULL ) goto lbl;
         1945  +  **   }else if( reg2 IS NULL ){
         1946  +  **     if( op==OP_Le ) goto lbl;
         1947  +  **   }
         1948  +  **
         1949  +  ** Additionally, if either reg1 or reg2 are NULL but the jump to lbl is 
         1950  +  ** not taken, control jumps over the comparison operator coded below this
         1951  +  ** block.  */
  1905   1952     if( pOrderBy->a[0].sortFlags & KEYINFO_ORDER_BIGNULL ){
  1906         -    int addr;
  1907         -    addr = sqlite3VdbeAddOp1(v, OP_NotNull, reg1); VdbeCoverage(v);
         1953  +    /* This block runs if reg1 contains a NULL. */
         1954  +    int addr = sqlite3VdbeAddOp1(v, OP_NotNull, reg1); VdbeCoverage(v);
  1908   1955       switch( op ){
  1909         -      case OP_Ge: sqlite3VdbeAddOp2(v, OP_Goto, 0, lbl); break;
         1956  +      case OP_Ge: 
         1957  +        sqlite3VdbeAddOp2(v, OP_Goto, 0, lbl); 
         1958  +        break;
  1910   1959         case OP_Gt: 
  1911   1960           sqlite3VdbeAddOp2(v, OP_NotNull, reg2, lbl); VdbeCoverage(v); 
  1912   1961           break;
  1913         -      default:
  1914         -        assert( op==OP_Le );
         1962  +      default: assert( op==OP_Le );
  1915   1963           sqlite3VdbeAddOp2(v, OP_IsNull, reg2, lbl); VdbeCoverage(v); 
  1916   1964           break;
  1917   1965       }
  1918         -    sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+2);
         1966  +    sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+3);
         1967  +
         1968  +    /* This block runs if reg1 is not NULL, but reg2 is. */
  1919   1969       sqlite3VdbeJumpHere(v, addr);
  1920   1970       sqlite3VdbeAddOp2(v, OP_IsNull, reg2, lbl); VdbeCoverage(v);
  1921   1971       if( op==OP_Gt || op==OP_Ge ){
  1922   1972         sqlite3VdbeChangeP2(v, -1, sqlite3VdbeCurrentAddr(v)+1);
  1923   1973       }
  1924   1974     }
         1975  +
         1976  +  /* Compare registers reg2 and reg1, taking the jump if required. Note that
         1977  +  ** control skips over this test if the BIGNULL flag is set and either
         1978  +  ** reg1 or reg2 contain a NULL value.  */
  1925   1979     sqlite3VdbeAddOp3(v, op, reg2, lbl, reg1); VdbeCoverage(v);
  1926   1980     sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
         1981  +
  1927   1982     assert( op==OP_Ge || op==OP_Gt || op==OP_Lt || op==OP_Le );
  1928   1983     testcase(op==OP_Ge); VdbeCoverageIf(v, op==OP_Ge);
  1929   1984     testcase(op==OP_Lt); VdbeCoverageIf(v, op==OP_Lt);
  1930   1985     testcase(op==OP_Le); VdbeCoverageIf(v, op==OP_Le);
  1931   1986     testcase(op==OP_Gt); VdbeCoverageIf(v, op==OP_Gt);
  1932         -
  1933   1987     sqlite3ReleaseTempReg(pParse, reg1);
  1934   1988     sqlite3ReleaseTempReg(pParse, reg2);
         1989  +
         1990  +  VdbeModuleComment((v, "CodeRangeTest: end"));
  1935   1991   }
  1936   1992   
  1937   1993   /*
  1938   1994   ** Helper function for sqlite3WindowCodeStep(). Each call to this function
  1939   1995   ** generates VM code for a single RETURN_ROW, AGGSTEP or AGGINVERSE 
  1940   1996   ** operation. Refer to the header comment for sqlite3WindowCodeStep() for
  1941   1997   ** details.

Changes to test/window8.tcl.

   242    242     ) FROM t1 ORDER BY 1 NULLS FIRST;
   243    243   }
   244    244   execsql_test 4.4.4 {
   245    245     SELECT sum(b) OVER (
   246    246       ORDER BY a DESC NULLS LAST ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING
   247    247     ) FROM t1 ORDER BY 1 NULLS LAST;
   248    248   }
          249  +
          250  +execsql_test 4.5.1 {
          251  +  SELECT sum(b) OVER (
          252  +    ORDER BY a ASC  NULLS LAST RANGE BETWEEN UNBOUNDED PRECEDING AND 10 FOLLOWING
          253  +  ) FROM t1 ORDER BY 1 NULLS LAST;
          254  +}
          255  +execsql_test 4.5.2 {
          256  +  SELECT sum(b) OVER (
          257  +    ORDER BY a DESC NULLS FIRST RANGE 
          258  +    BETWEEN UNBOUNDED PRECEDING AND 10 FOLLOWING
          259  +  ) FROM t1 ORDER BY 1 NULLS LAST;
          260  +}
   249    261   
   250    262   ==========
   251    263   
   252    264   execsql_test 5.0 {
   253    265     INSERT INTO t3 VALUES
   254    266       (NULL, 'bb', 355), (NULL, 'cc', 158), (NULL, 'aa', 399), 
   255    267       ('JJ', NULL, 839), ('FF', NULL, 618), ('BB', NULL, 393), 
................................................................................
   325    337   execsql_test 6.2 {
   326    338     SELECT string_agg(a, '.') OVER (
   327    339       ORDER BY b DESC NULLS LAST RANGE BETWEEN 7 PRECEDING AND 2 PRECEDING
   328    340     )
   329    341     FROM t2
   330    342   }
   331    343   
          344  +==========
   332    345   
   333    346   
   334    347   finish_test
   335    348   
   336    349   

Changes to test/window8.test.

  3574   3574   } {5   6   8   9   10}
  3575   3575   
  3576   3576   do_execsql_test 4.4.4 {
  3577   3577     SELECT sum(b) OVER (
  3578   3578       ORDER BY a DESC NULLS LAST ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING
  3579   3579     ) FROM t1 ORDER BY 1 NULLS LAST;
  3580   3580   } {5   6   8   9   10}
         3581  +
         3582  +do_execsql_test 4.5.1 {
         3583  +  SELECT sum(b) OVER (
         3584  +    ORDER BY a ASC  NULLS LAST RANGE BETWEEN UNBOUNDED PRECEDING AND 10 FOLLOWING
         3585  +  ) FROM t1 ORDER BY 1 NULLS LAST;
         3586  +} {9   9   15   15   15}
         3587  +
         3588  +do_execsql_test 4.5.2 {
         3589  +  SELECT sum(b) OVER (
         3590  +    ORDER BY a DESC NULLS FIRST RANGE 
         3591  +    BETWEEN UNBOUNDED PRECEDING AND 10 FOLLOWING
         3592  +  ) FROM t1 ORDER BY 1 NULLS LAST;
         3593  +} {6   6   6   15   15}
  3581   3594   
  3582   3595   #==========================================================================
  3583   3596   
  3584   3597   do_execsql_test 5.0 {
  3585   3598     INSERT INTO t3 VALUES
  3586   3599       (NULL, 'bb', 355), (NULL, 'cc', 158), (NULL, 'aa', 399), 
  3587   3600       ('JJ', NULL, 839), ('FF', NULL, 618), ('BB', NULL, 393), 
................................................................................
  6185   6198   
  6186   6199   do_execsql_test 6.2 {
  6187   6200     SELECT group_concat(a, '.') OVER (
  6188   6201       ORDER BY b DESC NULLS LAST RANGE BETWEEN 7 PRECEDING AND 2 PRECEDING
  6189   6202     )
  6190   6203     FROM t2
  6191   6204   } {{}   A.B   A.B}
         6205  +
         6206  +#==========================================================================
  6192   6207   
  6193   6208   finish_test