Implement Index

[kawasin73]

• [x] sqlite_schema index support #8
  • CREATE INDEX sql syntax : https://www.sqlite.org/lang_createindex.html
• [x] Single integer column index with WHERE <index_column> = <integer>
• [x] Type Conversions Prior To Comparison #7
  • https://www.sqlite.org/datatype3.html#type_conversions_prior_to_comparison
• [x] Collating Sequences for string comparison #23
  • https://www.sqlite.org/datatype3.html#collating_sequences
• [x] Multiple columns index
• [ ] autoindex from PRIMARY KEY support
• [ ] ORDER BY with index support

[kawasin73]

Btree cursor

• MoveTo is separated functions.

https://github.com/sqlite/sqlite/blob/cbaef88980f48c963da8788faadd429b64d72dca/src/btree.h#L250C1-L260C3

int sqlite3BtreeTableMoveto(
  BtCursor*,
  i64 intKey,
  int bias,
  int *pRes
);
int sqlite3BtreeIndexMoveto(
  BtCursor*,
  UnpackedRecord *pUnKey,
  int *pRes
);

next, previous is resued for both index and table pages.

[kawasin73]

Schema

index is stored in Schema.idxHash

struct Schema {
  int schema_cookie;   /* Database schema version number for this file */
  int iGeneration;     /* Generation counter.  Incremented with each change */
  Hash tblHash;        /* All tables indexed by name */
  Hash idxHash;        /* All (named) indices indexed by name */
  Hash trigHash;       /* All triggers indexed by name */
  Hash fkeyHash;       /* All foreign keys by referenced table name */
  Table *pSeqTab;      /* The sqlite_sequence table used by AUTOINCREMENT */
  u8 file_format;      /* Schema format version for this file */
  u8 enc;              /* Text encoding used by this database */
  u16 schemaFlags;     /* Flags associated with this schema */
  int cache_size;      /* Number of pages to use in the cache */
};

Index is created at sqlite3CreateIndex() in build.c

      p = sqlite3HashInsert(&pIndex->pSchema->idxHash, 
          pIndex->zName, pIndex);

  if( db->init.busy || pTblName==0 ){
    pIndex->pNext = pTab->pIndex;
    pTab->pIndex = pIndex;
    pIndex = 0;
  }

Table also holds the list of index. index itself is linked list.

