/ Check-in [d8efa5f8]
Login

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

Overview
Comment:Futher enhancements to the ORDER BY optimizer.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: d8efa5f8b60bc4c8df8bfad077f87f76f7ee9bf6
User & Date: drh 2013-05-31 13:36:32
Context
2013-05-31
14:31
Enhance the shell to provide more flexibility when entering numeric arguments on dot-commands. In particular, allow hex arguments to .wheretrace. check-in: b9578c37 user: drh tags: nextgen-query-plan-exp
13:36
Futher enhancements to the ORDER BY optimizer. check-in: d8efa5f8 user: drh tags: nextgen-query-plan-exp
12:43
Improved detection of unnecessary ORDER BY clauses. check-in: 58805eb3 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

4506
4507
4508
4509
4510
4511
4512

4513
4514
4515
4516
4517
4518
4519
....
4565
4566
4567
4568
4569
4570
4571

4572
4573
4574
4575

4576
4577
4578
4579
4580
4581
4582
....
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
....
4633
4634
4635
4636
4637
4638
4639
4640




4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651
....
4739
4740
4741
4742
4743
4744
4745
4746
4747
4748
4749
4750
4751
4752
4753
**   -1:  Unknown at this time
**
*/
static int wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */
  WherePath *pPath,     /* The WherePath to check */
  int nLoop,            /* Number of entries in pPath->aLoop[] */

  WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  Bitmask *pRevMask     /* Mask of WhereLoops to run in reverse order */
){
  u8 revSet;            /* True if rev is known */
  u8 rev;               /* Composite sort order */
  u8 revIdx;            /* Index sort order */
  u8 isOneRow;          /* Current WhereLoop is a one-row loop */
................................................................................
    assert( nLoop==0 );
    return pLast->u.vtab.isOrdered;
  }

  /* Sorting is always required if any term of the ORDER BY is not a 
  ** column reference */
  nOrderBy = pOrderBy->nExpr;

  for(i=0; i<nOrderBy; i++){
    pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
    if( pOBExpr->op!=TK_COLUMN ) return 0;
  }

    
  for(i=0; i<=nLoop && nUsed<nOrderBy; i++){
    pLoop = i<nLoop ? pPath->aLoop[i] : pLast;
    assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
    isOneRow = isUniqueIdx = 1;
    if( pLoop->wsFlags & WHERE_IPK ){
      if( (pLoop->wsFlags & WHERE_COLUMN_IN)!=0 ) isOneRow = 0;
................................................................................
    requireOneRow = !isOneRow;
    iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
    j = 0;
    revSet = rev = 0;
    for(j=0; j<=nColumn && nUsed<nOrderBy; j++, nUsed++){
      int skipable;
      pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
      assert( pOBExpr->op==TK_COLUMN );
      if( pOBExpr->iTable!=iCur ) break;
      if( isOneRow ){ j--; continue; }
      if( j<nColumn ){
        /* Normal index columns */
        iColumn = pIndex->aiColumn[j];
        revIdx = pIndex->aSortOrder[j];
        if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
................................................................................
        if( revSet ){
          if( (rev ^ revIdx)!=pOrderBy->a[nUsed].sortOrder ) return 0;
        }else{
          rev = revIdx ^ pOrderBy->a[nUsed].sortOrder;
          revSet = 1;
        }
      }
      if( j>=nColumn-1 && isUniqueIdx ){ j--; isOneRow = 1; }




    }
    if( rev ) revMask |= ((Bitmask)1)<<i;
  }
  if( nUsed==nOrderBy ){
    *pRevMask = revMask;
    return 1;
  }
  return -1;
}

