This article mainly describes the implementation principle of vearch's range index. When vearch is building a table, it supports the establishment of a range index for non-vector fields. When Vearch performs a vector search, it will first call the range filter and output the doc that meets the filter conditions into a bitmap for The next vector search is used.

1. The LSM tree saves the modified increments of the data in the memory. After the specified size limit is reached, the data is flushed to the disk in batches. The trees in the disk can be merged into a large tree regularly to optimize the read performance. The range index is developed based on the LSM tree.
2. Sparse nodes and dense nodes: There are two storage methods for range indexes. Sparse nodes are implemented by arrays to store fields with low repetitiveness, and dense nodes are implemented by bitmap to store fields with high repetitiveness.
3. Sparse nodes and dense nodes can be converted to each other. When the field data density of a dense node drops to a threshold, it will be converted to a sparse node, and when the density of a sparse node reaches the threshold, it will be converted to a dense node.
4. Byte order, the nodes stored in the range index are stored in big-endian order, so the numeric type needs to be converted from little-endian to big-endian, and the string type does not need to be converted.
5. Numeric type index is used for range query, string type index is also called label index, used for single point query

int AddField(int field, enum DataType field_type)

In order not to block the main thread insert operation, the range index is inserted asynchronously

The dense node uses bitmap to store the docid. 1 byte can store up to 8 docids, aligned according to 64. During the insertion process, if the data density (max-min) / size <0.08, the node will be converted to a sparse node

The sparse node uses an array to store the docid, capacity is the capacity of the array, and size is the number of elements in the array. During the insertion process, if the data density (max-min) / size> 0.1, the node will be converted to a dense node

The density of the mutual conversion between sparse nodes and dense nodes is 0.1 and 0.08. The reason why they are set to be different is to prevent frequent conversion between the two during the insertion process.

BM_OPERATE_TYPE *op_data_dst = (BM_OPERATE_TYPE *)bitmap;
BM_OPERATE_TYPE *op_data_ori = (BM_OPERATE_TYPE *)data;
int offset = (min - min_aligned) / op_len;
for (int j = 0; j < (max - min + 1) / op_len; ++j) {
  op_data_dst[j + offset] |= op_data_ori[j];
}

The final output result of range filtering is a bitmap. If the result to be merged is a dense node, the node stores a bitmap. Set the operation step size to sizeof(BM_OPERATE_TYPE) * 8, and BM_OPERATE_TYPE to long, so the actual step size is 8 * 8 = 64, that is, 64 elements are copied each time. Because the content of the loop is very simple and the compiler is optimized at the O3 level, the for loop will automatically expand, and a large number of elements can be copied every CPU cycle

for (int i = 0; i < j; ++i) {
  if (i == shortest_idx) {
    continue;
  }
  char *data = results[i].Ref();
  BM_OPERATE_TYPE *op_data_ori = (BM_OPERATE_TYPE *)data;
  int min = results[i].MinAligned();
  int max = results[i].MaxAligned();

  if (min < min_doc) {
    int offset = (min_doc - min) / op_len;
    if (max > max_doc) {
      for (int k = 0; k < (max_doc - min_doc + 1) / op_len; ++k) {
        op_data_dst[k] &= op_data_ori[k + offset];
      }
    } else {
      for (int k = 0; k < (max - min_doc + 1) / op_len; ++k) {
        op_data_dst[k] &= op_data_ori[k + offset];
      }
    }
  } else {
    int offset = (min - min_doc) / op_len;
    if (max > max_doc) {
      for (int k = 0; k < (max_doc - min_doc + 1) / op_len; ++k) {
        op_data_dst[k + offset] &= op_data_ori[k];
      }
    } else {
      for (int k = 0; k < (max - min_doc + 1) / op_len; ++k) {
        op_data_dst[k + offset] &= op_data_ori[k];
      }
    }
  }
}

When multiple results are intersected, first select the shortest bitmap, and then intersect with other bitmaps accordingly. The operation step is 64. Pay attention to the alignment of the results

Execute unset directly in bitmap

Traverse the array, find the node, and overwrite the previous nodes in turn