/ Check-in [7b70b419]
Login

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

Overview
Comment:Replace variable Index.avgEq (average number of rows in keys for which there is no sample in sqlite_stat4) with vector Index.aAvgEq.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | sqlite_stat4
Files: files | file ages | folders
SHA1:7b70b419c43b2c3b2daf11d833a1d60245bfaef5
User & Date: dan 2013-08-07 19:46:15
Context
2013-08-08
11:48
Fix a bug in using stat4 data to estimate the number of rows selected by a range constraint. check-in: f783938e user: dan tags: sqlite_stat4
2013-08-07
19:46
Replace variable Index.avgEq (average number of rows in keys for which there is no sample in sqlite_stat4) with vector Index.aAvgEq. check-in: 7b70b419 user: dan tags: sqlite_stat4
18:42
Merge latest trunk changes with this branch. check-in: 08f74c45 user: dan tags: sqlite_stat4
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/analyze.c.

323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
....
1172
1173
1174
1175
1176
1177
1178

1179
1180
1181
1182
1183
1184
1185
1186

1187
1188
1189
1190
1191
1192
1193
....
1225
1226
1227
1228
1229
1230
1231



1232

1233
1234
1235
1236



1237
1238
1239
1240
1241
1242
1243
static void stat4Push(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  Stat4Accum *p = (Stat4Accum*)sqlite3_value_blob(argv[0]);
  i64 rowid = sqlite3_value_int64(argv[1]);
  i64 nSumEq = 0;                 /* Sum of all nEq parameters */
  struct Stat4Sample *pSample;
  u32 h;
  int iMin = p->iMin;
  int i;
  u8 isPSample = 0;
  u8 doInsert = 0;

................................................................................
    nSample = sqlite3_column_int(pStmt, 1);
    pIdx = sqlite3FindIndex(db, zIndex, zDb);
    if( pIdx==0 ) continue;
    assert( pIdx->nSample==0 );
    pIdx->nSample = nSample;
    nByte = sizeof(IndexSample) * nSample;
    nByte += sizeof(tRowcnt) * pIdx->nColumn * 3 * nSample;


    pIdx->aSample = sqlite3DbMallocZero(db, nByte);
    pIdx->avgEq = pIdx->aiRowEst[1];
    if( pIdx->aSample==0 ){
      sqlite3_finalize(pStmt);
      return SQLITE_NOMEM;
    }
    pSpace = (tRowcnt*)&pIdx->aSample[nSample];

    for(i=0; i<pIdx->nSample; i++){
      pIdx->aSample[i].anEq = pSpace; pSpace += pIdx->nColumn;
      pIdx->aSample[i].anLt = pSpace; pSpace += pIdx->nColumn;
      pIdx->aSample[i].anDLt = pSpace; pSpace += pIdx->nColumn;
    }
    assert( ((u8*)pSpace)-nByte==(u8*)(pIdx->aSample) );
  }
