SQLite4  Check-in [03f26d8c60]

**
*************************************************************************
*/

#include "sqliteInt.h"
#include "vdbeInt.h"

/*
** The global count record is a set of N varints, where N is one greater
** than the number of columns in the indexed table. The first varint
** contains the number of records in the table. Each subsequent varint
** contains the total number of tokens stored in each column.
**
** The key used for the global record in the KV store is the root page 
** number of the FTS index followed by a single 0x00 byte.
*/

/*
** Default distance value for NEAR operators.
*/
#define FTS5_DEFAULT_NEAR 10

/*
** Token types used by expression parser.

  Fts5ExprNode *pRight;
  const u8 *aPk;                  /* Primary key of current entry (or null) */
  int nPk;                        /* Size of aPk[] in bytes */
};

struct Fts5Expr {
  Fts5ExprNode *pRoot;

  int nPhrase;                    /* Number of Fts5Str objects in query */
  Fts5Str **apPhrase;             /* All Fts5Str objects */
};

/*
** FTS5 specific cursor data.
*/
struct Fts5Cursor {
  sqlite4 *db;
  Fts5Info *pInfo;
  Fts5Expr *pExpr;                /* MATCH expression for this cursor */
  char *zExpr;                    /* Full text of MATCH expression */
  KVByteArray *aKey;              /* Buffer for primary key */
  int nKeyAlloc;                  /* Bytes allocated at aKey[] */

  KVCursor *pCsr;                 /* Cursor used to retrive values */
  Mem *aMem;                      /* Array of column values */

  /* Array of nPhrase*nCol integers. See sqlite4_mi_row_count() for details. */
  int *anRow;
  i64 *aGlobal;
};

/*
** This type is used when reading (decoding) an instance-list.
*/
typedef struct InstanceList InstanceList;
struct InstanceList {

typedef struct TokenizeCtx TokenizeCtx;
typedef struct TokenizeTerm TokenizeTerm;
struct TokenizeCtx {
  int rc;
  int iCol;
  sqlite4 *db;
  int nMax;
  int *aSz;                       /* Number of tokens in each column */
  Hash hash;
};
struct TokenizeTerm {
  int iWeight;                    /* Weight of previous entry */
  int iCol;                       /* Column containing previous entry */
  int iOff;                       /* Token offset of previous entry */
  int nToken;                     /* Size of token in bytes */