#ifdef WHERETRACE_ENABLED
................................................................................
        if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        /* At this point, pWLoop is a candidate to be the next loop. 
        ** Compute its cost */
        rCost = pWLoop->rSetup + pWLoop->rRun*pFrom->nRow + pFrom->rCost;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( !isOrderedValid ){
          switch( wherePathSatisfiesOrderBy(pWInfo, pFrom, iLoop,
                                            pWLoop, &revMask) ){
            case 1:  /* Yes.  pFrom+pWLoop does satisfy the ORDER BY clause */
              isOrdered = 1;
              isOrderedValid = 1;
              break;
            case 0:  /* No.  pFrom+pWLoop will require a separate sort */
              isOrdered = 0;







>







 







>




>







 







|







 







|
>
>
>
>



|







 







|







4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
....
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
4579
4580
4581
4582
4583
4584
4585
....
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
....
4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
4658
....
4746
4747
4748
4749
4750
4751
4752
4753
4754
4755
4756
4757
4758
4759
4760
**   -1:  Unknown at this time
**
*/
static int wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */
  WherePath *pPath,     /* The WherePath to check */
  int nLoop,            /* Number of entries in pPath->aLoop[] */
  int isLastLoop,       /* True for the very last loop */
  WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  Bitmask *pRevMask     /* Mask of WhereLoops to run in reverse order */
){
  u8 revSet;            /* True if rev is known */
  u8 rev;               /* Composite sort order */
  u8 revIdx;            /* Index sort order */
  u8 isOneRow;          /* Current WhereLoop is a one-row loop */
................................................................................
    assert( nLoop==0 );
    return pLast->u.vtab.isOrdered;
  }

  /* Sorting is always required if any term of the ORDER BY is not a 
  ** column reference */
  nOrderBy = pOrderBy->nExpr;
#if 0
  for(i=0; i<nOrderBy; i++){
    pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
    if( pOBExpr->op!=TK_COLUMN ) return 0;
  }
#endif
    
  for(i=0; i<=nLoop && nUsed<nOrderBy; i++){
    pLoop = i<nLoop ? pPath->aLoop[i] : pLast;
    assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
    isOneRow = isUniqueIdx = 1;
    if( pLoop->wsFlags & WHERE_IPK ){
      if( (pLoop->wsFlags & WHERE_COLUMN_IN)!=0 ) isOneRow = 0;
................................................................................
    requireOneRow = !isOneRow;
    iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
    j = 0;
    revSet = rev = 0;
    for(j=0; j<=nColumn && nUsed<nOrderBy; j++, nUsed++){
      int skipable;
      pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[nUsed].pExpr);
      if( pOBExpr->op!=TK_COLUMN ) return 0;
      if( pOBExpr->iTable!=iCur ) break;
      if( isOneRow ){ j--; continue; }
      if( j<nColumn ){
        /* Normal index columns */
        iColumn = pIndex->aiColumn[j];
        revIdx = pIndex->aSortOrder[j];
        if( iColumn==pIndex->pTable->iPKey ) iColumn = -1;
................................................................................
        if( revSet ){
          if( (rev ^ revIdx)!=pOrderBy->a[nUsed].sortOrder ) return 0;
        }else{
          rev = revIdx ^ pOrderBy->a[nUsed].sortOrder;
          revSet = 1;
        }
      }
      if( j>=nColumn-1 && isUniqueIdx ){
        if( isLastLoop && i==nLoop ) break;
        j--;
        isOneRow = 1;
      }
    }
    if( rev ) revMask |= ((Bitmask)1)<<i;
  }
  if( isLastLoop || nUsed==nOrderBy ){
    *pRevMask = revMask;
    return 1;
  }
  return -1;
}

#ifdef WHERETRACE_ENABLED
................................................................................
        if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
        if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
        /* At this point, pWLoop is a candidate to be the next loop. 
        ** Compute its cost */
        rCost = pWLoop->rSetup + pWLoop->rRun*pFrom->nRow + pFrom->rCost;
        maskNew = pFrom->maskLoop | pWLoop->maskSelf;
        if( !isOrderedValid ){
          switch( wherePathSatisfiesOrderBy(pWInfo, pFrom, iLoop, iLoop==nLoop-1,
                                            pWLoop, &revMask) ){
            case 1:  /* Yes.  pFrom+pWLoop does satisfy the ORDER BY clause */
              isOrdered = 1;
              isOrderedValid = 1;
              break;
            case 0:  /* No.  pFrom+pWLoop will require a separate sort */
              isOrdered = 0;