SQLite

Check-in [2459d32388]
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
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 2459d3238853951bc3a507dd975e7ec921cf8446
User & Date: drh 2016-02-25 23:21:41.832
Context
2016-02-25
23:25
Add tool for smoke-testing the UWP VSIX package. (check-in: d27f32c6d7 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: 2459d32388 user: drh tags: trunk)
21:38
Small optimization in FK handling. (check-in: e0d25913b7 user: mistachkin tags: trunk)
Changes
Unified Diff 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 {
︙︙