/ Check-in [24fe9f25]
Login

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

Overview
Comment:Further optimizations for sorting records that begin with integer or text values.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | sorter-opt
Files: files | file ages | folders
SHA1: 24fe9f25d64ee516633fed1ae7ebc21554aa69ca
User & Date: dan 2015-03-28 19:56:41
Context
2015-03-30
09:58
Remove some unnecessary code from vdbesort.c. check-in: b58191e9 user: dan tags: sorter-opt
2015-03-28
19:56
Further optimizations for sorting records that begin with integer or text values. check-in: 24fe9f25 user: dan tags: sorter-opt
2015-03-26
11:55
Optimize cases where all the sorter is sorting a set of records that all begin with integer values, or that all begin with text values to be compared using BINARY. check-in: ce5ad17c user: dan tags: sorter-opt
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/vdbesort.c.

   287    287   **      to sqlite3ThreadJoin() is likely to block. Cases that are likely to
   288    288   **      block provoke debugging output.
   289    289   **
   290    290   ** In both cases, the effects of the main thread seeing (bDone==0) even
   291    291   ** after the thread has finished are not dire. So we don't worry about
   292    292   ** memory barriers and such here.
   293    293   */
          294  +typedef int (*SorterCompare)(SortSubtask*,int*,const void*,int,const void*,int);
   294    295   struct SortSubtask {
   295    296     SQLiteThread *pThread;          /* Background thread, if any */
   296    297     int bDone;                      /* Set if thread is finished but not joined */
   297    298     VdbeSorter *pSorter;            /* Sorter that owns this sub-task */
   298    299     UnpackedRecord *pUnpacked;      /* Space to unpack a record */
   299    300     SorterList list;                /* List for thread to write to a PMA */
   300    301     int nPMA;                       /* Number of PMAs currently in file */
   301         -  RecordCompare xCompare;         /* Compare function to use */
          302  +  SorterCompare xCompare;         /* Compare function to use */
   302    303     SorterFile file;                /* Temp file for level-0 PMAs */
   303    304     SorterFile file2;               /* Space for other PMAs */
   304    305   };
          306  +
   305    307   
   306    308   /*
   307    309   ** Main sorter structure. A single instance of this is allocated for each 
   308    310   ** sorter cursor created by the VDBE.
   309    311   **
   310    312   ** mxKeysize:
   311    313   **   As records are added to the sorter by calls to sqlite3VdbeSorterWrite(),
................................................................................
   743    745   
   744    746     if( rc==SQLITE_OK ){
   745    747       rc = vdbePmaReaderNext(pReadr);
   746    748     }
   747    749     return rc;
   748    750   }
   749    751   
   750         -
   751    752   /*
   752    753   ** Compare key1 (buffer pKey1, size nKey1 bytes) with key2 (buffer pKey2, 
   753    754   ** size nKey2 bytes). Use (pTask->pKeyInfo) for the collation sequences
   754    755   ** used by the comparison. Return the result of the comparison.
   755    756   **
   756         -** Before returning, object (pTask->pUnpacked) is populated with the
   757         -** unpacked version of key2. Or, if pKey2 is passed a NULL pointer, then it 
   758         -** is assumed that the (pTask->pUnpacked) structure already contains the 
   759         -** unpacked key to use as key2.
          757  +** If IN/OUT parameter *pbKey2Cached is true when this function is called,
          758  +** it is assumed that (pTask->pUnpacked) contains the unpacked version
          759  +** of key2. If it is false, (pTask->pUnpacked) is populated with the unpacked
          760  +** version of key2 and *pbKey2Cached set to true before returning.
   760    761   **
   761    762   ** If an OOM error is encountered, (pTask->pUnpacked->error_rc) is set
   762    763   ** to SQLITE_NOMEM.
   763    764   */
   764    765   static int vdbeSorterCompare(
   765    766     SortSubtask *pTask,             /* Subtask context (for pKeyInfo) */
          767  +  int *pbKey2Cached,              /* True if pTask->pUnpacked is pKey2 */
   766    768     const void *pKey1, int nKey1,   /* Left side of comparison */
   767    769     const void *pKey2, int nKey2    /* Right side of comparison */
   768    770   ){
   769    771     UnpackedRecord *r2 = pTask->pUnpacked;
   770         -  if( pKey2 ){
          772  +  if( !*pbKey2Cached ){
   771    773       sqlite3VdbeRecordUnpack(pTask->pSorter->pKeyInfo, nKey2, pKey2, r2);
          774  +    *pbKey2Cached = 1;
   772    775     }
   773         -  return pTask->xCompare(nKey1, pKey1, r2);
          776  +  return sqlite3VdbeRecordCompare(nKey1, pKey1, r2);
          777  +}
          778  +
          779  +/*
          780  +** A specially optimized version of vdbeSorterCompare() that assumes that
          781  +** the first field of each key is a TEXT value and that the collation
          782  +** sequence to compare them with is BINARY.
          783  +*/
          784  +static int vdbeSorterCompareText(
          785  +  SortSubtask *pTask,             /* Subtask context (for pKeyInfo) */
          786  +  int *pbKey2Cached,              /* True if pTask->pUnpacked is pKey2 */
          787  +  const void *pKey1, int nKey1,   /* Left side of comparison */
          788  +  const void *pKey2, int nKey2    /* Right side of comparison */
          789  +){
          790  +  const u8 * const p1 = (const u8 * const)pKey1;
          791  +  const u8 * const p2 = (const u8 * const)pKey2;
          792  +  const u8 * const v1 = &p1[ p1[0] ];   /* Pointer to value 1 */
          793  +  const u8 * const v2 = &p2[ p2[0] ];   /* Pointer to value 2 */
          794  +
          795  +  int n1;
          796  +  int n2;
          797  +  int res;
          798  +
          799  +  getVarint32(&p1[1], n1); n1 = (n1 - 13) / 2;
          800  +  getVarint32(&p2[1], n2); n2 = (n2 - 13) / 2;
          801  +  res = memcmp(v1, v2, MIN(n1, n2));
          802  +  if( res==0 ){
          803  +    res = n1 - n2;
          804  +  }
          805  +
          806  +  if( res==0 ){
          807  +    if( pTask->pSorter->pKeyInfo->nField>1 ){
          808  +      res = vdbeSorterCompare(pTask, pbKey2Cached, pKey1, nKey1, pKey2, nKey2);
          809  +    }
          810  +  }else{
          811  +    if( pTask->pSorter->pKeyInfo->aSortOrder[0] ){
          812  +      res = res * -1;
          813  +    }
          814  +  }
          815  +
          816  +  return res;
          817  +}
          818  +
          819  +/*
          820  +** A specially optimized version of vdbeSorterCompare() that assumes that
          821  +** the first field of each key is an INTEGER value.
          822  +*/
          823  +static int vdbeSorterCompareInt(
          824  +  SortSubtask *pTask,             /* Subtask context (for pKeyInfo) */
          825  +  int *pbKey2Cached,              /* True if pTask->pUnpacked is pKey2 */
          826  +  const void *pKey1, int nKey1,   /* Left side of comparison */
          827  +  const void *pKey2, int nKey2    /* Right side of comparison */
          828  +){
          829  +  const u8 * const p1 = (const u8 * const)pKey1;
          830  +  const u8 * const p2 = (const u8 * const)pKey2;
          831  +  const int s1 = p1[1];                 /* Left hand serial type */
          832  +  const int s2 = p2[1];                 /* Right hand serial type */
          833  +  const u8 * const v1 = &p1[ p1[0] ];   /* Pointer to value 1 */
          834  +  const u8 * const v2 = &p2[ p2[0] ];   /* Pointer to value 2 */
          835  +  int res;                              /* Return value */
          836  +
          837  +  assert( (s1>0 && s1<7) || s1==8 || s1==9 );
          838  +  assert( (s2>0 && s2<7) || s2==8 || s2==9 );
          839  +
          840  +  if( s1>7 && s2>7 ){
          841  +    res = s1 - s2;
          842  +  }else{
          843  +    if( s1==s2 ){
          844  +      if( (*v1 ^ *v2) & 0x80 ){
          845  +        /* The two values have different signs */
          846  +        res = (*v1 & 0x80) ? -1 : +1;
          847  +      }else{
          848  +        /* The two values have the same sign. Compare using memcmp(). */
          849  +        static const u8 aLen[] = {0, 1, 2, 3, 4, 6, 8 };
          850  +        int i;
          851  +        res = 0;
          852  +        for(i=0; i<aLen[s1]; i++){
          853  +          if( (res = v1[i] - v2[i]) ) break;
          854  +        }
          855  +      }
          856  +    }else{
          857  +      if( s2>7 ){
          858  +        res = +1;
          859  +      }else if( s1>7 ){
          860  +        res = -1;
          861  +      }else{
          862  +        res = s1 - s2;
          863  +      }
          864  +
          865  +      if( res>0 ){
          866  +        if( *v1 & 0x80 ) res = -1;
          867  +      }else if( res<0 ){
          868  +        if( *v2 & 0x80 ) res = +1;
          869  +      }
          870  +    }
          871  +  }
          872  +
          873  +  if( res==0 ){
          874  +    if( pTask->pSorter->pKeyInfo->nField>1 ){
          875  +      res = vdbeSorterCompare(pTask, pbKey2Cached, pKey1, nKey1, pKey2, nKey2);
          876  +    }
          877  +  }else if( pTask->pSorter->pKeyInfo->aSortOrder[0] ){
          878  +    res = res * -1;
          879  +  }
          880  +
          881  +  return res;
   774    882   }
   775    883   
   776    884   /*
   777    885   ** Initialize the temporary index cursor just opened as a sorter cursor.
   778    886   **
   779    887   ** Usually, the sorter module uses the value of (pCsr->pKeyInfo->nField)
   780    888   ** to determine the number of fields that should be compared from the
................................................................................
   869    977           assert( pSorter->iMemory==0 );
   870    978           pSorter->nMemory = pgsz;
   871    979           pSorter->list.aMemory = (u8*)sqlite3Malloc(pgsz);
   872    980           if( !pSorter->list.aMemory ) rc = SQLITE_NOMEM;
   873    981         }
   874    982       }
   875    983   
   876         -    if( (pKeyInfo->nField+pKeyInfo->nXField)<13 && pKeyInfo->aColl[0]==0 ){
          984  +    if( (pKeyInfo->nField+pKeyInfo->nXField)<13 
          985  +     && (pKeyInfo->aColl[0]==0 || pKeyInfo->aColl[0]==db->pDfltColl)
          986  +    ){
   877    987         pSorter->typeMask = SORTER_TYPE_INTEGER | SORTER_TYPE_TEXT;
   878    988       }
   879    989     }
   880    990   
   881    991     return rc;
   882    992   }
   883    993   #undef nWorker   /* Defined at the top of this function */
................................................................................
  1215   1325     SortSubtask *pTask,             /* Calling thread context */
  1216   1326     SorterRecord *p1,               /* First list to merge */
  1217   1327     SorterRecord *p2,               /* Second list to merge */
  1218   1328     SorterRecord **ppOut            /* OUT: Head of merged list */
  1219   1329   ){
  1220   1330     SorterRecord *pFinal = 0;
  1221   1331     SorterRecord **pp = &pFinal;
  1222         -  void *pVal2 = p2 ? SRVAL(p2) : 0;
         1332  +  int bCached = 0;
  1223   1333   
  1224   1334     while( p1 && p2 ){
  1225   1335       int res;
  1226         -    res = vdbeSorterCompare(pTask, SRVAL(p1), p1->nVal, pVal2, p2->nVal);
         1336  +    res = pTask->xCompare(
         1337  +        pTask, &bCached, SRVAL(p1), p1->nVal, SRVAL(p2), p2->nVal
         1338  +    );
         1339  +
  1227   1340       if( res<=0 ){
  1228   1341         *pp = p1;
  1229   1342         pp = &p1->u.pNext;
  1230   1343         p1 = p1->u.pNext;
  1231         -      pVal2 = 0;
  1232   1344       }else{
  1233   1345         *pp = p2;
  1234         -       pp = &p2->u.pNext;
         1346  +      pp = &p2->u.pNext;
  1235   1347         p2 = p2->u.pNext;
  1236         -      if( p2==0 ) break;
  1237         -      pVal2 = SRVAL(p2);
         1348  +      bCached = 0;
  1238   1349       }
  1239   1350     }
  1240   1351     *pp = p1 ? p1 : p2;
  1241   1352     *ppOut = pFinal;
  1242   1353   }
         1354  +
         1355  +/*
         1356  +** Return the SorterCompare function to compare values collected by the
         1357  +** sorter object passed as the only argument.
         1358  +*/
         1359  +static SorterCompare vdbeSorterGetCompare(VdbeSorter *p){
         1360  +  if( p->typeMask==SORTER_TYPE_INTEGER ){
         1361  +    return vdbeSorterCompareInt;
         1362  +  }else if( p->typeMask==SORTER_TYPE_TEXT ){
         1363  +    return vdbeSorterCompareText; 
         1364  +  }
         1365  +  return vdbeSorterCompare;
         1366  +}
  1243   1367   
  1244   1368   /*
  1245   1369   ** Sort the linked list of records headed at pTask->pList. Return 
  1246   1370   ** SQLITE_OK if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if 
  1247   1371   ** an error occurs.
  1248   1372   */
  1249   1373   static int vdbeSorterSort(SortSubtask *pTask, SorterList *pList){
................................................................................
  1252   1376     SorterRecord *p;
  1253   1377     int rc;
  1254   1378   
  1255   1379     rc = vdbeSortAllocUnpacked(pTask);
  1256   1380     if( rc!=SQLITE_OK ) return rc;
  1257   1381   
  1258   1382     p = pList->pList;
  1259         -  if( pTask->pSorter->typeMask==0 ){
  1260         -    pTask->xCompare = sqlite3VdbeRecordCompare;
  1261         -  }else{
  1262         -    UnpackedRecord *pRec = pTask->pUnpacked;
  1263         -    sqlite3VdbeRecordUnpack(pTask->pSorter->pKeyInfo, p->nVal, SRVAL(p), pRec);
  1264         -    pTask->xCompare = sqlite3VdbeFindCompare(pRec);
  1265         -  }
         1383  +  pTask->xCompare = vdbeSorterGetCompare(pTask->pSorter);
  1266   1384   
  1267   1385     aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *));
  1268   1386     if( !aSlot ){
  1269   1387       return SQLITE_NOMEM;
  1270   1388     }
  1271   1389   
  1272   1390     while( p ){
................................................................................
  1478   1596     rc = vdbePmaReaderNext(&pMerger->aReadr[iPrev]);
  1479   1597   
  1480   1598     /* Update contents of aTree[] */
  1481   1599     if( rc==SQLITE_OK ){
  1482   1600       int i;                      /* Index of aTree[] to recalculate */
  1483   1601       PmaReader *pReadr1;         /* First PmaReader to compare */
  1484   1602       PmaReader *pReadr2;         /* Second PmaReader to compare */
  1485         -    u8 *pKey2;                  /* To pReadr2->aKey, or 0 if record cached */
         1603  +    int bCached = 0;
  1486   1604   
  1487   1605       /* Find the first two PmaReaders to compare. The one that was just
  1488   1606       ** advanced (iPrev) and the one next to it in the array.  */
  1489   1607       pReadr1 = &pMerger->aReadr[(iPrev & 0xFFFE)];
  1490   1608       pReadr2 = &pMerger->aReadr[(iPrev | 0x0001)];
  1491         -    pKey2 = pReadr2->aKey;
  1492   1609   
  1493   1610       for(i=(pMerger->nTree+iPrev)/2; i>0; i=i/2){
  1494   1611         /* Compare pReadr1 and pReadr2. Store the result in variable iRes. */
  1495   1612         int iRes;
  1496   1613         if( pReadr1->pFd==0 ){
  1497   1614           iRes = +1;
  1498   1615         }else if( pReadr2->pFd==0 ){
  1499   1616           iRes = -1;
  1500   1617         }else{
  1501         -        iRes = vdbeSorterCompare(pTask, 
  1502         -            pReadr1->aKey, pReadr1->nKey, pKey2, pReadr2->nKey
         1618  +        iRes = pTask->xCompare(pTask, &bCached,
         1619  +            pReadr1->aKey, pReadr1->nKey, pReadr2->aKey, pReadr2->nKey
  1503   1620           );
  1504   1621         }
  1505   1622   
  1506   1623         /* If pReadr1 contained the smaller value, set aTree[i] to its index.
  1507   1624         ** Then set pReadr2 to the next PmaReader to compare to pReadr1. In this
  1508   1625         ** case there is no cache of pReadr2 in pTask->pUnpacked, so set
  1509   1626         ** pKey2 to point to the record belonging to pReadr2.
................................................................................
  1517   1634         ** If the two values were equal, then the value from the oldest
  1518   1635         ** PMA should be considered smaller. The VdbeSorter.aReadr[] array
  1519   1636         ** is sorted from oldest to newest, so pReadr1 contains older values
  1520   1637         ** than pReadr2 iff (pReadr1<pReadr2).  */
  1521   1638         if( iRes<0 || (iRes==0 && pReadr1<pReadr2) ){
  1522   1639           pMerger->aTree[i] = (int)(pReadr1 - pMerger->aReadr);
  1523   1640           pReadr2 = &pMerger->aReadr[ pMerger->aTree[i ^ 0x0001] ];
  1524         -        pKey2 = pReadr2->aKey;
         1641  +        bCached = 0;
  1525   1642         }else{
  1526         -        if( pReadr1->pFd ) pKey2 = 0;
         1643  +        bCached = (pReadr1->pFd!=0);
  1527   1644           pMerger->aTree[i] = (int)(pReadr2 - pMerger->aReadr);
  1528   1645           pReadr1 = &pMerger->aReadr[ pMerger->aTree[i ^ 0x0001] ];
  1529   1646         }
  1530   1647       }
  1531   1648       *pbEof = (pMerger->aReadr[pMerger->aTree[1]].pFd==0);
  1532   1649     }
  1533   1650   
................................................................................
  1631   1748     int nReq;                       /* Bytes of memory required */
  1632   1749     int nPMA;                       /* Bytes of PMA space required */
  1633   1750     int t;                          /* serial type of first record field */
  1634   1751   
  1635   1752     getVarint32((const u8*)&pVal->z[1], t);
  1636   1753     if( t>0 && t<10 && t!=7 ){
  1637   1754       pSorter->typeMask &= SORTER_TYPE_INTEGER;
  1638         -  }else if( t & 0x01 ){
         1755  +  }else if( t>10 && (t & 0x01) ){
  1639   1756       pSorter->typeMask &= SORTER_TYPE_TEXT;
  1640   1757     }else{
  1641   1758       pSorter->typeMask = 0;
  1642   1759     }
  1643   1760   
  1644   1761     assert( pSorter );
  1645   1762   
................................................................................
  1901   2018     p2 = &pMerger->aReadr[i2];
  1902   2019   
  1903   2020     if( p1->pFd==0 ){
  1904   2021       iRes = i2;
  1905   2022     }else if( p2->pFd==0 ){
  1906   2023       iRes = i1;
  1907   2024     }else{
         2025  +    SortSubtask *pTask = pMerger->pTask;
         2026  +    int bCached = 0;
  1908   2027       int res;
  1909         -    assert( pMerger->pTask->pUnpacked!=0 );  /* from vdbeSortSubtaskMain() */
  1910         -    res = vdbeSorterCompare(
  1911         -        pMerger->pTask, p1->aKey, p1->nKey, p2->aKey, p2->nKey
         2028  +    assert( pTask->pUnpacked!=0 );  /* from vdbeSortSubtaskMain() */
         2029  +    res = pTask->xCompare(
         2030  +        pTask, &bCached, p1->aKey, p1->nKey, p2->aKey, p2->nKey
  1912   2031       );
  1913   2032       if( res<=0 ){
  1914   2033         iRes = i1;
  1915   2034       }else{
  1916   2035         iRes = i2;
  1917   2036       }
  1918   2037     }
................................................................................
  2322   2441   */
  2323   2442   static int vdbeSorterSetupMerge(VdbeSorter *pSorter){
  2324   2443     int rc;                         /* Return code */
  2325   2444     SortSubtask *pTask0 = &pSorter->aTask[0];
  2326   2445     MergeEngine *pMain = 0;
  2327   2446   #if SQLITE_MAX_WORKER_THREADS
  2328   2447     sqlite3 *db = pTask0->pSorter->db;
  2329         -  RecordCompare xCompare = (pSorter->typeMask==0 ? 
  2330         -      sqlite3VdbeRecordCompare : pSorter->aTask[0].xCompare
  2331         -  );
  2332   2448     int i;
         2449  +  SorterCompare xCompare = vdbeSorterGetCompare(pSorter);
  2333   2450     for(i=0; i<pSorter->nTask; i++){
  2334   2451       pSorter->aTask[i].xCompare = xCompare;
  2335   2452     }
  2336   2453   #endif
  2337   2454   
  2338   2455     rc = vdbeSorterMergeTreeBuild(pSorter, &pMain);
  2339   2456     if( rc==SQLITE_OK ){