................................................................................

    nCol = pIdx->nColumn;
    decodeIntArray((char*)sqlite3_column_text(pStmt,1), nCol, pSample->anEq, 0);
    decodeIntArray((char*)sqlite3_column_text(pStmt,2), nCol, pSample->anLt, 0);
    decodeIntArray((char*)sqlite3_column_text(pStmt,3), nCol, pSample->anDLt,0);

    if( idx==pIdx->nSample-1 ){



      if( pSample->anDLt[0]>0 ){

        for(i=0, sumEq=0; i<=idx-1; i++) sumEq += pIdx->aSample[i].anEq[0];
        pIdx->avgEq = (pSample->anLt[0] - sumEq)/pSample->anDLt[0];
      }
      if( pIdx->avgEq<=0 ) pIdx->avgEq = 1;



    }

    pSample->n = sqlite3_column_bytes(pStmt, 4);
    pSample->p = sqlite3DbMallocZero(db, pSample->n);
    if( pSample->p==0 ){
      sqlite3_finalize(pStmt);
      return SQLITE_NOMEM;







<







 







>


<





>







 







>
>
>
|
>
|
|
|
<
>
>
>







323
324
325
326
327
328
329

330
331
332
333
334
335
336
....
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180

1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
....
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239

1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
static void stat4Push(
  sqlite3_context *context,
  int argc,
  sqlite3_value **argv
){
  Stat4Accum *p = (Stat4Accum*)sqlite3_value_blob(argv[0]);
  i64 rowid = sqlite3_value_int64(argv[1]);

  struct Stat4Sample *pSample;
  u32 h;
  int iMin = p->iMin;
  int i;
  u8 isPSample = 0;
  u8 doInsert = 0;

................................................................................
    nSample = sqlite3_column_int(pStmt, 1);
    pIdx = sqlite3FindIndex(db, zIndex, zDb);
    if( pIdx==0 ) continue;
    assert( pIdx->nSample==0 );
    pIdx->nSample = nSample;
    nByte = sizeof(IndexSample) * nSample;
    nByte += sizeof(tRowcnt) * pIdx->nColumn * 3 * nSample;
    nByte += pIdx->nColumn * sizeof(tRowcnt);    /* Space for Index.aAvgEq[] */

    pIdx->aSample = sqlite3DbMallocZero(db, nByte);

    if( pIdx->aSample==0 ){
      sqlite3_finalize(pStmt);
      return SQLITE_NOMEM;
    }
    pSpace = (tRowcnt*)&pIdx->aSample[nSample];
    pIdx->aAvgEq = pSpace; pSpace += pIdx->nColumn;
    for(i=0; i<pIdx->nSample; i++){
      pIdx->aSample[i].anEq = pSpace; pSpace += pIdx->nColumn;
      pIdx->aSample[i].anLt = pSpace; pSpace += pIdx->nColumn;
      pIdx->aSample[i].anDLt = pSpace; pSpace += pIdx->nColumn;
    }
    assert( ((u8*)pSpace)-nByte==(u8*)(pIdx->aSample) );
  }
................................................................................

    nCol = pIdx->nColumn;
    decodeIntArray((char*)sqlite3_column_text(pStmt,1), nCol, pSample->anEq, 0);
    decodeIntArray((char*)sqlite3_column_text(pStmt,2), nCol, pSample->anLt, 0);
    decodeIntArray((char*)sqlite3_column_text(pStmt,3), nCol, pSample->anDLt,0);

    if( idx==pIdx->nSample-1 ){
      int iCol;
      for(iCol=0; iCol<pIdx->nColumn; iCol++){
        tRowcnt avgEq = 0;
        tRowcnt nDLt = pSample->anDLt[iCol];
        if( nDLt>idx ){
          for(i=0, sumEq=0; i<idx; i++) sumEq += pIdx->aSample[i].anEq[iCol];
          avgEq = (pSample->anLt[iCol] - sumEq)/(nDLt - idx);
        }

        if( avgEq==0 ) avgEq = 1;
        pIdx->aAvgEq[iCol] = avgEq;
      }
    }

    pSample->n = sqlite3_column_bytes(pStmt, 4);
    pSample->p = sqlite3DbMallocZero(db, pSample->n);
    if( pSample->p==0 ){
      sqlite3_finalize(pStmt);
      return SQLITE_NOMEM;

Changes to src/sqliteInt.h.

1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
  u16 nColumn;             /* Number of columns in table used by this index */
  u8 onError;              /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
  unsigned autoIndex:2;    /* 1==UNIQUE, 2==PRIMARY KEY, 0==CREATE INDEX */
  unsigned bUnordered:1;   /* Use this index for == or IN queries only */
  unsigned uniqNotNull:1;  /* True if UNIQUE and NOT NULL for all columns */
#ifdef SQLITE_ENABLE_STAT4
  int nSample;             /* Number of elements in aSample[] */
  tRowcnt avgEq;           /* Average nEq value for key values not in aSample */
  IndexSample *aSample;    /* Samples of the left-most key */
#endif
};

/*
** Each sample stored in the sqlite_stat3 table is represented in memory 
** using a structure of this type.  See documentation at the top of the







|







1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
  u16 nColumn;             /* Number of columns in table used by this index */
  u8 onError;              /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
  unsigned autoIndex:2;    /* 1==UNIQUE, 2==PRIMARY KEY, 0==CREATE INDEX */
  unsigned bUnordered:1;   /* Use this index for == or IN queries only */
  unsigned uniqNotNull:1;  /* True if UNIQUE and NOT NULL for all columns */
#ifdef SQLITE_ENABLE_STAT4
  int nSample;             /* Number of elements in aSample[] */
  tRowcnt *aAvgEq;         /* Average nEq values for keys not in aSample */
  IndexSample *aSample;    /* Samples of the left-most key */
#endif
};

/*
** Each sample stored in the sqlite_stat3 table is represented in memory 
** using a structure of this type.  See documentation at the top of the

Changes to src/where.c.

2414
2415
2416
2417
2418
2419
2420

2421

2422
2423
2424
2425
2426
2427
2428
....
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
....
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
....
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
  UnpackedRecord *pRec,       /* Vector of values to consider */
  int roundUp,                /* Round up if true.  Round down if false */
  tRowcnt *aStat              /* OUT: stats written here */
){
  IndexSample *aSample = pIdx->aSample;
  int i;
  int isEq = 0;



  for(i=0; i<pIdx->nSample; i++){
    int res = sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec);
    if( res>=0 ){
      isEq = (res==0);
      break;
    }
  }