  int nSrc
){
  TokenizeCtx *p = (TokenizeCtx *)pCtx;
  TokenizeTerm *pTerm = 0;
  TokenizeTerm *pOrig = 0;

  if( nToken>p->nMax ) p->nMax = nToken;
  p->aSz[p->iCol]++;

  pTerm = (TokenizeTerm *)sqlite4HashFind(&p->hash, zToken, nToken);
  if( pTerm==0 ){
    /* Size the initial allocation so that it fits in the lookaside buffer */
    int nAlloc = sizeof(TokenizeTerm) + nToken + 32;

    pTerm = sqlite4DbMallocZero(p->db, nAlloc);

  if( !pTerm ){
    p->rc = SQLITE4_NOMEM;
    return 1;
  }

  return 0;
}

static int fts5LoadGlobal(sqlite4 *db, Fts5Info *pInfo, i64 *aVal){
  int rc;
  int nVal = pInfo->nCol + 1;
  u8 aKey[10];                    /* Global record key */
  int nKey;                       /* Bytes in key aKey */
  KVCursor *pCsr = 0;             /* Cursor used to read global record */

  nKey = putVarint32(aKey, pInfo->iRoot);
  aKey[nKey++] = 0x00;

  rc = sqlite4KVStoreOpenCursor(db->aDb[pInfo->iDb].pKV, &pCsr);
  if( rc==SQLITE4_OK ){
    rc = sqlite4KVCursorSeek(pCsr, aKey, nKey, 0);
    if( rc==SQLITE4_NOTFOUND ){
      rc = SQLITE4_OK;
      memset(aVal, 0, sizeof(i64)*nVal);
    }else if( rc==SQLITE4_OK ){
      const u8 *aData = 0;
      int nData = 0;
      rc = sqlite4KVCursorData(pCsr, 0, -1, &aData, &nData);
      if( rc==SQLITE4_OK ){
        int i;
        int iOff = 0;
        for(i=0; i<nVal; i++){
          iOff += sqlite4GetVarint(&aData[iOff], (u64 *)&aVal[i]);
        }
      }
    }
    sqlite4KVCursorClose(pCsr);
  }

  return rc;
}

static int fts5CsrLoadGlobal(Fts5Cursor *pCsr){
  int rc = SQLITE4_OK;
  if( pCsr->aGlobal==0 ){
    int nByte = sizeof(i64) * (pCsr->pInfo->nCol + 1);
    pCsr->aGlobal = (i64 *)sqlite4DbMallocZero(pCsr->db, nByte);
    if( pCsr->aGlobal==0 ){
      rc = SQLITE4_NOMEM;
    }else{
      rc = fts5LoadGlobal(pCsr->db, pCsr->pInfo, pCsr->aGlobal);
    }
  }
  return rc;
}


/*
** Update an fts index.
*/
int sqlite4Fts5Update(
  sqlite4 *db,                    /* Database handle */
  Fts5Info *pInfo,                /* Description of fts index to update */

  pPK = (const u8 *)sqlite4_value_blob(pKey);
  nPK = sqlite4_value_bytes(pKey);
  
  nTnum = getVarint32(pPK, dummy);
  nPK -= nTnum;
  pPK += nTnum;

  sCtx.aSz = (int *)sqlite4DbMallocZero(db, pInfo->nCol * sizeof(int));
  if( sCtx.aSz==0 ) rc = SQLITE4_NOMEM;

  for(i=0; rc==SQLITE4_OK && i<pInfo->nCol; i++){
    sqlite4_value *pArg = (sqlite4_value *)(&aArg[i]);
    if( pArg->flags & MEM_Str ){
      const char *zText;
      int nText;

      zText = (const char *)sqlite4_value_text(pArg);
      nText = sqlite4_value_bytes(pArg); 
      sCtx.iCol = i;
      rc = pInfo->pTokenizer->xTokenize(
          &sCtx, pInfo->p, zText, nText, fts5TokenizeCb
      );
    }
  }

  nKey = sqlite4VarintLen(pInfo->iRoot)+2+sCtx.nMax+nPK + 10*(pInfo->nCol+1);
  aKey = sqlite4DbMallocRaw(db, nKey);
  if( aKey==0 ) rc = SQLITE4_NOMEM;

  for(pElem=sqliteHashFirst(&sCtx.hash); pElem; pElem=sqliteHashNext(pElem)){
    TokenizeTerm *pTerm = (TokenizeTerm *)sqliteHashData(pElem);
    if( rc==SQLITE4_OK ){
      int nToken = sqliteHashKeysize(pElem);

        const KVByteArray *aData = (const KVByteArray *)&pTerm[1];
        aData += pTerm->nToken;
        rc = sqlite4KVStoreReplace(pStore, aKey, nKey, aData, pTerm->nData);
      }
    }
    sqlite4DbFree(db, pTerm);
  }

  /* Write the "sizes" record into the db */
  if( rc==SQLITE4_OK ){
    nKey = putVarint32(aKey, pInfo->iRoot);
    aKey[nKey++] = 0x00;
    memcpy(&aKey[nKey], pPK, nPK);
    nKey += nPK;

    if( bDel ){
      rc = sqlite4KVStoreReplace(pStore, aKey, nKey, 0, -1);
    }else{
      u8 *aData = &aKey[nKey];
      int nData = 0;
      for(i=0; i<pInfo->nCol; i++){
        nData += putVarint32(&aData[nData], sCtx.aSz[i]);
      }
      rc = sqlite4KVStoreReplace(pStore, aKey, nKey, aData, nData);
    }
  }

  /* Update the global record */
  if( rc==SQLITE4_OK ){
    i64 *aGlobal = (i64 *)aKey;
    u8 *aData = (u8 *)&aGlobal[pInfo->nCol+1];
    int nData = 0;

    rc = fts5LoadGlobal(db, pInfo, aGlobal);
    if( rc==SQLITE4_OK ){
      u8 aDbKey[10];
      int nDbKey;
      nDbKey = putVarint32(aDbKey, pInfo->iRoot);
      aDbKey[nDbKey++] = 0x00;

      nData += sqlite4PutVarint(&aData[nData], aGlobal[0] + (bDel?-1:1));
      for(i=0; i<pInfo->nCol; i++){
        i64 iNew = aGlobal[i+1] + (i64)sCtx.aSz[i] * (bDel?-1:1);
        nData += sqlite4PutVarint(&aData[nData], iNew);
      }

      rc = sqlite4KVStoreReplace(pStore, aDbKey, nDbKey, aData, nData);
    }
  }
  
  sqlite4DbFree(db, aKey);
  sqlite4DbFree(db, sCtx.aSz);
  sqlite4HashClear(&sCtx.hash);
  return rc;
}

static Fts5Info *fts5InfoCreate(Parse *pParse, Index *pIdx, int bCol){
  sqlite4 *db = pParse->db;
  Fts5Info *pInfo;                /* p4 argument for FtsUpdate opcode */

  return fts5OpenExprCursors(db, pInfo, pCsr->pExpr->pRoot);
}

void sqlite4Fts5Close(sqlite4 *db, Fts5Cursor *pCsr){
  if( pCsr ){
    fts5ExpressionFree(db, pCsr->pExpr);
    sqlite4DbFree(db, pCsr->aKey);
    sqlite4DbFree(db, pCsr->anRow);
    sqlite4DbFree(db, pCsr);
  }
}

static int fts5TokenAdvanceToMatch(
  InstanceList *p,
  InstanceList *pFirst,

  const char *zMatch,             /* Match expression */
  int bDesc,                      /* True to iterate in desc. order of PK */
  Fts5Cursor **ppCsr,             /* OUT: New FTS cursor object */
  char **pzErr                    /* OUT: Error message */
){
  int rc = SQLITE4_OK;
  Fts5Cursor *pCsr;
  int nMatch = sqlite4Strlen30(zMatch);

  pCsr = sqlite4DbMallocZero(db, sizeof(Fts5Cursor) + nMatch + 1);

  if( !pCsr ){
    rc = SQLITE4_NOMEM;
  }else{
    pCsr->zExpr = (char *)&pCsr[1];
    memcpy(pCsr->zExpr, nMatch, zMatch);
    pCsr->pInfo = pInfo;
    pCsr->db = db;
    rc = fts5ParseExpression(db, pInfo->pTokenizer, pInfo->p, 
        pInfo->iRoot, pInfo->azCol, pInfo->nCol, zMatch, &pCsr->pExpr, pzErr
    );
  }

  int iPhrase, 
  int iMatch, 
  int *piOff
){
}

int sqlite4_mi_total_match_count(
  sqlite4_context *pCtx,
  int iCol,
  int iPhrase,
  int *pnMatch,
  int *pnDoc,
  int *pnRelevant
){
}

int sqlite4_mi_total_size(sqlite4_context *pCtx, int iCol, int *pnToken){
  int rc = SQLITE4_OK;
  if( pCtx->pFts ){
    Fts5Cursor *pCsr = pCtx->pFts;
    int nCol = pCsr->pInfo->nCol;

    if( iCol>=nCol ){
      rc = SQLITE4_ERROR;
    }else{
      rc = fts5CsrLoadGlobal(pCsr);
      if( rc==SQLITE4_OK ){
        if( iCol<0 ){
          int i;
          int nToken = 0;
          for(i=0; i<nCol; i++){
            nToken += pCsr->aGlobal[i+1];
          }
          *pnToken = nToken;
        }else{
          *pnToken = pCsr->aGlobal[iCol+1];
        }
      }
    }
  }else{
    rc = SQLITE4_MISUSE;
  }
  return rc;
}

static int fts5CsrLoadRowcounts(Fts5Cursor *pCsr){
  if( pCsr->anRow==0 ){
    Fts5Expr *pExpr = pCsr->pExpr;
    Fts5Info *pInfo = pCsr->pInfo;
    int *anRow;

    pCsr->anRow = anRow = (int *)sqlite4DbMallocZero(pCsr->db, 
        pExpr->nPhrase * pInfo->nCol * sizeof(int)
    );
    if( !anRow ) return SQLITE4_NOMEM;

  }
}

int sqlite4_mi_row_count(
  sqlite4_context *pCtx,          /* Context object passed to mi function */
  int iCol,                       /* Specific column (or -1) */
  int iPhrase,                    /* Specific phrase (or -1) */
  int *pnRow                      /* Total number of rows */
){
  int rc = SQLITE4_OK;
  if( pCtx->pFts ){
    Fts5Cursor *pCsr = pCtx->pFts;
    Fts5Expr *pExpr = pCsr->pExpr;
    int nCol = pCsr->pInfo->nCol;
    int nPhrase = pExpr->nPhrase;

    if( iCol>=nCol || iPhrase>=nPhrase ){
      rc = SQLITE4_ERROR;
    }

    else if( iPhrase>=0 ){
      int iIdx = iPhrase * pCsr->pInfo->nCol;

      rc = fts5CsrLoadRowcounts(pCsr);
      if( rc==SQLITE4_OK ){
        if( iCol>0 ){
          *pnRow = pCsr->anRow[iIdx + iCol];
        }else{
          int i;
          int nRow = 0;
          for(i=0; i<pCsr->pInfo->nCol; i++){
            nRow += pCsr->anRow[iIdx + i];
          }
          *pnRow = nRow;
        }
      }
    }else{
      /* Total number of rows in table... */
      rc = fts5CsrLoadGlobal(pCsr);
      if( rc==SQLITE4_OK ){
        *pnRow = (int)pCsr->aGlobal[0];
      }
    }
  }else{
    rc = SQLITE4_MISUSE;
  }
  return rc;
}

/**************************************************************************
***************************************************************************
** Below this point is test code.
*/
#ifdef SQLITE4_TEST

/*
** 2012 December 17
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
*/

/*
** BM25 and BM25F references:
**
**   Stephen Robertson and Hugo Zaragoza: "The Probablistic Relevance
**   Framework: BM25 and Beyond", 2009.
**
**   http://xapian.org/docs/bm25.html
**
**   http://en.wikipedia.org/wiki/Okapi_BM25
*/

#include "sqliteInt.h"

static char fts5Tolower(char c){
  if( c>='A' && c<='Z' ) c = c + ('a' - 'A');
  return c;
}

