SQLite

Changes On Branch rtree-update-optimization
Login

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

Changes In Branch rtree-update-optimization Excluding Merge-Ins

This is equivalent to a diff from b816023c to 6f7cfeff

2018-05-26
13:55
Add a single sentence of documentation about the virtual table scan flags. No changes to code. (check-in: 27b4fa5d user: drh tags: trunk)
2018-05-25
19:22
Forward port the geopoly extension functions into the r-tree extension, with the idea of creating a new spatial index based on simply polygons. (check-in: 0593aac8 user: drh tags: rtree-geopoly)
14:39
This is an untested proof-of-concept for enhancements to RTree that attempt to use sqlite3_value_nochange() to reduce the amount of work associated with UPDATE operations in cases where either the coordinates or the auxiliary data is unchanged. (Leaf check-in: 6f7cfeff user: drh tags: rtree-update-optimization)
09:36
Merge latest trunk changes into this branch. (check-in: 62325198 user: dan tags: exp-window-functions)
03:46
Add SQLITE_LOCKED_VTAB and SQLITE_CORRUPT_SEQUENCE to sqlite3ErrName(). Also, use SQLITE_CORRUPT_BKPT in one more place. (Leaf check-in: eac8888d user: mistachkin tags: errCodes)
2018-05-24
23:51
When doing a one-pass UPDATE or DELETE on virtual tables, close the cursor prior to running VUpdate. This allows one-pass to work on virtual tables that do not allow concurrent reads and writes. Enhance rtree to take advantage of this new capability. (check-in: b816023c user: drh tags: trunk)
22:42
New test case for reading and writing the same rtree concurrently. (check-in: 3ba08e53 user: drh tags: trunk)

Changes to ext/rtree/rtree.c.

3072
3073
3074
3075
3076
3077
3078
3079
3080



3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091





























3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
  sqlite3_vtab *pVtab, 
  int nData, 
  sqlite3_value **aData, 
  sqlite_int64 *pRowid
){
  Rtree *pRtree = (Rtree *)pVtab;
  int rc = SQLITE_OK;
  RtreeCell cell;                 /* New cell to insert if nData>1 */
  int bHaveRowid = 0;             /* Set to 1 after new rowid is determined */




  if( pRtree->nNodeRef ){
    /* Unable to write to the btree while another cursor is reading from it,
    ** since the write might do a rebalance which would disrupt the read
    ** cursor. */
    return SQLITE_LOCKED_VTAB;
  }
  rtreeReference(pRtree);
  assert(nData>=1);

  cell.iRowid = 0;  /* Used only to suppress a compiler warning */






























  /* Constraint handling. A write operation on an r-tree table may return
  ** SQLITE_CONSTRAINT for two reasons:
  **
  **   1. A duplicate rowid value, or
  **   2. The supplied data violates the "x2>=x1" constraint.
  **
  ** In the first case, if the conflict-handling mode is REPLACE, then
  ** the conflicting row can be removed before proceeding. In the second
  ** case, SQLITE_CONSTRAINT must be returned regardless of the
  ** conflict-handling mode specified by the user.
  */
  if( nData>1 ){
    int ii;
    int nn = nData - 4;

    if( nn > pRtree->nDim2 ) nn = pRtree->nDim2;
    /* Populate the cell.aCoord[] array. The first coordinate is aData[3].
    **
    ** NB: nData can only be less than nDim*2+3 if the rtree is mis-declared
    ** with "column" that are interpreted as table constraints.
    ** Example:  CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5));
    ** This problem was discovered after years of use, so we silently ignore
    ** these kinds of misdeclared tables to avoid breaking any legacy.
    */

#ifndef SQLITE_RTREE_INT_ONLY
    if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
      for(ii=0; ii<nn; ii+=2){
        cell.aCoord[ii].f = rtreeValueDown(aData[ii+3]);
        cell.aCoord[ii+1].f = rtreeValueUp(aData[ii+4]);
        if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
          rc = rtreeConstraintError(pRtree, ii+1);
          goto constraint;
        }
      }
    }else
#endif
    {
      for(ii=0; ii<nn; ii+=2){
        cell.aCoord[ii].i = sqlite3_value_int(aData[ii+3]);
        cell.aCoord[ii+1].i = sqlite3_value_int(aData[ii+4]);
        if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){
          rc = rtreeConstraintError(pRtree, ii+1);
          goto constraint;
        }
      }







