/ Check-in [2459d323]
Login

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

Overview
Comment:Fix an incorrect cost computation for sorting (introduced just a few check-ins ago). Should be NlogN, not NloglogN.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 2459d3238853951bc3a507dd975e7ec921cf8446
User & Date: drh 2016-02-25 23:21:41
Context
2016-02-25
23:25
Add tool for smoke-testing the UWP VSIX package. check-in: d27f32c6 user: mistachkin tags: trunk
23:21
Fix an incorrect cost computation for sorting (introduced just a few check-ins ago). Should be NlogN, not NloglogN. check-in: 2459d323 user: drh tags: trunk
21:38
Small optimization in FK handling. check-in: e0d25913 user: mistachkin tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

3459
3460
3461
3462
3463
3464
3465
3466
3467
3468
3469
3470
3471
3472
3473
3474
3475
  LogEst rScale, rSortCost;
  assert( nOrderBy>0 && 66==sqlite3LogEst(100) );
  rScale = sqlite3LogEst((nOrderBy-nSorted)*100/nOrderBy) - 66;
  rSortCost = nRow + rScale + 16;

  /* Multiple by log(M) where M is the number of output rows.
  ** Use the LIMIT for M if it is smaller */
  if( (pWInfo->wctrlFlags & WHERE_USE_LIMIT)!=0 ){
    LogEst m = sqlite3LogEst(pWInfo->iLimit);
    if( m<nRow ) nRow = m;
  }
  rSortCost += estLog(nRow);
  return rSortCost;
}

/*
** Given the list of WhereLoop objects at pWInfo->pLoops, this routine







|
|
<







3459
3460
3461
3462
3463
3464
3465
3466
3467

3468
3469
3470
3471
3472
3473
3474
  LogEst rScale, rSortCost;
  assert( nOrderBy>0 && 66==sqlite3LogEst(100) );
  rScale = sqlite3LogEst((nOrderBy-nSorted)*100/nOrderBy) - 66;
  rSortCost = nRow + rScale + 16;

  /* Multiple by log(M) where M is the number of output rows.
  ** Use the LIMIT for M if it is smaller */
  if( (pWInfo->wctrlFlags & WHERE_USE_LIMIT)!=0 && pWInfo->iLimit<nRow ){
    nRow = pWInfo->iLimit;

  }
  rSortCost += estLog(nRow);
  return rSortCost;
}

/*
** Given the list of WhereLoop objects at pWInfo->pLoops, this routine

Changes to test/where.test.

569
570
571
572
573
574
575
576
577
578
579
580






581
582
583
584
585
586
587
  }
} {1 100 4 2 99 9 3 98 16 nosort}
do_test where-6.6 {
  cksort {
    SELECT * FROM t3 WHERE a>0 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}
do_test where-6.7 {
  cksort {
    SELECT * FROM t3 WHERE b>0 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}






ifcapable subquery {
  do_test where-6.8a {
    cksort {
      SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a LIMIT 3
    }
  } {1 100 4 2 99 9 3 98 16 nosort}
  do_test where-6.8b {







|

|

|
>
>
>
>
>
>







569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
  }
} {1 100 4 2 99 9 3 98 16 nosort}
do_test where-6.6 {
  cksort {
    SELECT * FROM t3 WHERE a>0 ORDER BY a LIMIT 3
  }
} {1 100 4 2 99 9 3 98 16 nosort}
do_test where-6.7.1 {
  cksort {
    SELECT * FROM t3 WHERE b>0 ORDER BY a LIMIT 10
  }
} {/1 100 4 2 99 9 3 98 16 .* nosort/}
do_test where-6.7.2 {
  cksort {
    SELECT * FROM t3 WHERE b>0 ORDER BY a LIMIT 1
  }
} {1 100 4 sort}
exit
ifcapable subquery {
  do_test where-6.8a {
    cksort {
      SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a LIMIT 3
    }
  } {1 100 4 2 99 9 3 98 16 nosort}
  do_test where-6.8b {