SQLite

      sqlite3DbFree(x.pParse->db, x.apExpr);
      nChng += x.nChng;
    }
  }while( x.nChng );  
  return nChng;
}

#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
# if !defined(SQLITE_OMIT_WINDOWFUNC)
/*
** This function is called to determine whether or not it is safe to
** push WHERE clause expression pExpr down to FROM clause sub-query
** pSubq, which contains at least one window function. Return 1
** if it is safe and the expression should be pushed down, or 0 
** otherwise.
**
** It is only safe to push the expression down if it consists only 
** of constants and copies of expressions that appear in the PARTITION
** BY clause of all window function used by the sub-query. It is safe
** to filter out entire partitions, but not rows within partitions, as
** this may change the results of the window functions.
**
** At the time this function is called it is guaranteed that 
**
**   * the sub-query uses only one distinct window frame, and 
**   * that the window frame has a PARTITION BY clase.
*/
static int pushDownWindowCheck(Parse *pParse, Select *pSubq, Expr *pExpr){
  assert( pSubq->pWin->pPartition );
  assert( (pSubq->selFlags & SF_MultiPart)==0 );
  assert( pSubq->pPrior==0 );
  return sqlite3ExprIsConstantOrGroupBy(pParse, pExpr, pSubq->pWin->pPartition);
}
# endif /* SQLITE_OMIT_WINDOWFUNC */
#endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */

#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
/*
** Make copies of relevant WHERE clause terms of the outer query into
** the WHERE clause of subquery.  Example:
**
**    SELECT * FROM (SELECT a AS x, c-d AS y FROM t1) WHERE x=5 AND y=10;
**

**           JOIN (SELECT 1 AS b2 UNION ALL SELECT 2) AS bb ON (a1=b2)
**           LEFT JOIN (SELECT 8 AS c3 UNION ALL SELECT 9) AS cc ON (b2=2);
**
**       The correct answer is three rows:  (1,1,NULL),(2,2,8),(2,2,9).
**       But if the (b2=2) term were to be pushed down into the bb subquery,
**       then the (1,1,NULL) row would be suppressed.
**
**   (6) Window functions make things tricky as changes to the WHERE clause 
**       of the inner query could change the window over which window 
**       functions are calculated. Therefore, do not attempt the optimization
**       if:
**
**     (6a) The inner query uses multiple incompatible window partitions.
**
**     (6b) The inner query is a compound and uses window-functions. 
**
**     (6c) The WHERE clause does not consist entirely of constants and
**          copies of expressions found in the PARTITION BY clause of
**          all window-functions used by the sub-query. It is safe to
**          filter out entire partitions, as this does not change the 
**          window over which any window-function is calculated.
**
**   (7) The inner query is a Common Table Expression (CTE) that should
**       be materialized.  (This restriction is implemented in the calling
**       routine.)
**
** Return 0 if no changes are made and non-zero if one or more WHERE clause
** terms are duplicated into the subquery.
*/
static int pushDownWhereTerms(
  Parse *pParse,        /* Parse context (for malloc() and error reporting) */
  Select *pSubq,        /* The subquery whose WHERE clause is to be augmented */
  Expr *pWhere,         /* The WHERE clause of the outer query */
  int iCursor,          /* Cursor number of the subquery */
  int isLeftJoin        /* True if pSubq is the right term of a LEFT JOIN */
){
  Expr *pNew;
  int nChng = 0;

  if( pWhere==0 ) return 0;
  if( pSubq->selFlags & (SF_Recursive|SF_MultiPart) ) return 0;

#ifndef SQLITE_OMIT_WINDOWFUNC
  if( pSubq->pPrior ){
    Select *pSel;
    for(pSel=pSubq; pSel; pSel=pSel->pPrior){
      if( pSel->pWin ) return 0;    /* restriction (6b) */
    }
  }else{
    if( pSubq->pWin && pSubq->pWin->pPartition==0 ) return 0;
  }
#endif

#ifdef SQLITE_DEBUG
  /* Only the first term of a compound can have a WITH clause.  But make
  ** sure no other terms are marked SF_Recursive in case something changes
  ** in the future.

      unsetJoinExpr(pNew, -1);
      x.pParse = pParse;
      x.iTable = iCursor;
      x.iNewTable = iCursor;
      x.isLeftJoin = 0;
      x.pEList = pSubq->pEList;
      pNew = substExpr(&x, pNew);
#ifndef SQLITE_OMIT_WINDOWFUNC
      if( pSubq->pWin && 0==pushDownWindowCheck(pParse, pSubq, pNew) ){
        /* Restriction 6c has prevented push-down in this case */
        sqlite3ExprDelete(pParse->db, pNew);
        nChng--;
        break;
      }