  return SQLITE4_OK;
}

static int fts5SimpleDestroy(sqlite4_tokenizer *p){
  return SQLITE4_OK;
}

typedef struct Fts5RankCtx Fts5RankCtx;
struct Fts5RankCtx {
  sqlite4 *db;
  double avgdl;                   /* Average document size in tokens */
  int nPhrase;                    /* Number of phrases in query */
  double *aIdf;                   /* IDF weights for each phrase in query */
};

static void fts5RankFreeCtx(void *pCtx){
  if( pCtx ){
    Fts5RankCtx *p = (Fts5RankCtx *)pCtx;
    sqlite4DbFree(p->db, p);
  }
}

/*
** A BM25 based ranking function for fts5.
**
** This is based on the information in the Robertson/Zaragoza paper 
** referenced above. As there is no way to provide relevance feedback 
** IDF weights (equation 3.3 in R/Z) are used instead of RSJ for each phrase.
** The rest of the implementation is as presented in equation 3.15.
**
** R and Z observe that the experimental evidence suggests that reasonable
** values for free parameters "b" and "k1" are often in the ranges 
** (0.5 < b < 0.8) and (1.2 < k1 < 2), although the optimal values depend
** on the nature of both the documents and queries. The implementation
** below sets each parameter to the midpoint of the suggested range.
*/
static void fts5Rank(sqlite4_context *pCtx, int nArg, sqlite4_value **apArg){
  const double b = 0.65;
  const double k1 = 1.6;

  int rc = SQLITE4_OK;            /* Error code */
  Fts5RankCtx *p;                 /* Structure to store reusable values */
  int i;                          /* Used to iterate through phrases */
  double rank = 0.0;              /* UDF return value */

  p = sqlite4_get_auxdata(pCtx, 0);
  if( p==0 ){
    sqlite4 *db = sqlite4_context_db_handle(pCtx);
    int nPhrase;                  /* Number of phrases in query expression */
    int nByte;                    /* Number of bytes of data to allocate */

    sqlite4_mi_phrase_count(pCtx, &nPhrase);
    nByte = sizeof(Fts5RankCtx) + nPhrase * sizeof(double);
    p = (Fts5RankCtx *)sqlite4DbMallocZero(db, nByte);
    sqlite4_set_auxdata(pCtx, 0, (void *)p, fts5RankFreeCtx);
    p = sqlite4_get_auxdata(pCtx, 0);

    if( !p ){
      rc = SQLITE4_NOMEM;
    }else{
      int N;                      /* Total number of docs in collection */
      int ni;                     /* Number of docs with phrase i */

      p->db = db;
      p->nPhrase = nPhrase;
      p->aIdf = (double *)&p[1];

      /* Determine the IDF weight for each phrase in the query. */
      rc = sqlite4_mi_row_count(pCtx, -1, -1, &N);
      for(i=0; rc==SQLITE4_OK && i<nPhrase; i++){
        rc = sqlite4_mi_row_count(pCtx, -1, i, &ni);
        if( rc==SQLITE4_OK ){
          p->aIdf[i] = log((0.5 + N - ni) / (0.5 + ni));
        }
      }

      /* Determine the average document length */
      if( rc==SQLITE4_OK ){
        int nTotal;
        rc = sqlite4_mi_total_size(pCtx, -1, &nTotal);
        if( rc==SQLITE4_OK ){
          p->avgdl = (double)nTotal / (double)N;
        }
      }
    }
  }

  for(i=0; rc==SQLITE4_OK && i<p->nPhrase; i++){
    int tf;                     /* Occurences of phrase i in row (term freq.) */
    int dl;                     /* Tokens in this row (document length) */
    double L;                   /* Normalized document length */
    double prank;               /* Contribution to rank of this phrase */

    /* Set variable tf to the total number of occurrences of phrase iPhrase
    ** in this row (within any column). And dl to the number of tokens in
    ** the current row (again, in any column).  */
    rc = sqlite4_mi_match_count(pCtx, -1, i, &tf); 
    if( rc==SQLITE4_OK ) rc = sqlite4_mi_column_size(pCtx, -1, &dl); 

    /* Calculate the normalized document length */
    L = (double)dl / p->avgdl;

    /* Calculate the contribution to the rank made by this phrase. Then
    ** add it to variable rank.  */
    prank = (p->aIdf[i] * tf) / (k1 * ( (1.0 - b) + b * L) + tf);
    rank += prank;
  }

  if( rc==SQLITE4_OK ){
    sqlite4_result_double(pCtx, rank);
  }else{
    sqlite4_result_error_code(pCtx, rc);
  }
}

