SQLite4
Check-in [d9fa045dd7]
Not logged in

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

Overview
Comment:Write a delete-key into the top level of the fast-insert tree when an item is deleted. Change the seek code so that if a delete-key is encountered SQLITE4_NOTFOUND is returned to the caller.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: d9fa045dd73419a940de66ec6cae9a55ab2c8714
User & Date: dan 2013-11-28 18:24:18
Context
2013-12-05
20:08
Support scan queries on fast-insert data. Still some problems. check-in: 0cd2ab7e9e user: dan tags: trunk
2013-11-28
18:24
Write a delete-key into the top level of the fast-insert tree when an item is deleted. Change the seek code so that if a delete-key is encountered SQLITE4_NOTFOUND is returned to the caller. check-in: d9fa045dd7 user: dan tags: trunk
15:23
Make a small change to the bt cell formats to accommodate delete keys. check-in: a5186d0b0a user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/bt_main.c.

   492    492       if( btFlags(aData) & BT_PGFLAGS_INTERNAL ){
   493    493         sqlite4BtBufAppendf(pBuf, "  child=%d ", (int)btGetU32(&pCell[j]));
   494    494       }else{
   495    495         int nVal;
   496    496         pCell += nKey;
   497    497         sqlite4BtBufAppendf(pBuf, "  ");
   498    498         pCell += sqlite4BtVarintGet32(pCell, &nVal);
   499         -      for(j=0; j<(nVal-1); j++){
   500         -        sqlite4BtBufAppendf(pBuf, "%02X", (int)pCell[j]);
          499  +      if( nVal>=2 ){
          500  +        for(j=0; j<(nVal-2); j++){
          501  +          sqlite4BtBufAppendf(pBuf, "%02X", (int)pCell[j]);
          502  +        }
          503  +      }else{
          504  +        sqlite4BtBufAppendf(pBuf, "delete-key");
   501    505         }
   502    506       }
   503    507       sqlite4BtBufAppendf(pBuf, "\n");
   504    508     }
   505    509   }
   506    510   
   507    511   int sqlite4BtDebugPage(sqlite4_buffer *pBuf, u32 pgno, char *aData, int nData){
................................................................................
   870    874     return rc;
   871    875   }
   872    876   
   873    877   static u32 btBlockToRoot(BtDbHdr *pHdr, u32 iBlk){
   874    878     assert( iBlk>0 );
   875    879     return (iBlk - 1) * (pHdr->blksz / pHdr->pgsz) + 1;
   876    880   }
          881  +
          882  +/*
          883  +** Return true if the cell that the argument cursor currently points to
          884  +** is a delete marker.
          885  +*/
          886  +static int fiCsrIsDelete(BtCursor *pCsr){
          887  +  const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
          888  +  int bRet;                       /* Return value */
          889  +  u8 *aData;
          890  +  u8 *pCell;
          891  +  int n;
          892  +
          893  +  aData = sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
          894  +  pCell = btCellFind(aData, pgsz, pCsr->aiCell[pCsr->nPg-1]);
          895  +
          896  +  pCell += sqlite4BtVarintGet32(pCell, &n);
          897  +  if( n==0 ){
          898  +    /* Type (c) cell */
          899  +    pCell += sqlite4BtVarintGet32(pCell, &n);
          900  +    pCell += n;
          901  +    pCell += sqlite4BtVarintGet32(pCell, &n);
          902  +    pCell += sqlite4BtVarintGet32(pCell, &n);
          903  +    bRet = (n==0);
          904  +  }else{
          905  +    pCell += n;
          906  +    pCell += sqlite4BtVarintGet32(pCell, &n);
          907  +    bRet = (n==1);
          908  +  }
          909  +
          910  +  return bRet;
          911  +}
   877    912   
   878    913   /*
   879    914   ** Seek a fast-insert cursor.
   880    915   */
   881    916   static int fiCsrSeek(FiCursor *pCsr, const void *pK, int nK, int eSeek){
   882    917     int rc = SQLITE4_OK;            /* Return code */
   883    918     bt_db *db = pCsr->base.pDb;     /* Database handle */
................................................................................
   911    946             btCsrSetup(db, btBlockToRoot(pHdr, iBlk), pSub);
   912    947             rc = btCsrSeek(pSub, pK, nK, BT_SEEK_EQ, BT_CSRSEEK_SEEK);
   913    948             if( rc!=SQLITE4_NOTFOUND && rc!=SQLITE4_INEXACT ){
   914    949               /* A hit on the requested key or an error has occurred. Either
   915    950               ** way, break out of the loop. If this is a hit, set iBt to
   916    951               ** zero so that the BtCsrKey() and BtCsrData() routines know
   917    952               ** to return data from the first (only) sub-cursor. */
   918         -            if( rc==SQLITE4_OK ) pCsr->iBt = 0;
          953  +            assert( pCsr->iBt<0 );
          954  +            if( rc==SQLITE4_OK ){
          955  +              if( 0==fiCsrIsDelete(pSub) ){
          956  +                pCsr->iBt = 0;
          957  +              }else{
          958  +                rc = SQLITE4_NOTFOUND;
          959  +              }
          960  +            }
   919    961               break;
   920    962             }
   921    963           }
   922    964           btCsrReset(&mcsr, 1);
   923    965         }
   924    966       }else{
   925    967         /* Deal with this later... */
................................................................................
  1436   1478       p += sqlite4BtVarintGet32(p, &nKey);
  1437   1479       if( nKey==0 ){
  1438   1480         /* Type (b) cell */
  1439   1481         p += sqlite4BtVarintGet32(p, &nKey);
  1440   1482         p += nKey;
  1441   1483         p += sqlite4BtVarintGet32(p, &nKey);
  1442   1484         p += btOverflowArrayLen(p);
  1443         -    }else{
  1444         -      /* Type (a) cell */
         1485  +    }else if( nKey>=2 ){
  1445   1486         p += (nKey-2);
  1446   1487       }
  1447   1488     }
  1448   1489   
  1449   1490     return (p-pCell);
  1450   1491   }
  1451   1492   