#endif
      if( pSubq->selFlags & SF_Aggregate ){
        pSubq->pHaving = sqlite3ExprAnd(pParse, pSubq->pHaving, pNew);
      }else{
        pSubq->pWhere = sqlite3ExprAnd(pParse, pSubq->pWhere, pNew);
      }
      pSubq = pSubq->pPrior;
    }

#define SF_ComplexResult 0x0040000 /* Result contains subquery or function */
#define SF_WhereBegin    0x0080000 /* Really a WhereBegin() call.  Debug Only */
#define SF_WinRewrite    0x0100000 /* Window function rewrite accomplished */
#define SF_View          0x0200000 /* SELECT statement is a view */
#define SF_NoopOrderBy   0x0400000 /* ORDER BY is ignored for this query */
#define SF_UpdateFrom    0x0800000 /* Statement is an UPDATE...FROM */
#define SF_PushDown      0x1000000 /* SELECT has be modified by push-down opt */
#define SF_MultiPart     0x2000000 /* Has multiple incompatible PARTITIONs */

/*
** The results of a SELECT can be distributed in several ways, as defined
** by one of the following macros.  The "SRT" prefix means "SELECT Result
** Type".
**
**     SRT_Union       Store results as a key in a temporary index

/*
** Possibly link window pWin into the list at pSel->pWin (window functions
** to be processed as part of SELECT statement pSel). The window is linked
** in if either (a) there are no other windows already linked to this
** SELECT, or (b) the windows already linked use a compatible window frame.
*/
void sqlite3WindowLink(Select *pSel, Window *pWin){
  if( pSel ){
    if( 0==pSel->pWin || 0==sqlite3WindowCompare(0, pSel->pWin, pWin, 0) ){

      pWin->pNextWin = pSel->pWin;
      if( pSel->pWin ){
        pSel->pWin->ppThis = &pWin->pNextWin;
      }
      pSel->pWin = pWin;
      pWin->ppThis = &pSel->pWin;
    }else{
      if( sqlite3ExprListCompare(pWin->pPartition, pSel->pWin->pPartition,-1) ){
        pSel->selFlags |= SF_MultiPart;
      }
    }
  }
}

