/ Check-in [5129bcc9]
Login

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

Overview
Comment:Expand on header comment for sqlite3WindowCodeStep(). Further simplify the implementation of the same.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | window-functions
Files: files | file ages | folders
SHA3-256: 5129bcc996b3c9f78ab6b674a4364787e7b353b90f15f027cad4431012022c30
User & Date: dan 2019-03-12 15:21:51
Wiki:window-functions
Context
2019-03-12
18:28
Allow real values to be used in PRECEDING and FOLLOWING expressions for RANGE window frames. check-in: 25ff7091 user: dan tags: window-functions
15:21
Expand on header comment for sqlite3WindowCodeStep(). Further simplify the implementation of the same. check-in: 5129bcc9 user: dan tags: window-functions
2019-03-11
19:50
Remove "cache mode" from the window frame code generator. Handle the same cases by editing the window frame specification itself. check-in: 08126353 user: dan tags: window-functions
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/window.c.

  1490   1490   ** arrays of registers using the collation sequences and other comparison
  1491   1491   ** parameters specified by pOrderBy. 
  1492   1492   **
  1493   1493   ** If the two arrays are not equal, the contents of regNew is copied to 
  1494   1494   ** regOld and control falls through. Otherwise, if the contents of the arrays
  1495   1495   ** are equal, an OP_Goto is executed. The address of the OP_Goto is returned.
  1496   1496   */
  1497         -static int windowIfNewPeer(
         1497  +static void windowIfNewPeer(
  1498   1498     Parse *pParse,
  1499   1499     ExprList *pOrderBy,
  1500   1500     int regNew,                     /* First in array of new values */
  1501         -  int regOld                      /* First in array of old values */
         1501  +  int regOld,                     /* First in array of old values */
         1502  +  int addr                        /* Jump here */
  1502   1503   ){
  1503   1504     Vdbe *v = sqlite3GetVdbe(pParse);
  1504         -  int addr;
  1505   1505     if( pOrderBy ){
  1506   1506       int nVal = pOrderBy->nExpr;
  1507   1507       KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pOrderBy, 0, 0);
  1508   1508       sqlite3VdbeAddOp3(v, OP_Compare, regOld, regNew, nVal);
  1509   1509       sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
  1510         -    addr = sqlite3VdbeAddOp3(
  1511         -        v, OP_Jump, sqlite3VdbeCurrentAddr(v)+1, 0, sqlite3VdbeCurrentAddr(v)+1
         1510  +    sqlite3VdbeAddOp3(v, OP_Jump, 
         1511  +      sqlite3VdbeCurrentAddr(v)+1, addr, sqlite3VdbeCurrentAddr(v)+1
  1512   1512       );
  1513   1513       VdbeCoverageEqNe(v);
  1514   1514       sqlite3VdbeAddOp3(v, OP_Copy, regNew, regOld, nVal-1);
  1515   1515     }else{
  1516         -    addr = sqlite3VdbeAddOp0(v, OP_Goto);
         1516  +    sqlite3VdbeAddOp2(v, OP_Goto, 0, addr);
  1517   1517     }
  1518         -  return addr;
  1519   1518   }
  1520   1519   
  1521   1520   typedef struct WindowCodeArg WindowCodeArg;
  1522   1521   typedef struct WindowCsrAndReg WindowCsrAndReg;
  1523   1522   struct WindowCsrAndReg {
  1524   1523     int csr;
  1525   1524     int reg;
................................................................................
  1704   1703     }
  1705   1704   
  1706   1705     if( bPeer ){
  1707   1706       int addr;
  1708   1707       int nReg = (pMWin->pOrderBy ? pMWin->pOrderBy->nExpr : 0);
  1709   1708       int regTmp = (nReg ? sqlite3GetTempRange(pParse, nReg) : 0);
  1710   1709       windowReadPeerValues(p, csr, regTmp);
  1711         -    addr = windowIfNewPeer(pParse, pMWin->pOrderBy, regTmp, reg);
  1712         -    sqlite3VdbeChangeP2(v, addr, addrContinue);
         1710  +    windowIfNewPeer(pParse, pMWin->pOrderBy, regTmp, reg, addrContinue);
  1713   1711       sqlite3ReleaseTempRange(pParse, regTmp, nReg);
  1714   1712     }
  1715   1713   
  1716   1714     if( addrNextRange ){
  1717   1715       sqlite3VdbeAddOp2(v, OP_Goto, 0, addrNextRange);
  1718   1716     }
  1719   1717     sqlite3VdbeResolveLabel(v, lblDone);
................................................................................
  1846   1844   **
  1847   1845   **     ... loop started by sqlite3WhereBegin() ...
  1848   1846   **       if( new partition ){
  1849   1847   **         Gosub flush
  1850   1848   **       }
  1851   1849   **       Insert new row into eph table.
  1852   1850   **       if( first row of partition ){
  1853         -**         Rewind(csrEnd)
  1854         -**         Rewind(csrStart)
  1855         -**         Rewind(csrCurrent)
         1851  +**         Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
  1856   1852   **         regEnd = <expr2>
  1857   1853   **         regStart = <expr1>
  1858   1854   **       }else{
  1859   1855   **         if( (regEnd--)<=0 ){
  1860   1856   **           AGGSTEP
  1861   1857   **         }
  1862   1858   **         RETURN_ROW
................................................................................
  1876   1872   **
  1877   1873   **     ... loop started by sqlite3WhereBegin() ...
  1878   1874   **     if( new partition ){
  1879   1875   **       Gosub flush
  1880   1876   **     }
  1881   1877   **     Insert new row into eph table.
  1882   1878   **     if( first row of partition ){
  1883         -**       Rewind(csrEnd)
  1884         -**       Rewind(csrStart)
  1885         -**       Rewind(csrCurrent)
         1879  +**       Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
  1886   1880   **       regEnd = <expr2>
  1887   1881   **       regStart = regEnd - <expr1>
  1888   1882   **     }else{
  1889   1883   **       AGGSTEP
  1890   1884   **       if( (regEnd--)<=0 ){
  1891   1885   **         RETURN_ROW
  1892   1886   **       }
................................................................................
  1922   1916   **
  1923   1917   **     ... loop started by sqlite3WhereBegin() ...
  1924   1918   **     if( new partition ){
  1925   1919   **       Gosub flush
  1926   1920   **     }
  1927   1921   **     Insert new row into eph table.
  1928   1922   **     if( first row of partition ){
  1929         -**       Rewind(csrEnd)
  1930         -**       Rewind(csrStart)
  1931         -**       Rewind(csrCurrent)
         1923  +**       Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
  1932   1924   **       regStart = <expr1>
  1933   1925   **     }else{
  1934   1926   **       AGGSTEP
  1935   1927   **     }
  1936   1928   **   }
  1937   1929   **   flush:
  1938   1930   **     AGGSTEP
................................................................................
  1942   1934   **         if( eof ) break
  1943   1935   **       }
  1944   1936   **       RETURN_ROW
  1945   1937   **     }
  1946   1938   **     while( !eof csrCurrent ){
  1947   1939   **       RETURN_ROW
  1948   1940   **     }
         1941  +**
         1942  +** Also requiring special handling are the cases:
         1943  +**
         1944  +**   ROWS BETWEEN <expr1> PRECEDING AND <expr2> PRECEDING
         1945  +**   ROWS BETWEEN <expr1> FOLLOWING AND <expr2> FOLLOWING
         1946  +**
         1947  +** when (expr1 < expr2). This is detected at runtime, not by this function.
         1948  +** To handle this case, the pseudo-code programs depicted above are modified
         1949  +** slightly to be:
         1950  +**
         1951  +**     ... loop started by sqlite3WhereBegin() ...
         1952  +**     if( new partition ){
         1953  +**       Gosub flush
         1954  +**     }
         1955  +**     Insert new row into eph table.
         1956  +**     if( first row of partition ){
         1957  +**       Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
         1958  +**       regEnd = <expr2>
         1959  +**       regStart = <expr1>
         1960  +**       if( regEnd < regStart ){
         1961  +**         RETURN_ROW
         1962  +**         delete eph table contents
         1963  +**         continue
         1964  +**       }
         1965  +**     ...
         1966  +**
         1967  +** The new "continue" statement in the above jumps to the next iteration
         1968  +** of the outer loop - the one started by sqlite3WhereBegin().
         1969  +**
         1970  +** The various GROUPS cases are implemented using the same patterns as
         1971  +** ROWS. The VM code is modified slightly so that:
         1972  +**
         1973  +**   1. The else branch in the main loop is only taken if the row just
         1974  +**      added to the ephemeral table is the start of a new group. In
         1975  +**      other words, it becomes:
         1976  +**
         1977  +**         ... loop started by sqlite3WhereBegin() ...
         1978  +**         if( new partition ){
         1979  +**           Gosub flush
         1980  +**         }
         1981  +**         Insert new row into eph table.
         1982  +**         if( first row of partition ){
         1983  +**           Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
         1984  +**           regEnd = <expr2>
         1985  +**           regStart = <expr1>
         1986  +**         }else if( new group ){
         1987  +**           ... 
         1988  +**         }
         1989  +**       }
         1990  +**
         1991  +**   2. Instead of processing a single row, each RETURN_ROW, AGGSTEP or 
         1992  +**      AGGINVERSE step processes the current row of the relevant cursor and
         1993  +**      all subsequent rows belonging to the same group.
         1994  +**
         1995  +** RANGE window frames are a little different again. As for GROUPS, the 
         1996  +** main loop runs once per group only. And RETURN_ROW, AGGSTEP and AGGINVERSE
         1997  +** deal in groups instead of rows. As for ROWS and GROUPS, there are three
         1998  +** basic cases:
         1999  +**
         2000  +**   RANGE BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
         2001  +**
         2002  +**     ... loop started by sqlite3WhereBegin() ...
         2003  +**       if( new partition ){
         2004  +**         Gosub flush
         2005  +**       }
         2006  +**       Insert new row into eph table.
         2007  +**       if( first row of partition ){
         2008  +**         Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
         2009  +**         regEnd = <expr2>
         2010  +**         regStart = <expr1>
         2011  +**       }else{
         2012  +**         AGGSTEP
         2013  +**         while( (csrCurrent.key + regEnd) < csrEnd.key ){
         2014  +**           RETURN_ROW
         2015  +**           while( csrStart.key + regStart) < csrCurrent.key ){
         2016  +**             AGGINVERSE
         2017  +**           }
         2018  +**         }
         2019  +**       }
         2020  +**     }
         2021  +**     flush:
         2022  +**       AGGSTEP
         2023  +**       while( 1 ){
         2024  +**         RETURN ROW
         2025  +**         if( csrCurrent is EOF ) break;
         2026  +**           while( csrStart.key + regStart) < csrCurrent.key ){
         2027  +**             AGGINVERSE
         2028  +**           }
         2029  +**         }
         2030  +**       }
         2031  +**
         2032  +** In the above notation, "csr.key" means the current value of the ORDER BY 
         2033  +** expression (there is only ever 1 for a RANGE that uses an <expr> FOLLOWING
         2034  +** or <expr PRECEDING) read from cursor csr.
         2035  +**
         2036  +**   RANGE BETWEEN <expr1> PRECEDING AND <expr2> PRECEDING
         2037  +**
         2038  +**     ... loop started by sqlite3WhereBegin() ...
         2039  +**       if( new partition ){
         2040  +**         Gosub flush
         2041  +**       }
         2042  +**       Insert new row into eph table.
         2043  +**       if( first row of partition ){
         2044  +**         Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
         2045  +**         regEnd = <expr2>
         2046  +**         regStart = <expr1>
         2047  +**       }else{
         2048  +**         while( (csrEnd.key + regEnd) <= csrCurrent.key ){
         2049  +**           AGGSTEP
         2050  +**         }
         2051  +**         RETURN_ROW
         2052  +**         while( (csrStart.key + regStart) < csrCurrent.key ){
         2053  +**           AGGINVERSE
         2054  +**         }
         2055  +**       }
         2056  +**     }
         2057  +**     flush:
         2058  +**       while( (csrEnd.key + regEnd) <= csrCurrent.key ){
         2059  +**         AGGSTEP
         2060  +**       }
         2061  +**       RETURN_ROW
         2062  +**
         2063  +**   RANGE BETWEEN <expr1> FOLLOWING AND <expr2> FOLLOWING
         2064  +**
         2065  +**     ... loop started by sqlite3WhereBegin() ...
         2066  +**       if( new partition ){
         2067  +**         Gosub flush
         2068  +**       }
         2069  +**       Insert new row into eph table.
         2070  +**       if( first row of partition ){
         2071  +**         Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
         2072  +**         regEnd = <expr2>
         2073  +**         regStart = <expr1>
         2074  +**       }else{
         2075  +**         AGGSTEP
         2076  +**         while( (csrCurrent.key + regEnd) < csrEnd.key ){
         2077  +**           while( (csrCurrent.key + regStart) > csrStart.key ){
         2078  +**             AGGINVERSE
         2079  +**           }
         2080  +**           RETURN_ROW
         2081  +**         }
         2082  +**       }
         2083  +**     }
         2084  +**     flush:
         2085  +**       AGGSTEP
         2086  +**       while( 1 ){
         2087  +**         while( (csrCurrent.key + regStart) > csrStart.key ){
         2088  +**           AGGINVERSE
         2089  +**           if( eof ) break "while( 1 )" loop.
         2090  +**         }
         2091  +**         RETURN_ROW
         2092  +**       }
         2093  +**       while( !eof csrCurrent ){
         2094  +**         RETURN_ROW
         2095  +**       }
         2096  +**
  1949   2097   */
  1950   2098   void sqlite3WindowCodeStep(
  1951   2099     Parse *pParse,                  /* Parse context */
  1952   2100     Select *p,                      /* Rewritten SELECT statement */
  1953   2101     WhereInfo *pWInfo,              /* Context returned by sqlite3WhereBegin() */
  1954   2102     int regGosub,                   /* Register for OP_Gosub */
  1955   2103     int addrGosub                   /* OP_Gosub here to return each row */
................................................................................
  1958   2106     ExprList *pOrderBy = pMWin->pOrderBy;
  1959   2107     Vdbe *v = sqlite3GetVdbe(pParse);
  1960   2108     int regFlushPart;               /* Register for "Gosub flush_partition" */
  1961   2109     int csrWrite;                   /* Cursor used to write to eph. table */
  1962   2110     int csrInput = p->pSrc->a[0].iCursor;     /* Cursor of sub-select */
  1963   2111     int nInput = p->pSrc->a[0].pTab->nCol;    /* Number of cols returned by sub */
  1964   2112     int iInput;                               /* To iterate through sub cols */
  1965         -  int addrGoto;                   /* Address of OP_Goto */
  1966   2113     int addrIfNot;                  /* Address of OP_IfNot */
  1967   2114     int addrGosubFlush;             /* Address of OP_Gosub to flush: */
  1968   2115     int addrInteger;                /* Address of OP_Integer */
  1969         -  int addrShortcut = 0;
  1970   2116     int addrEmpty = 0;              /* Address of OP_Rewind in flush: */
  1971         -  int addrPeerJump = 0;           /* Address of jump taken if not new peer */
  1972   2117     int regStart = 0;               /* Value of <expr> PRECEDING */
  1973   2118     int regEnd = 0;                 /* Value of <expr> FOLLOWING */
  1974   2119     int regNew;                     /* Array of registers holding new input row */
  1975   2120     int regRecord;                  /* regNew array in record form */
  1976   2121     int regRowid;                   /* Rowid for regRecord in eph table */
  1977   2122     int regNewPeer = 0;             /* Peer values for new row (part of regNew) */
  1978   2123     int regPeer = 0;                /* Peer values for current row */
  1979   2124     WindowCodeArg s;                /* Context object for sub-routines */
         2125  +  int lblWhereEnd;                /* Label just before sqlite3WhereEnd() code */
  1980   2126   
  1981   2127     assert( pMWin->eStart==TK_PRECEDING || pMWin->eStart==TK_CURRENT 
  1982   2128          || pMWin->eStart==TK_FOLLOWING || pMWin->eStart==TK_UNBOUNDED 
  1983   2129     );
  1984   2130     assert( pMWin->eEnd==TK_FOLLOWING || pMWin->eEnd==TK_CURRENT 
  1985   2131          || pMWin->eEnd==TK_UNBOUNDED || pMWin->eEnd==TK_PRECEDING 
  1986   2132     );
  1987   2133   
  1988         -  /* Determine whether or not each partition will be cached before beginning
  1989         -  ** to process rows within it.  */
         2134  +  lblWhereEnd = sqlite3VdbeMakeLabel(pParse);
  1990   2135   
  1991   2136     /* Fill in the context object */
  1992   2137     memset(&s, 0, sizeof(WindowCodeArg));
  1993   2138     s.pParse = pParse;
  1994   2139     s.pMWin = pMWin;
  1995   2140     s.pVdbe = v;
  1996   2141     s.regGosub = regGosub;
................................................................................
  2079   2224     if( pMWin->eStart==pMWin->eEnd && regStart && regEnd ){
  2080   2225       int op = ((pMWin->eStart==TK_FOLLOWING) ? OP_Ge : OP_Le);
  2081   2226       int addrGe = sqlite3VdbeAddOp3(v, op, regStart, 0, regEnd);
  2082   2227       windowAggFinal(pParse, pMWin, 0);
  2083   2228       sqlite3VdbeAddOp2(v, OP_Rewind, s.current.csr, 1);
  2084   2229       windowReturnOneRow(pParse, pMWin, regGosub, addrGosub);
  2085   2230       sqlite3VdbeAddOp1(v, OP_ResetSorter, s.current.csr);
  2086         -    addrShortcut = sqlite3VdbeAddOp0(v, OP_Goto);
         2231  +    sqlite3VdbeAddOp2(v, OP_Goto, 0, lblWhereEnd);
  2087   2232       sqlite3VdbeJumpHere(v, addrGe);
  2088   2233     }
  2089   2234     if( pMWin->eStart==TK_FOLLOWING && pMWin->eType!=TK_RANGE && regEnd ){
  2090   2235       assert( pMWin->eEnd==TK_FOLLOWING );
  2091   2236       sqlite3VdbeAddOp3(v, OP_Subtract, regStart, regEnd, regStart);
  2092   2237     }
  2093   2238   
................................................................................
  2100   2245       sqlite3VdbeAddOp3(v, OP_Copy, regNewPeer, regPeer, pOrderBy->nExpr-1);
  2101   2246       sqlite3VdbeAddOp3(v, OP_Copy, regPeer, s.start.reg, pOrderBy->nExpr-1);
  2102   2247       sqlite3VdbeAddOp3(v, OP_Copy, regPeer, s.current.reg, pOrderBy->nExpr-1);
  2103   2248       sqlite3VdbeAddOp3(v, OP_Copy, regPeer, s.end.reg, pOrderBy->nExpr-1);
  2104   2249     }
  2105   2250   
  2106   2251     sqlite3VdbeAddOp2(v, OP_Integer, 0, pMWin->regFirst);
  2107         -  addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
         2252  +  sqlite3VdbeAddOp2(v, OP_Goto, 0, lblWhereEnd);
  2108   2253   
  2109   2254     /* Begin generating SECOND_ROW_CODE */
  2110   2255     VdbeModuleComment((pParse->pVdbe, "Begin WindowCodeStep.SECOND_ROW"));
  2111   2256     sqlite3VdbeJumpHere(v, addrIfNot);
  2112   2257     if( regPeer ){
  2113         -    addrPeerJump = windowIfNewPeer(pParse, pOrderBy, regNewPeer, regPeer);
         2258  +    windowIfNewPeer(pParse, pOrderBy, regNewPeer, regPeer, lblWhereEnd);
  2114   2259     }
  2115   2260     if( pMWin->eStart==TK_FOLLOWING ){
  2116   2261       windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0);
  2117   2262       if( pMWin->eEnd!=TK_UNBOUNDED ){
  2118   2263         if( pMWin->eType==TK_RANGE ){
  2119   2264           int lbl = sqlite3VdbeMakeLabel(pParse);
  2120   2265           int addrNext = sqlite3VdbeCurrentAddr(v);
................................................................................
  2154   2299           if( regEnd ) addr = sqlite3VdbeAddOp3(v, OP_IfPos, regEnd, 0, 1);
  2155   2300           windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0);
  2156   2301           windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0);
  2157   2302           if( regEnd ) sqlite3VdbeJumpHere(v, addr);
  2158   2303         }
  2159   2304       }
  2160   2305     }
  2161         -  if( addrPeerJump ){
  2162         -    sqlite3VdbeJumpHere(v, addrPeerJump);
  2163         -  }
  2164   2306     VdbeModuleComment((pParse->pVdbe, "End WindowCodeStep.SECOND_ROW"));
  2165   2307   
  2166   2308     /* End of the main input loop */
  2167         -  sqlite3VdbeJumpHere(v, addrGoto);
  2168         -  if( addrShortcut>0 ) sqlite3VdbeJumpHere(v, addrShortcut);
         2309  +  sqlite3VdbeResolveLabel(v, lblWhereEnd);
  2169   2310     sqlite3WhereEnd(pWInfo);
  2170   2311   
  2171   2312     /* Fall through */
  2172   2313     if( pMWin->pPartition ){
  2173   2314       addrInteger = sqlite3VdbeAddOp2(v, OP_Integer, 0, regFlushPart);
  2174   2315       sqlite3VdbeJumpHere(v, addrGosubFlush);
  2175   2316     }
................................................................................
  2213   2354       windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0);
  2214   2355       addrStart = sqlite3VdbeCurrentAddr(v);
  2215   2356       addrBreak = windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 1);
  2216   2357       windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0);
  2217   2358       sqlite3VdbeAddOp2(v, OP_Goto, 0, addrStart);
  2218   2359       sqlite3VdbeJumpHere(v, addrBreak);
  2219   2360     }
  2220         -
  2221   2361     sqlite3VdbeJumpHere(v, addrEmpty);
  2222   2362   
  2223   2363     sqlite3VdbeAddOp1(v, OP_ResetSorter, s.current.csr);
  2224   2364     sqlite3VdbeAddOp2(v, OP_Integer, 1, pMWin->regFirst);
  2225   2365     VdbeModuleComment((pParse->pVdbe, "End WindowCodeStep.FLUSH"));
  2226   2366     if( pMWin->pPartition ){
  2227   2367       sqlite3VdbeChangeP1(v, addrInteger, sqlite3VdbeCurrentAddr(v));
  2228   2368       sqlite3VdbeAddOp1(v, OP_Return, regFlushPart);
  2229   2369     }
  2230   2370   }
  2231   2371   
  2232   2372   #endif /* SQLITE_OMIT_WINDOWFUNC */