/ Check-in [301bbee4]
Login

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

Overview
Comment:Bug fixes in the ORDER BY optimizer.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | qp-enhancements
Files: files | file ages | folders
SHA1:301bbee4045aa169e29fb4fb75743b71eb4760a1
User & Date: drh 2012-10-08 19:41:38
Context
2012-10-08
20:27
Further tweaks to the ORDER BY optimizer, to fix a bug and to get the optimizer to recognize some additional cases. check-in: bcb4f262 user: drh tags: qp-enhancements
19:41
Bug fixes in the ORDER BY optimizer. check-in: 301bbee4 user: drh tags: qp-enhancements
18:23
Continued refactoring of the ORDER BY optimization logic. This check-in is close to working, but it still has issues. A few test cases fail. check-in: adbdc663 user: drh tags: qp-enhancements
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811





2812




2813
2814
2815
2816




2817
2818
2819
2820
2821
2822
2823
....
2932
2933
2934
2935
2936
2937
2938






2939
2940
2941
2942
2943
2944
2945
  struct ExprList_item *pOBItem;/* A term of the ORDER BY clause */
  Table *pTab = pIdx->pTable;   /* Table that owns index pIdx */
  ExprList *pOrderBy;           /* The ORDER BY clause */
  Parse *pParse = p->pParse;    /* Parser context */
  sqlite3 *db = pParse->db;     /* Database connection */
  int nPriorSat;                /* ORDER BY terms satisfied by outer loops */
  int seenRowid = 0;            /* True if an ORDER BY rowid term is seen */
  int uniqueNotNull = 1;        /* pIdx is UNIQUE with all terms are NOT NULL */

  if( p->i==0 ){
    nPriorSat = 0;
  }else{
    nPriorSat = p->aLevel[p->i-1].plan.nOBSat;





    if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return nPriorSat;




  }
  pOrderBy = p->pOrderBy;
  assert( pOrderBy!=0 );
  if( pIdx->bUnordered ) return nPriorSat;




  nTerm = pOrderBy->nExpr;
  uniqueNotNull = pIdx->onError!=OE_None;
  assert( nTerm>0 );

  /* Argument pIdx must either point to a 'real' named index structure, 
  ** or an index structure allocated on the stack by bestBtreeIndex() to
  ** represent the rowid index that is part of every table.  */
................................................................................
    if( iColumn<0 ){
      seenRowid = 1;
      break;
    }else if( pTab->aCol[iColumn].notNull==0 ){
      uniqueNotNull = 0;
    }
  }






  *pbRev = sortOrder & 1;

  /* If there was an "ORDER BY rowid" term that matched, or it is only
  ** possible for a single row from this table to match, then skip over
  ** any additional ORDER BY terms dealing with this table.
  */
  if( seenRowid || (uniqueNotNull && i>=pIdx->nColumn) ){







|





>
>
>
>
>
|
>
>
>
>



|
>
>
>
>







 







>
>
>
>
>
>







2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
....
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
  struct ExprList_item *pOBItem;/* A term of the ORDER BY clause */
  Table *pTab = pIdx->pTable;   /* Table that owns index pIdx */
  ExprList *pOrderBy;           /* The ORDER BY clause */
  Parse *pParse = p->pParse;    /* Parser context */
  sqlite3 *db = pParse->db;     /* Database connection */
  int nPriorSat;                /* ORDER BY terms satisfied by outer loops */
  int seenRowid = 0;            /* True if an ORDER BY rowid term is seen */
  int uniqueNotNull;            /* pIdx is UNIQUE with all terms are NOT NULL */

  if( p->i==0 ){
    nPriorSat = 0;
  }else{
    nPriorSat = p->aLevel[p->i-1].plan.nOBSat;
    if( (p->aLevel[p->i-1].plan.wsFlags & WHERE_ORDERED)==0 ){
      /* This loop cannot be ordered unless the next outer loop is
      ** also ordered */
      return nPriorSat;
    }
    if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ){
      /* Only look at the outer-most loop if the OrderByIdxJoin
      ** optimization is disabled */
      return nPriorSat;
    }
  }
  pOrderBy = p->pOrderBy;
  assert( pOrderBy!=0 );
  if( pIdx->bUnordered ){
    /* Hash indices (indicated by the "unordered" tag on sqlite_stat1) cannot
    ** be used for sorting */
    return nPriorSat;
  }
  nTerm = pOrderBy->nExpr;
  uniqueNotNull = pIdx->onError!=OE_None;
  assert( nTerm>0 );

  /* Argument pIdx must either point to a 'real' named index structure, 
  ** or an index structure allocated on the stack by bestBtreeIndex() to
  ** represent the rowid index that is part of every table.  */
................................................................................
    if( iColumn<0 ){
      seenRowid = 1;
      break;
    }else if( pTab->aCol[iColumn].notNull==0 ){
      uniqueNotNull = 0;
    }
  }

  /* If we have not found at least one ORDER BY term that matches the
  ** index, then show no progress. */
  if( pOBItem==&pOrderBy->a[nPriorSat] ) return nPriorSat;

  /* Return the necessary scan order back to the caller */
  *pbRev = sortOrder & 1;

  /* If there was an "ORDER BY rowid" term that matched, or it is only
  ** possible for a single row from this table to match, then skip over
  ** any additional ORDER BY terms dealing with this table.
  */
  if( seenRowid || (uniqueNotNull && i>=pIdx->nColumn) ){