|
|
>
>
>











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












<
<
<
|
<
<
<
<
<
<
<
<
<
<


|










|







3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135



3136










3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
  sqlite3_vtab *pVtab, 
  int nData, 
  sqlite3_value **aData, 
  sqlite_int64 *pRowid
){
  Rtree *pRtree = (Rtree *)pVtab;
  int rc = SQLITE_OK;
  RtreeCell cell;              /* New cell to insert if nData>1 */
  int bHaveRowid = 0;          /* Set to 1 after new rowid is determined */
  int bRtreeInsert = 0;        /* True if rtree data is to be inserted */
  int nCoord;                  /* Number of coordinate columns */
  int ii;                      /* Loop counter */

  if( pRtree->nNodeRef ){
    /* Unable to write to the btree while another cursor is reading from it,
    ** since the write might do a rebalance which would disrupt the read
    ** cursor. */
    return SQLITE_LOCKED_VTAB;
  }
  rtreeReference(pRtree);
  assert(nData>=1);

  cell.iRowid = 0;  /* Used only to suppress a compiler warning */

  /* Set bRtreeInsert if this is an INSERT statement, or if it is an
  ** UPDATE statement that changes the rowid or one of the coordinates.
  ** Leave bRtreeInsert at zero if this is a DELETE or if this is an
  ** UPDATE that only changes auxiliary columns.
  */
  if( nData>1 ){
    nCoord = pRtree->nDim2;

    /* NB: nData can only be less than nDim2+3 if the rtree is mis-declared
    ** with "column" that are interpreted as table constraints.
    ** Example:  CREATE VIRTUAL TABLE bad USING rtree(x,y,CHECK(y>5));
    ** This problem was discovered after years of use, so we silently ignore
    ** these kinds of misdeclared tables to avoid breaking any legacy.
    */
    if( nCoord > nData-3 ) nCoord = nData - 3;

    if( sqlite3_value_type(aData[0])==SQLITE_NULL ){
      bRtreeInsert = 1;   /* This is an INSERT statement */
    }else{
      /* This is an UPDATE statement.  Check to see if the rowid (aData[2])
      ** or any coordinate column (aData[3] through aData[nCoord+2])
      ** has changed. */
      for(ii=nCoord+2; ii>=2; ii--){
        if( !sqlite3_value_nochange(aData[ii]) ) break;
      }
      bRtreeInsert = ii>=2;
    }
  }

  /* Constraint handling. A write operation on an r-tree table may return
  ** SQLITE_CONSTRAINT for two reasons:
  **
  **   1. A duplicate rowid value, or
  **   2. The supplied data violates the "x2>=x1" constraint.
  **
  ** In the first case, if the conflict-handling mode is REPLACE, then
  ** the conflicting row can be removed before proceeding. In the second
  ** case, SQLITE_CONSTRAINT must be returned regardless of the
  ** conflict-handling mode specified by the user.
  */



  if( bRtreeInsert ){










#ifndef SQLITE_RTREE_INT_ONLY
    if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
      for(ii=0; ii<nCoord; ii+=2){
        cell.aCoord[ii].f = rtreeValueDown(aData[ii+3]);
        cell.aCoord[ii+1].f = rtreeValueUp(aData[ii+4]);
        if( cell.aCoord[ii].f>cell.aCoord[ii+1].f ){
          rc = rtreeConstraintError(pRtree, ii+1);
          goto constraint;
        }
      }
    }else
#endif
    {
      for(ii=0; ii<nCoord; ii+=2){
        cell.aCoord[ii].i = sqlite3_value_int(aData[ii+3]);
        cell.aCoord[ii+1].i = sqlite3_value_int(aData[ii+4]);
        if( cell.aCoord[ii].i>cell.aCoord[ii+1].i ){
          rc = rtreeConstraintError(pRtree, ii+1);
          goto constraint;
        }
      }
3162
3163
3164
3165
3166
3167
3168
3169


3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183

3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198



3199














3200
3201

3202



3203
3204
3205
3206
3207
3208
3209
    }
  }

  /* If aData[0] is not an SQL NULL value, it is the rowid of a
  ** record to delete from the r-tree table. The following block does
  ** just that.
  */
  if( sqlite3_value_type(aData[0])!=SQLITE_NULL ){


    rc = rtreeDeleteRowid(pRtree, sqlite3_value_int64(aData[0]));
  }

  /* If the aData[] array contains more than one element, elements
  ** (aData[2]..aData[argc-1]) contain a new record to insert into
  ** the r-tree structure.
  */
  if( rc==SQLITE_OK && nData>1 ){
    /* Insert the new record into the r-tree */
    RtreeNode *pLeaf = 0;

    /* Figure out the rowid of the new row. */
    if( bHaveRowid==0 ){
      rc = newRowid(pRtree, &cell.iRowid);

    }
    *pRowid = cell.iRowid;

    if( rc==SQLITE_OK ){
      rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
    }
    if( rc==SQLITE_OK ){
      int rc2;
      pRtree->iReinsertHeight = -1;
      rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0);
      rc2 = nodeRelease(pRtree, pLeaf);
      if( rc==SQLITE_OK ){
        rc = rc2;
      }
    }



    if( pRtree->nAux ){














      sqlite3_stmt *pUp = pRtree->pWriteAux;
      int jj;

      sqlite3_bind_int64(pUp, 1, *pRowid);



      for(jj=0; jj<pRtree->nAux; jj++){
        sqlite3_bind_value(pUp, jj+2, aData[pRtree->nDim2+3+jj]);
      }
      sqlite3_step(pUp);
      rc = sqlite3_reset(pUp);
    }
  }