................................................................................
  1582   1623     assert( pKV->eType==KV_CELL || pKV->eType==KV_VALUE );
  1583   1624     if( pKV->eType==KV_CELL ){
  1584   1625       nByte = pKV->nV;
  1585   1626     }else{
  1586   1627       if( pKV->pgno ){
  1587   1628         nByte = sqlite4BtVarintLen32(pKV->nK) + pKV->nK + 4;
  1588   1629       }else{
         1630  +      assert( pKV->nV>=0 || pKV->pV==0 );
  1589   1631         nByte = 
  1590   1632           sqlite4BtVarintLen32(pKV->nK) 
  1591   1633           + sqlite4BtVarintLen32(pKV->nV+2)
  1592         -        + pKV->nV + pKV->nK;
         1634  +        + MAX(pKV->nV, 0) + pKV->nK;
  1593   1635       }
  1594   1636     }
  1595   1637     return nByte;
  1596   1638   }
  1597   1639   
  1598   1640   /*
  1599   1641   ** Write a cell based on *pKV to buffer aBuffer. Return the number
................................................................................
  1606   1648       memcpy(aBuf, pKV->pV, i);
  1607   1649     }else{
  1608   1650       i += sqlite4BtVarintPut32(&aBuf[i], pKV->nK);
  1609   1651       memcpy(&aBuf[i], pKV->pK, pKV->nK); i += pKV->nK;
  1610   1652   
  1611   1653       if( pKV->pgno==0 ){
  1612   1654         i += sqlite4BtVarintPut32(&aBuf[i], pKV->nV+2);
  1613         -      memcpy(&aBuf[i], pKV->pV, pKV->nV); 
  1614         -      i += pKV->nV;
         1655  +      if( pKV->nV>0 ){
         1656  +        memcpy(&aBuf[i], pKV->pV, pKV->nV); 
         1657  +        i += pKV->nV;
         1658  +      }
  1615   1659       }else{
  1616   1660         btPutU32(&aBuf[i], pKV->pgno);
  1617   1661         i += 4;
  1618   1662       }
  1619   1663     }
  1620   1664   
  1621   1665     assert( i==btKVCellSize(pKV) );
................................................................................
  1662   1706       rc = sqlite4BtPageAllocate(db->pPager, ppPg);
  1663   1707     }
  1664   1708     return rc;
  1665   1709   }
  1666   1710   
  1667   1711   /*
  1668   1712   ** Trim a non-overflow page.
  1669         -**
  1670         -** This function is a simple wrapper around sqlite4BtPageAllocate(),
  1671         -** except that if the database is currenly in fast-insert mode the
  1672         -** BtDbHdr.nSubPg counter is incremented.
  1673   1713   */
  1674   1714   static int btTrimNonOverflow(bt_db *db, BtPage *pPg){
  1675         -  int rc = sqlite4BtPageTrim(pPg);
  1676         -  if( rc==SQLITE4_OK && db->bFastInsertOp ){
  1677         -    BtDbHdr *pHdr = sqlite4BtPagerDbhdr(db->pPager);
  1678         -    pHdr->nSubPg--;
         1715  +  int rc;                         /* Return code */
         1716  +  if( db->bFastInsertOp==0 ){
         1717  +    rc = sqlite4BtPageTrim(pPg);
         1718  +  }else{
         1719  +    rc = sqlite4BtPageRelease(pPg);
  1679   1720     }
  1680   1721     return rc;
  1681   1722   }
  1682   1723   
  1683   1724   /*
  1684   1725   ** Allocate and zero an overflow page.
  1685   1726   */
................................................................................
  1828   1869   
  1829   1870     assert( pKV->pgno==0 && pKV->eType==KV_VALUE );
  1830   1871   
  1831   1872     /* Check if this is a type (a) cell - one that can fit entirely on a 
  1832   1873     ** leaf page. If so, do nothing.  */
  1833   1874     nReq = btKVCellSize(pKV);
  1834   1875     if( nReq > nMaxSize ){
  1835         -    int nArraySz = btOverflowArraySz(pgsz, pKV->nK + pKV->nV);
         1876  +    int nArraySz = btOverflowArraySz(pgsz, pKV->nK + MAX(0, pKV->nV));
  1836   1877       u8 *pBuf = 0;                 /* Buffer containing formatted cell */
  1837   1878       int nKeyOvfl;                 /* Bytes of key that overflow */
  1838   1879       int nValOvfl;                 /* Bytes of value that overflow */
  1839   1880   
  1840   1881       /* Check if the entire key can fit on a leaf page. If so, this is a
  1841   1882       ** type (b) page - entire key and partial value on the leaf page, 
  1842   1883       ** overflow pages contain the rest of the value.  
  1843   1884       **
  1844   1885       ** This expression uses sqlite4BtVarintLen32() to calculate an upper
  1845   1886       ** bound for the size of the varint that indicates the number of bytes
  1846   1887       ** of the value stored locally.  */
  1847   1888       nReq = 1 + sqlite4BtVarintLen32(pKV->nK) + pKV->nK 
  1848   1889            + 1 + sqlite4BtVarintLen32(pKV->nV) + nArraySz;
  1849         -    if( nReq<nMaxSize ){
         1890  +    if( nReq<nMaxSize && pKV->nV>=0 ){
  1850   1891         /* nSpc is initialized to the amount of space available to store:
  1851   1892         **
  1852   1893         **    * varint containing number of bytes stored locally (nLVal).
  1853   1894         **    * nLVal bytes of content.
  1854   1895         **    * varint containing number of bytes in overflow pages.
  1855   1896         */
  1856   1897         int nLVal;                  /* Bytes of value data on main page */
................................................................................
  1888   1929           *pOut++ = 0x00;
  1889   1930         }
  1890   1931         pOut += sqlite4BtVarintPut32(pOut, nLKey);
  1891   1932         memcpy(pOut, pKV->pK, nLKey);
  1892   1933         pOut += nLKey;
  1893   1934         if( nKeyOvfl==0 ){
  1894   1935           /* Type (b) cell */
         1936  +        assert( pKV->nV>=0 );
  1895   1937           *pOut++ = 0x00;
  1896   1938           pOut += sqlite4BtVarintPut32(pOut, nLVal);
  1897   1939           memcpy(pOut, pKV->pV, nLVal);
  1898   1940           pOut += nLVal;
  1899   1941         }else{
  1900   1942           /* Type (c) cell */
  1901   1943           pOut += sqlite4BtVarintPut32(pOut, nKeyOvfl);
  1902   1944         }
  1903   1945         pOut += sqlite4BtVarintPut32(pOut, nValOvfl + (nKeyOvfl>0));
  1904   1946   
  1905   1947         rc = btOverflowArrayPopulate(db, &pOut,
  1906   1948             (u8*)(pKV->pK) + nLKey, nKeyOvfl,
  1907         -          (u8*)(pKV->pV) + nLVal, nValOvfl
         1949  +          (u8*)(pKV->pV) + nLVal, MAX(0, nValOvfl)
  1908   1950         );
  1909   1951         if( rc==SQLITE4_OK ){
  1910   1952           memset(pKV, 0, sizeof(*pKV));
  1911   1953           pKV->pV = pBuf;
  1912   1954           pKV->nV = pOut - pBuf;
  1913   1955           pKV->eType = KV_CELL;
  1914   1956           pBuf = 0;
................................................................................
  2767   2809     }
  2768   2810   
  2769   2811     if( rc==SQLITE4_OK ){
  2770   2812       /* The cursor currently points to an entry with key pK/nK. This call
  2771   2813       ** should therefore replace that entry. So delete it and then re-seek
  2772   2814       ** the cursor.  */
  2773   2815       rc = sqlite4BtDelete(&csr.base);
  2774         -
  2775         -    if( rc==SQLITE4_OK && nV>=0 ){
         2816  +    if( rc==SQLITE4_OK && (nV>=0 || iRoot==0) ){
  2776   2817         rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, BT_CSRSEEK_UPDATE);
  2777   2818         if( rc==SQLITE4_OK ) rc = btErrorBkpt(SQLITE4_CORRUPT);
  2778   2819       }
  2779   2820     }
  2780   2821   
  2781         -  if( nV>=0 && (rc==SQLITE4_NOTFOUND || rc==SQLITE4_INEXACT ) ){
  2782         -    KeyValue kv;
  2783         -    kv.pgno = 0;
  2784         -    kv.eType = KV_VALUE;
  2785         -    kv.pK = pK; kv.nK = nK;
  2786         -    kv.pV = pV; kv.nV = nV;
  2787         -
  2788         -    rc = btOverflowAssign(db, &kv);
  2789         -    if( rc==SQLITE4_OK ){
  2790         -      do{
  2791         -        /* Insert the new KV pair into the current leaf. */
  2792         -        rc = btInsertAndBalance(&csr, 1, &kv);
  2793         -
  2794         -        /* Unless this is a block-full error, break out of the loop */
  2795         -        if( rc!=BT_BLOCKFULL ) break;
  2796         -        assert( iRoot==0 );
  2797         -
  2798         -        rc = btFastInsertRoot(db, pHdr, &iRootPg);
  2799         -        if( rc==SQLITE4_OK ){
  2800         -          btCsrReset(&csr, 1);
  2801         -          btCsrSetup(db, iRootPg, &csr);
  2802         -          rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, BT_CSRSEEK_UPDATE);
  2803         -        }
  2804         -      }while( rc==SQLITE4_NOTFOUND || rc==SQLITE4_INEXACT );
  2805         -    }
  2806         -
  2807         -    if( kv.eType==KV_CELL ){
  2808         -      sqlite4_free(db->pEnv, (void*)kv.pV);
         2822  +
         2823  +  if( rc==SQLITE4_NOTFOUND || rc==SQLITE4_INEXACT ){
         2824  +    if( nV<0 && iRoot!=0 ){
         2825  +      /* This is a delete on the regular b-tree (not the fast-insert tree).
         2826  +      ** Nothing more to do.  */
         2827  +      rc = SQLITE4_OK;
         2828  +    }else{
         2829  +      KeyValue kv;
         2830  +      kv.pgno = 0;
         2831  +      kv.eType = KV_VALUE;
         2832  +      kv.pK = pK; kv.nK = nK;
         2833  +      kv.pV = pV; kv.nV = nV;
         2834  +
         2835  +      rc = btOverflowAssign(db, &kv);
         2836  +      if( rc==SQLITE4_OK ){
         2837  +        do{
         2838  +          /* Insert the new KV pair into the current leaf. */
         2839  +          rc = btInsertAndBalance(&csr, 1, &kv);
         2840  +
         2841  +          /* Unless this is a block-full error, break out of the loop */
         2842  +          if( rc!=BT_BLOCKFULL ) break;
         2843  +          assert( iRoot==0 );
         2844  +
         2845  +          rc = btFastInsertRoot(db, pHdr, &iRootPg);
         2846  +          if( rc==SQLITE4_OK ){
         2847  +            btCsrReset(&csr, 1);
         2848  +            btCsrSetup(db, iRootPg, &csr);
         2849  +            rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, BT_CSRSEEK_UPDATE);
         2850  +          }
         2851  +        }while( rc==SQLITE4_NOTFOUND || rc==SQLITE4_INEXACT );
         2852  +      }
         2853  +
         2854  +      if( kv.eType==KV_CELL ){
         2855  +        sqlite4_free(db->pEnv, (void*)kv.pV);
         2856  +      }
  2809   2857       }
  2810   2858     }
  2811   2859   
  2812   2860     btCsrReset(&csr, 1);
  2813         -
  2814   2861     return rc;
  2815   2862   }
  2816   2863   
  2817   2864   static int btAllocateNewRoot(bt_db *db, u32 *piNew){
  2818   2865     u32 iNew = 0;
  2819   2866     BtPage *pPg;
  2820   2867     int rc;

Changes to www/bt.wiki.

   538    538   that use overflow pages for the value only, and (c) cells that use overflow
   539    539   pages for the key and value.
   540    540   
   541    541   <p>Cell type (a):
   542    542   <ul>
   543    543     <li> Number of bytes of the entries key (nKey), as a varint.
   544    544     <li> nKey bytes of key data.
   545         -  <li> Number of bytes in entries value plus one (nValue+2), as a varint. Or,
          545  +  <li> Number of bytes in entries value plus two (nValue+2), as a varint. Or,
   546    546          for a delete key, a single 0x01 byte.
   547    547     <li> Unless this is a delete key, nValue bytes of value data.
   548    548   </ul>
   549    549   
   550    550   <p>Cell type (b):
   551    551   <ul>
   552    552     <li> Number of bytes in entries key (nKey), as a varint.