struct Table {
  char *zName;         /* Name of the table or view */
  Column *aCol;        /* Information about each column */
  Index *pIndex;       /* List of SQL indexes on this table. */

/*
** Each SQL index is represented in memory by an
** instance of the following structure.
**
** The columns of the table that are to be indexed are described
** by the aiColumn[] field of this structure.  For example, suppose
** we have the following table and index:
**
**     CREATE TABLE Ex1(c1 int, c2 int, c3 text);
**     CREATE INDEX Ex2 ON Ex1(c3,c1);
**
** In the Table structure describing Ex1, nCol==3 because there are
** three columns in the table.  In the Index structure describing
** Ex2, nColumn==2 since 2 of the 3 columns of Ex1 are indexed.
** The value of aiColumn is {2, 0}.  aiColumn[0]==2 because the
** first column to be indexed (c3) has an index of 2 in Ex1.aCol[].
** The second column to be indexed (c1) has an index of 0 in
** Ex1.aCol[], hence Ex2.aiColumn[1]==0.
**
** The Index.onError field determines whether or not the indexed columns
** must be unique and what to do if they are not.  When Index.onError=OE_None,
** it means this is not a unique index.  Otherwise it is a unique index
** and the value of Index.onError indicates which conflict resolution
** algorithm to employ when an attempt is made to insert a non-unique
** element.
**
** The colNotIdxed bitmask is used in combination with SrcItem.colUsed
** for a fast test to see if an index can serve as a covering index.
** colNotIdxed has a 1 bit for every column of the original table that
** is *not* available in the index.  Thus the expression
** "colUsed & colNotIdxed" will be non-zero if the index is not a
** covering index.  The most significant bit of of colNotIdxed will always
** be true (note-20221022-a).  If a column beyond the 63rd column of the
** table is used, the "colUsed & colNotIdxed" test will always be non-zero
** and we have to assume either that the index is not covering, or use
** an alternative (slower) algorithm to determine whether or not
** the index is covering.
**
** While parsing a CREATE TABLE or CREATE INDEX statement in order to
** generate VDBE code (as opposed to parsing one read from an sqlite_schema
** table as part of parsing an existing database schema), transient instances
** of this structure may be created. In this case the Index.tnum variable is
** used to store the address of a VDBE instruction, not a database page
** number (it cannot - the database page is not allocated until the VDBE
** program is executed). See convertToWithoutRowidTable() for details.
*/
struct Index {
  char *zName;             /* Name of this index */
  i16 *aiColumn;           /* Which columns are used by this index.  1st is 0 */
  LogEst *aiRowLogEst;     /* From ANALYZE: Est. rows selected by each column */
  Table *pTable;           /* The SQL table being indexed */
  char *zColAff;           /* String defining the affinity of each column */
  Index *pNext;            /* The next index associated with the same table */
  Schema *pSchema;         /* Schema containing this index */
  u8 *aSortOrder;          /* for each column: True==DESC, False==ASC */
  const char **azColl;     /* Array of collation sequence names for index */
  Expr *pPartIdxWhere;     /* WHERE clause for partial indices */
  ExprList *aColExpr;      /* Column expressions */
  Pgno tnum;               /* DB Page containing root of this index */
  LogEst szIdxRow;         /* Estimated average row size in bytes */
  u16 nKeyCol;             /* Number of columns forming the key */
  u16 nColumn;             /* Number of columns stored in the index */
  u8 onError;              /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
  unsigned idxType:2;      /* 0:Normal 1:UNIQUE, 2:PRIMARY KEY, 3:IPK */
  unsigned bUnordered:1;   /* Use this index for == or IN queries only */
  unsigned uniqNotNull:1;  /* True if UNIQUE and NOT NULL for all columns */
  unsigned isResized:1;    /* True if resizeIndexObject() has been called */
  unsigned isCovering:1;   /* True if this is a covering index */
  unsigned noSkipScan:1;   /* Do not try to use skip-scan if true */
  unsigned hasStat1:1;     /* aiRowLogEst values come from sqlite_stat1 */
  unsigned bNoQuery:1;     /* Do not use this index to optimize queries */
  unsigned bAscKeyBug:1;   /* True if the bba7b69f9849b5bf bug applies */
  unsigned bHasVCol:1;     /* Index references one or more VIRTUAL columns */
  unsigned bHasExpr:1;     /* Index contains an expression, either a literal
                           ** expression, or a reference to a VIRTUAL column */
#ifdef SQLITE_ENABLE_STAT4
  int nSample;             /* Number of elements in aSample[] */
  int nSampleCol;          /* Size of IndexSample.anEq[] and so on */
  tRowcnt *aAvgEq;         /* Average nEq values for keys not in aSample */
  IndexSample *aSample;    /* Samples of the left-most key */
  tRowcnt *aiRowEst;       /* Non-logarithmic stat1 data for this index */
  tRowcnt nRowEst0;        /* Non-logarithmic number of rows in the index */
#endif
  Bitmask colNotIdxed;     /* Unindexed columns in pTab */
};

[kawasin73]

Value Comparison

https://www.sqlite.org/datatype3.html#comparison_expressions

Ord ? PartialOrd?

• NULL < INTEGER|REAL < TEXT|BLOB

sqlite does not accept NaN. If a serialized value is NaN, it is interpreted as NULL.

pMem->flags = IsNaN(x) ? MEM_Null : MEM_Real;

https://github.com/sqlite/sqlite/blob/038ac625afbc0a67c5ac9d5a9c780e8a28391baa/src/vdbeaux.c#L4050

also sqlite3IsNaN() is used to assert that read number is not NaN.

/// https://www.sqlite.org/datatype3.html#comparison_expressions
#[derive(Debug)]
pub enum CompareValue<'a> {
    IsNull,
    IsNotNull,
    Integer(i64),
    Float(f64),
    /// BINARY collating function. This is compatible to memcmp.
    Binary(&'a [u8]),
    // TODO: other collating functions NOCASE, RTRIM
}

impl CompareValue<'_> {
    fn partial_cmp(&self, other: &Value) -> Option<Ordering> {
        match *self {
            CompareValue::IsNull => {
                if matches!(other, Value::Null) {
                    Some(Ordering::Equal)
                } else {
                    Some(Ordering::Less)
                }
            }
            CompareValue::IsNotNull => {
                if matches!(other, Value::Null) {
                    Some(Ordering::Greater)
                } else {
                    Some(Ordering::Equal)
                }
            }
            CompareValue::Integer(v1) => match other {
                Value::Null => Some(Ordering::Greater),
                Value::Integer(v2) => Some(v1.cmp(v2)),
                Value::Real(v2) => (v1 as f64).partial_cmp(v2),
                _ => Some(Ordering::Less),
            },
            CompareValue::Float(v1) => match other {
                Value::Null => Some(Ordering::Greater),
                Value::Integer(v2) => v1.partial_cmp(&(*v2 as f64)),
                Value::Real(v2) => v1.partial_cmp(v2),
                _ => Some(Ordering::Less),
            },
            CompareValue::Binary(v1) => match other {
                _ => Some(Ordering::Greater),
                Value::Blob(v2) => Some(v1.cmp(v2)),
                Value::Text(v2) => Some(v1.cmp(&v2.as_bytes())),
            },
        }
    }
}

OP_Compare

vdbe.c

/* Opcode: Compare P1 P2 P3 P4 P5
** Synopsis: r[P1@P3] <-> r[P2@P3]
**
** Compare two vectors of registers in reg(P1)..reg(P1+P3-1) (call this
** vector "A") and in reg(P2)..reg(P2+P3-1) ("B").  Save the result of
** the comparison for use by the next OP_Jump instruct.
**
** If P5 has the OPFLAG_PERMUTE bit set, then the order of comparison is
** determined by the most recent OP_Permutation operator.  If the
** OPFLAG_PERMUTE bit is clear, then register are compared in sequential
** order.
**
** P4 is a KeyInfo structure that defines collating sequences and sort
** orders for the comparison.  The permutation applies to registers
** only.  The KeyInfo elements are used sequentially.
**
** The comparison is a sort comparison, so NULLs compare equal,
** NULLs are less than numbers, numbers are less than strings,
** and strings are less than blobs.
**
** This opcode must be immediately followed by an OP_Jump opcode.
*/

  for(i=0; i<n; i++){
    idx = aPermute ? aPermute[i] : (u32)i;
    pColl = pKeyInfo->aColl[i];
    bRev = (pKeyInfo->aSortFlags[i] & KEYINFO_ORDER_DESC);
    iCompare = sqlite3MemCompare(&aMem[p1+idx], &aMem[p2+idx], pColl);

• sqlite3MemCompare()

vdbeaux.c

/*
** Compare the values contained by the two memory cells, returning
** negative, zero or positive if pMem1 is less than, equal to, or greater
** than pMem2. Sorting order is NULL's first, followed by numbers (integers
** and reals) sorted numerically, followed by text ordered by the collating
** sequence pColl and finally blob's ordered by memcmp().
**
** Two NULL values are considered equal by this function.
*/
int sqlite3MemCompare(const Mem *pMem1, const Mem *pMem2, const CollSeq *pColl){