................................................................................

  /* At this point, aSample[i] is the first sample that is greater than
  ** or equal to pVal.  Or if i==pIdx->nSample, then all samples are less
  ** than pVal.  If aSample[i]==pVal, then isEq==1.
  */
  if( isEq ){
    assert( i<pIdx->nSample );
    aStat[0] = aSample[i].anLt[0];
    aStat[1] = aSample[i].anEq[0];
  }else{
    tRowcnt iLower, iUpper, iGap;
    if( i==0 ){
      iLower = 0;
      iUpper = aSample[0].anLt[0];
    }else{
      iUpper = i>=pIdx->nSample ? pIdx->aiRowEst[0] : aSample[i].anLt[0];
      iLower = aSample[i-1].anEq[0] + aSample[i-1].anLt[0];
    }
    aStat[1] = pIdx->avgEq;
    if( iLower>=iUpper ){
      iGap = 0;
    }else{
      iGap = iUpper - iLower;
    }
    if( roundUp ){
      iGap = (iGap*2)/3;
................................................................................
  }

  if( nEq>p->nColumn ){
    *pnRow = 1;
    return SQLITE_OK;
  }

  aff = p->pTable->aCol[p->aiColumn[0]].affinity;
  rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq-1, &bOk);
  pBuilder->pRec = pRec;
  if( rc!=SQLITE_OK ) return rc;
  if( bOk==0 ) return SQLITE_NOTFOUND;
  pBuilder->nRecValid = nEq;

  rc = whereKeyStats(pParse, p, pRec, 0, a);
................................................................................
  if( rc==SQLITE_OK ){
    WHERETRACE(0x100,("equality scan regions: %d\n", (int)a[1]));
    *pnRow = a[1];
    if( pBuilder->nMaxRowcnt && *pnRow>pBuilder->nMaxRowcnt ){
      *pnRow = pBuilder->nMaxRowcnt;
    }
  }

  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT4) */

#ifdef SQLITE_ENABLE_STAT4
/*
** Estimate the number of rows that will be returned based on







>

>







 







|
|




|

|
|

|







 







|







 







|







2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
....
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
....
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
....
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
  UnpackedRecord *pRec,       /* Vector of values to consider */
  int roundUp,                /* Round up if true.  Round down if false */
  tRowcnt *aStat              /* OUT: stats written here */
){
  IndexSample *aSample = pIdx->aSample;
  int i;
  int isEq = 0;
  int iCol = pRec->nField-1;

  assert( pRec->nField>0 && iCol<pIdx->nColumn );
  for(i=0; i<pIdx->nSample; i++){
    int res = sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec);
    if( res>=0 ){
      isEq = (res==0);
      break;
    }
  }
................................................................................

  /* At this point, aSample[i] is the first sample that is greater than
  ** or equal to pVal.  Or if i==pIdx->nSample, then all samples are less
  ** than pVal.  If aSample[i]==pVal, then isEq==1.
  */
  if( isEq ){
    assert( i<pIdx->nSample );
    aStat[0] = aSample[i].anLt[iCol];
    aStat[1] = aSample[i].anEq[iCol];
  }else{
    tRowcnt iLower, iUpper, iGap;
    if( i==0 ){
      iLower = 0;
      iUpper = aSample[0].anLt[iCol];
    }else{
      iUpper = i>=pIdx->nSample ? pIdx->aiRowEst[0] : aSample[i].anLt[iCol];
      iLower = aSample[i-1].anEq[iCol] + aSample[i-1].anLt[iCol];
    }
    aStat[1] = pIdx->aAvgEq[iCol];
    if( iLower>=iUpper ){
      iGap = 0;
    }else{
      iGap = iUpper - iLower;
    }
    if( roundUp ){
      iGap = (iGap*2)/3;
................................................................................
  }

  if( nEq>p->nColumn ){
    *pnRow = 1;
    return SQLITE_OK;
  }

  aff = p->pTable->aCol[p->aiColumn[nEq-1]].affinity;
  rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq-1, &bOk);
  pBuilder->pRec = pRec;
  if( rc!=SQLITE_OK ) return rc;
  if( bOk==0 ) return SQLITE_NOTFOUND;
  pBuilder->nRecValid = nEq;

  rc = whereKeyStats(pParse, p, pRec, 0, a);
................................................................................
  if( rc==SQLITE_OK ){
    WHERETRACE(0x100,("equality scan regions: %d\n", (int)a[1]));
    *pnRow = a[1];
    if( pBuilder->nMaxRowcnt && *pnRow>pBuilder->nMaxRowcnt ){
      *pnRow = pBuilder->nMaxRowcnt;
    }
  }
  
  return rc;
}
#endif /* defined(SQLITE_ENABLE_STAT4) */

#ifdef SQLITE_ENABLE_STAT4
/*
** Estimate the number of rows that will be returned based on