static void fts5Snippet(sqlite4_context *pCtx, int nArg, sqlite4_value **apArg){
}

static int fts5SimpleTokenize(
  void *pCtx, 

**   of range (i.e. too large) it is not an error. In this case *piOff is 
**   set to -1 before returning.
**   
** sqlite4_mi_total_size():
**   Set *pnToken to the total number of tokens in column iCol of all rows
**   in the indexed table.
**
** sqlite4_mi_row_count():
**   If parameter iPhrase is negative, this function sets the output 
**   parameter to the total number of documents in the collection (rows 
**   in the indexed table).
**
**   Otherwise, if iPhrase is not negative, then the output is set to the
**   total number of rows that contain at least one instance of phrase iPhrase
**   in column iCol, or in any column if iCol is negative.
**
**   If parameter iPhrase is equal to or greater than the number of phrases
**   in the current query, or if iCol is equal to or greater than the number
**   of columns in the indexed table, SQLITE4_MISUSE is returned. The value
**   of the output parameter is undefined in this case.
*/
int sqlite4_mi_column_count(sqlite4_context *, int *pnCol);
int sqlite4_mi_column_size(sqlite4_context *, int iCol, int *pnToken);
int sqlite4_mi_column_value(sqlite4_context *, int iCol, sqlite4_value **ppVal);

int sqlite4_mi_phrase_count(sqlite4_context *, int *pnPhrase);

int sqlite4_mi_match_count(sqlite4_context *, int iCol, int iPhrase, int *pn);
int sqlite4_mi_match_detail(sqlite4_context *, 
    int iCol, int iPhrase, int iMatch, int *piOff, int *piWeight
); 



int sqlite4_mi_total_size(sqlite4_context *, int iCol, int *pnToken);
int sqlite4_mi_row_count(sqlite4_context *, int iCol, int iPhrase, int *pnRow);

/*
** Undo the hack that converts floating point types to integer for
** builds on processors without floating point support.
*/
#ifdef SQLITE4_OMIT_FLOATING_POINT
# undef double