SQLite

Check-in [9ce9e43af3]
Login

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

Overview
Comment:Handle compound-select statements originating from VALUES clauses as a special case that does not use recursion.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | many-VALUEs
Files: files | file ages | folders
SHA1: 9ce9e43af38e6bc362734463d4bfc40ff0c98f8f
User & Date: drh 2015-01-05 19:16:42.892
Context
2015-01-05
20:04
Avoid O(N*N) behavior with very long lists of VALUES. (Closed-Leaf check-in: ee30fb3521 user: drh tags: many-VALUEs)
19:16
Handle compound-select statements originating from VALUES clauses as a special case that does not use recursion. (check-in: 9ce9e43af3 user: drh tags: many-VALUEs)
16:27
Towards getting INSERT statements to except many VALUE terms (more than the limit imposed by SQLITE_LIMIT_COMPOUND_SELECT). This check-in segfaults on a stack overflow. And it is slow. (check-in: c9d65f739a user: drh tags: many-VALUEs)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/parse.y.
411
412
413
414
415
416
417

418
419
420
421

422

423

424
425
426
427
428
429
430
431
432

select(A) ::= with(W) selectnowith(X). {
  Select *p = X, *pNext, *pLoop;
  if( p ){
    int cnt = 0, mxSelect;
    p->pWith = W;
    if( p->pPrior ){

      pNext = 0;
      for(pLoop=p; pLoop; pNext=pLoop, pLoop=pLoop->pPrior, cnt++){
        pLoop->pNext = pNext;
        pLoop->selFlags |= SF_Compound;

      }

      if( (p->selFlags & SF_Values)==0

       && (mxSelect = pParse->db->aLimit[SQLITE_LIMIT_COMPOUND_SELECT])>0
       && cnt>mxSelect
      ){
        sqlite3ErrorMsg(pParse, "too many terms in compound SELECT");
      }
    }
  }else{
    sqlite3WithDelete(pParse->db, W);
  }







>




>

>
|
>
|
|







411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436

select(A) ::= with(W) selectnowith(X). {
  Select *p = X, *pNext, *pLoop;
  if( p ){
    int cnt = 0, mxSelect;
    p->pWith = W;
    if( p->pPrior ){
      u16 allValues = SF_Values;
      pNext = 0;
      for(pLoop=p; pLoop; pNext=pLoop, pLoop=pLoop->pPrior, cnt++){
        pLoop->pNext = pNext;
        pLoop->selFlags |= SF_Compound;
        allValues &= pLoop->selFlags;
      }
      if( allValues ){
        p->selFlags |= SF_AllValues;
      }else if(
        (mxSelect = pParse->db->aLimit[SQLITE_LIMIT_COMPOUND_SELECT])>0
        && cnt>mxSelect
      ){
        sqlite3ErrorMsg(pParse, "too many terms in compound SELECT");
      }
    }
  }else{
    sqlite3WithDelete(pParse->db, W);
  }
Changes to src/select.c.
2072
2073
2074
2075
2076
2077
2078




























































2079
2080
2081
2082
2083
2084
2085
/* Forward references */
static int multiSelectOrderBy(
  Parse *pParse,        /* Parsing context */
  Select *p,            /* The right-most of SELECTs to be coded */
  SelectDest *pDest     /* What to do with query results */
);






























































/*
** This routine is called to process a compound query form from
** two or more separate queries using UNION, UNION ALL, EXCEPT, or
** INTERSECT
**
** "p" points to the right-most of the two queries.  the query on the







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







2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
/* Forward references */
static int multiSelectOrderBy(
  Parse *pParse,        /* Parsing context */
  Select *p,            /* The right-most of SELECTs to be coded */
  SelectDest *pDest     /* What to do with query results */
);

/*
** Error message for when two or more terms of a compound select have different
** size result sets.
*/
static void selectWrongNumTermsError(Parse *pParse, Select *p){
  if( p->selFlags & SF_Values ){
    sqlite3ErrorMsg(pParse, "all VALUES must have the same number of terms");
  }else{
    sqlite3ErrorMsg(pParse, "SELECTs to the left and right of %s"
      " do not have the same number of result columns", selectOpName(p->op));
  }
}

/*
** Handle the special case of a compound-select that originates from a
** VALUES clause.  By handling this as a special case, we avoid deep
** recursion, and thus do not need to enforce the SQLITE_LIMIT_COMPOUND_SELECT
** on a VALUES clause.
**
** Because the Select object originates from a VALUES clause:
**   (1) It has no LIMIT or OFFSET
**   (2) All terms are UNION ALL
**   (3) There is no ORDER BY clause
*/
static int multiSelectValues(
  Parse *pParse,        /* Parsing context */
  Select *p,            /* The right-most of SELECTs to be coded */
  SelectDest *pDest     /* What to do with query results */
){
  Select *pPrior;
  int nExpr = p->pEList->nExpr;
  int nRow = 1;
  int rc = 0;
  assert( p->pNext==0 );
  assert( p->selFlags & SF_AllValues );
  do{
    assert( p->selFlags & SF_Values );
    assert( p->op==TK_ALL || (p->op==TK_SELECT && p->pPrior==0) );
    assert( p->pLimit==0 );
    assert( p->pOffset==0 );
    if( p->pEList->nExpr!=nExpr ){
      selectWrongNumTermsError(pParse, p);
      return 1;
    }
    if( p->pPrior==0 ) break;
    assert( p->pPrior->pNext==p );
    p = p->pPrior;
    nRow++;
  }while(1);
  while( p ){
    pPrior = p->pPrior;
    p->pPrior = 0;
    rc = sqlite3Select(pParse, p, pDest);
    p->pPrior = pPrior;
    if( rc ) break;
    p->nSelectRow = nRow;
    p = p->pNext;
  }
  return rc;
}

/*
** This routine is called to process a compound query form from
** two or more separate queries using UNION, UNION ALL, EXCEPT, or
** INTERSECT
**
** "p" points to the right-most of the two queries.  the query on the
2152
2153
2154
2155
2156
2157
2158







2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
  */
  if( dest.eDest==SRT_EphemTab ){
    assert( p->pEList );
    sqlite3VdbeAddOp2(v, OP_OpenEphemeral, dest.iSDParm, p->pEList->nExpr);
    sqlite3VdbeChangeP5(v, BTREE_UNORDERED);
    dest.eDest = SRT_Table;
  }








  /* Make sure all SELECTs in the statement have the same number of elements
  ** in their result sets.
  */
  assert( p->pEList && pPrior->pEList );
  if( p->pEList->nExpr!=pPrior->pEList->nExpr ){
    if( p->selFlags & SF_Values ){
      sqlite3ErrorMsg(pParse, "all VALUES must have the same number of terms");
    }else{
      sqlite3ErrorMsg(pParse, "SELECTs to the left and right of %s"
        " do not have the same number of result columns", selectOpName(p->op));
    }
    rc = 1;
    goto multi_select_end;
  }

#ifndef SQLITE_OMIT_CTE
  if( p->selFlags & SF_Recursive ){
    generateWithRecursiveQuery(pParse, p, &dest);







>
>
>
>
>
>
>






<
<
<
|
<
<







2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231



2232


2233
2234
2235
2236
2237
2238
2239
  */
  if( dest.eDest==SRT_EphemTab ){
    assert( p->pEList );
    sqlite3VdbeAddOp2(v, OP_OpenEphemeral, dest.iSDParm, p->pEList->nExpr);
    sqlite3VdbeChangeP5(v, BTREE_UNORDERED);
    dest.eDest = SRT_Table;
  }

  /* Special handling for a compound-select that originates as a VALUES clause.
  */
  if( p->selFlags & SF_AllValues ){
    rc = multiSelectValues(pParse, p, &dest);
    goto multi_select_end;
  }

  /* Make sure all SELECTs in the statement have the same number of elements
  ** in their result sets.
  */
  assert( p->pEList && pPrior->pEList );
  if( p->pEList->nExpr!=pPrior->pEList->nExpr ){



    selectWrongNumTermsError(pParse, p);


    rc = 1;
    goto multi_select_end;
  }

#ifndef SQLITE_OMIT_CTE
  if( p->selFlags & SF_Recursive ){
    generateWithRecursiveQuery(pParse, p, &dest);
Changes to src/sqliteInt.h.
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
#define SF_Resolved        0x0002  /* Identifiers have been resolved */
#define SF_Aggregate       0x0004  /* Contains aggregate functions */
#define SF_UsesEphemeral   0x0008  /* Uses the OpenEphemeral opcode */
#define SF_Expanded        0x0010  /* sqlite3SelectExpand() called on this */
#define SF_HasTypeInfo     0x0020  /* FROM subqueries have Table metadata */
#define SF_Compound        0x0040  /* Part of a compound query */
#define SF_Values          0x0080  /* Synthesized from VALUES clause */
                    /*     0x0100  NOT USED */
#define SF_NestedFrom      0x0200  /* Part of a parenthesized FROM clause */
#define SF_MaybeConvert    0x0400  /* Need convertCompoundSelectToSubquery() */
#define SF_Recursive       0x0800  /* The recursive part of a recursive CTE */
#define SF_MinMaxAgg       0x1000  /* Aggregate containing min() or max() */


/*







|







2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
#define SF_Resolved        0x0002  /* Identifiers have been resolved */
#define SF_Aggregate       0x0004  /* Contains aggregate functions */
#define SF_UsesEphemeral   0x0008  /* Uses the OpenEphemeral opcode */
#define SF_Expanded        0x0010  /* sqlite3SelectExpand() called on this */
#define SF_HasTypeInfo     0x0020  /* FROM subqueries have Table metadata */
#define SF_Compound        0x0040  /* Part of a compound query */
#define SF_Values          0x0080  /* Synthesized from VALUES clause */
#define SF_AllValues       0x0100  /* All terms of compound are VALUES */
#define SF_NestedFrom      0x0200  /* Part of a parenthesized FROM clause */
#define SF_MaybeConvert    0x0400  /* Need convertCompoundSelectToSubquery() */
#define SF_Recursive       0x0800  /* The recursive part of a recursive CTE */
#define SF_MinMaxAgg       0x1000  /* Aggregate containing min() or max() */


/*