/*
** Return 0 if the two window objects are identical, 1 if they are
** different, or 2 if it cannot be determined if the objects are identical
** or not. Identical window objects can be processed in a single scan.

      )
    )
  }
} -test {
  faultsim_test_result {0 {}}
}

#-------------------------------------------------------------------------
reset_db
do_execsql_test 11.0 {
  DROP TABLE IF EXISTS t0;
  CREATE TABLE t0(c0 INTEGER UNIQUE);
  INSERT INTO t0 VALUES(0);
} {}

do_faultsim_test 11.1 -faults oom* -prep {
} -body {
  execsql {
    SELECT * FROM t0 WHERE 
      (0, t0.c0) IN (SELECT DENSE_RANK() OVER(), LAG(0) OVER() FROM t0);
  }
} -test {
  faultsim_test_result {0 {}}
}

do_faultsim_test 11.2 -faults oom* -prep {
} -body {
  execsql {
    VALUES(false),(current_date collate binary) 
    intersect 
    values(count() not like group_concat(cast(cast(0e00 as text) as integer) <= NULL || 0.4e-0 || 0x8 & true ) over () collate rtrim);
  }
} -test {
  faultsim_test_result {0 {}}
}

#-------------------------------------------------------------------------
reset_db
do_execsql_test 12.0 {
  CREATE TABLE t1(a, b, c);
} {}
do_faultsim_test 12 -faults oom* -prep {
} -body {
  execsql {
    WITH v(a, b, row_number) AS (
      SELECT a, b, row_number() OVER (PARTITION BY a ORDER BY b) FROM t1
    )
    SELECT * FROM v WHERE a=2
  }
} -test {
  faultsim_test_result {0 {}}
}

finish_test

# 2021 February 23
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the push-down optimization when
# WHERE constraints are pushed down into a sub-query that uses
# window functions.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix windowpushd

do_execsql_test 1.0 {
  CREATE TABLE t1(id INTEGER PRIMARY KEY, grp_id);
  CREATE INDEX i1 ON t1(grp_id);
  CREATE VIEW lll AS SELECT
    row_number() OVER (PARTITION BY grp_id), 
    grp_id, id 
  FROM t1
}

do_execsql_test 1.1 {
  INSERT INTO t1 VALUES
    (1, 2), (2, 3), (3, 3), (4, 1), (5, 1),
    (6, 1), (7, 1), (8, 1), (9, 3), (10, 3), 
    (11, 2), (12, 3), (13, 3), (14, 2), (15, 1),
    (16, 2), (17, 1), (18, 2), (19, 3), (20, 2)
}

do_execsql_test 1.2 {
  SELECT * FROM lll
} {
  1 1 4 2 1 5 3 1 6 4 1 7 5 1 8 6 1 15 7 1 17 
  1 2 1 2 2 11 3 2 14 4 2 16 5 2 18 6 2 20 
  1 3 2 2 3 3 3 3 9 4 3 10 5 3 12 6 3 13 7 3 19
}

do_execsql_test 1.3 {
  SELECT * FROM lll WHERE grp_id=2
} {
  1 2 1 2 2 11 3 2 14 4 2 16 5 2 18 6 2 20 
}

do_eqp_test 1.4 {
  SELECT * FROM lll WHERE grp_id=2
} {SEARCH TABLE t1 USING COVERING INDEX i1 (grp_id=?)}

#-------------------------------------------------------------------------
reset_db
do_execsql_test 2.0 {
  CREATE TABLE t1(a, b, c, d);
  INSERT INTO t1 VALUES('A', 'C', 1,  0.1);
  INSERT INTO t1 VALUES('A', 'D', 2,  0.2);
  INSERT INTO t1 VALUES('A', 'E', 3,  0.3);
  INSERT INTO t1 VALUES('A', 'C', 4,  0.4);
  INSERT INTO t1 VALUES('B', 'D', 5,  0.5);
  INSERT INTO t1 VALUES('B', 'E', 6,  0.6);
  INSERT INTO t1 VALUES('B', 'C', 7,  0.7);
  INSERT INTO t1 VALUES('B', 'D', 8,  0.8);
  INSERT INTO t1 VALUES('C', 'E', 9,  0.9);
  INSERT INTO t1 VALUES('C', 'C', 10, 1.0);
  INSERT INTO t1 VALUES('C', 'D', 11, 1.1);
  INSERT INTO t1 VALUES('C', 'E', 12, 1.2);

  CREATE INDEX i1 ON t1(a);
  CREATE INDEX i2 ON t1(b);

  CREATE VIEW v1 AS SELECT a, c, max(c) OVER (PARTITION BY a) FROM t1;

  CREATE VIEW v2 AS SELECT a, c, 
      max(c) OVER (PARTITION BY a),
      row_number() OVER ()
  FROM t1;

  CREATE VIEW v3 AS SELECT b, d, 
      max(d) OVER (PARTITION BY b),
      row_number() OVER (PARTITION BY b)
  FROM t1;

  CREATE TABLE t2(x, y, z);
  INSERT INTO t2 VALUES('W', 3, 1);
  INSERT INTO t2 VALUES('W', 2, 2);
  INSERT INTO t2 VALUES('X', 1, 4);
  INSERT INTO t2 VALUES('X', 5, 7);
  INSERT INTO t2 VALUES('Y', 1, 9);
  INSERT INTO t2 VALUES('Y', 4, 2);
  INSERT INTO t2 VALUES('Z', 3, 3);
  INSERT INTO t2 VALUES('Z', 3, 4);
}

foreach tn {0 1} {
  optimization_control db push-down $tn

  do_execsql_test 2.$tn.1.1 {
    SELECT * FROM v1;
  } {
    A 1 4   A 2 4   A 3 4   A 4 4
    B 5 8   B 6 8   B 7 8   B 8 8
    C 9 12  C 10 12 C 11 12 C 12 12
  }

  do_execsql_test 2.$tn.1.2 {
    SELECT * FROM v1 WHERE a IN ('A', 'B');
  } {
    A 1 4   A 2 4   A 3 4   A 4 4
    B 5 8   B 6 8   B 7 8   B 8 8
  }

  do_execsql_test 2.$tn.1.3 {
    SELECT * FROM v1 WHERE a IS 'C'
  } {
    C 9 12  C 10 12 C 11 12 C 12 12
  }

  if {$tn==1} {
    do_eqp_test 2.$tn.1.4 {
      SELECT * FROM v1 WHERE a IN ('A', 'B');
    } {USING INDEX i1 (a=?)}

    do_eqp_test 2.$tn.1.5 {
      SELECT * FROM v1 WHERE a = 'c' COLLATE nocase
    } {USING INDEX i1}
  }

  do_execsql_test 2.$tn.2.1 {
    SELECT * FROM v2;
  } {
    A 1 4 1    A 2 4 2     A 3 4 3      A 4 4 4
    B 5 8 5    B 6 8 6     B 7 8 7      B 8 8 8
    C 9 12 9   C 10 12 10  C 11 12 11   C 12 12 12
  }

  do_execsql_test 2.$tn.2.2 {
    SELECT * FROM v2 WHERE a = 'C';
  } {
    C 9 12 9   C 10 12 10  C 11 12 11   C 12 12 12
  }

  do_execsql_test 2.$tn.3.1 { SELECT * FROM v3; } { 
    C 0.1 1.0 1 C 0.4 1.0 2 C 0.7 1.0 3 C 1.0 1.0 4 
    D 0.2 1.1 1 D 0.5 1.1 2 D 0.8 1.1 3 D 1.1 1.1 4 
    E 0.3 1.2 1 E 0.6 1.2 2 E 0.9 1.2 3 E 1.2 1.2 4
  }

  do_execsql_test 2.$tn.3.2 { SELECT * FROM v3 WHERE b<'E' } { 
    C 0.1 1.0 1 C 0.4 1.0 2 C 0.7 1.0 3 C 1.0 1.0 4 
    D 0.2 1.1 1 D 0.5 1.1 2 D 0.8 1.1 3 D 1.1 1.1 4 
  }

  if {$tn==1} {
    do_eqp_test 2.$tn.3.3 {
      SELECT * FROM v3 WHERE b='E'
    } {SEARCH TABLE t1 USING INDEX i2 (b=?)}
    do_eqp_test 2.$tn.3.4 {
      SELECT * FROM v3 WHERE b>'C'
    } {SEARCH TABLE t1 USING INDEX i2 (b>?)}
  }

  do_execsql_test 2.$tn.3.5 { SELECT * FROM v3 WHERE d<0.55; } { 
    C 0.1 1.0 1 C 0.4 1.0 2
    D 0.2 1.1 1 D 0.5 1.1 2
    E 0.3 1.2 1
  }
  if {$tn==1} {
    do_eqp_test 2.$tn.3.6 {
      SELECT * FROM v3 WHERE d<0.55
    } {SCAN TABLE t1 USING INDEX i2}
  }

  do_execsql_test 2.$tn.4.1 {
    SELECT * FROM (
      SELECT x, sum(y) AS s, max(z) AS m 
      FROM t2 GROUP BY x
    )
  } {
    W 5 2
    X 6 7
    Y 5 9
    Z 6 4
  }

  do_execsql_test 2.$tn.4.1 {
    SELECT * FROM (
      SELECT x, sum(y) AS s, max(z) AS m,
        max( max(z) ) OVER (PARTITION BY sum(y) 
            ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
        )
      FROM t2 GROUP BY x
    )
  } {
    W 5 2   9
    Y 5 9   9
    X 6 7   7
    Z 6 4   7
  }

  do_execsql_test 2.$tn.4.2 {
    SELECT * FROM (
      SELECT x, sum(y) AS s, max(z) AS m,
        max( max(z) ) OVER (PARTITION BY sum(y) 
            ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
        )
      FROM t2 GROUP BY x
    ) WHERE s=6
  } {
    X 6 7   7
    Z 6 4   7
  }

  do_execsql_test 2.$tn.4.3 {
    SELECT * FROM (
      SELECT x, sum(y) AS s, max(z) AS m,
        max( max(z) ) OVER (PARTITION BY sum(y) 
            ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
        )
      FROM t2 GROUP BY x
    ) WHERE s<6
  } {
    W 5 2   9
    Y 5 9   9
  }

}




finish_test