|
>
>







|






>















>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>


>
|
>
>
>







3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
    }
  }

  /* If aData[0] is not an SQL NULL value, it is the rowid of a
  ** record to delete from the r-tree table. The following block does
  ** just that.
  */
  if( sqlite3_value_type(aData[0])!=SQLITE_NULL
   && (bRtreeInsert || nData==1)
  ){
    rc = rtreeDeleteRowid(pRtree, sqlite3_value_int64(aData[0]));
  }

  /* If the aData[] array contains more than one element, elements
  ** (aData[2]..aData[argc-1]) contain a new record to insert into
  ** the r-tree structure.
  */
  if( rc==SQLITE_OK && bRtreeInsert ){
    /* Insert the new record into the r-tree */
    RtreeNode *pLeaf = 0;

    /* Figure out the rowid of the new row. */
    if( bHaveRowid==0 ){
      rc = newRowid(pRtree, &cell.iRowid);
      bHaveRowid = 1;
    }
    *pRowid = cell.iRowid;

    if( rc==SQLITE_OK ){
      rc = ChooseLeaf(pRtree, &cell, 0, &pLeaf);
    }
    if( rc==SQLITE_OK ){
      int rc2;
      pRtree->iReinsertHeight = -1;
      rc = rtreeInsertCell(pRtree, pLeaf, &cell, 0);
      rc2 = nodeRelease(pRtree, pLeaf);
      if( rc==SQLITE_OK ){
        rc = rc2;
      }
    }
  }

  /* Handle INSERT and UPDATE of auxiliary column data */
  if( rc==SQLITE_OK && nData>1 && pRtree->nAux ){
    if( sqlite3_value_type(aData[0])==SQLITE_NULL ){
      /* This is an INSERT statement.  Check to see if any
      ** auxiliary column is non-NULL and hence needs to be set */
      for(ii=pRtree->nAux+pRtree->nDim2+3; ii<nData; ii++){
        if( sqlite3_value_type(aData[ii])!=SQLITE_NULL ) break;
      }
    }else{
      /* This is an UPDATE statement.  Check to see if any
      ** auxiliary column value has changed. */
      for(ii=pRtree->nAux+pRtree->nDim2+3; ii<nData; ii++){
        if( sqlite3_value_nochange(aData[ii])==0 ) break;
      }
    }
    if( ii<nData ){
      sqlite3_stmt *pUp = pRtree->pWriteAux;
      int jj;
      if( bHaveRowid ){
        sqlite3_bind_int64(pUp, 1, cell.iRowid);
      }else{
        sqlite3_bind_int64(pUp, 1, sqlite3_value_int64(aData[1]));
      }
      for(jj=0; jj<pRtree->nAux; jj++){
        sqlite3_bind_value(pUp, jj+2, aData[pRtree->nDim2+3+jj]);
      }
      sqlite3_step(pUp);
      rc = sqlite3_reset(pUp);
    }
  }