kaivalnp commented on code in PR #14178:
URL: https://github.com/apache/lucene/pull/14178#discussion_r1941904975


##########
lucene/sandbox/src/java22/org/apache/lucene/sandbox/codecs/faiss/LibFaissC.java:
##########
@@ -0,0 +1,268 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.sandbox.codecs.faiss;
+
+import static java.lang.foreign.ValueLayout.ADDRESS;
+import static java.lang.foreign.ValueLayout.JAVA_FLOAT;
+import static java.lang.foreign.ValueLayout.JAVA_INT;
+import static java.lang.foreign.ValueLayout.JAVA_LONG;
+
+import java.lang.foreign.Arena;
+import java.lang.foreign.FunctionDescriptor;
+import java.lang.foreign.Linker;
+import java.lang.foreign.MemoryLayout;
+import java.lang.foreign.MemorySegment;
+import java.lang.foreign.SymbolLookup;
+import java.lang.invoke.MethodHandle;
+import java.nio.ByteOrder;
+import java.nio.FloatBuffer;
+import java.util.Locale;
+import org.apache.lucene.index.FloatVectorValues;
+import org.apache.lucene.index.KnnVectorValues;
+import org.apache.lucene.index.VectorSimilarityFunction;
+import org.apache.lucene.search.KnnCollector;
+import org.apache.lucene.util.Bits;
+
+public final class LibFaissC {
+  public static final String LIBRARY_VERSION = "1.9.0";
+
+  static {
+    try {
+      System.loadLibrary("faiss_c");
+    } catch (UnsatisfiedLinkError e) {
+      throw new RuntimeException(
+          "Shared library not found, build the Faiss C_API from 
https://github.com/facebookresearch/faiss/blob/main/c_api/INSTALL.md "
+              + "and link it (along with all dependencies) to the library path 
"
+              + "(-Djava.library.path JVM argument or $LD_LIBRARY_PATH 
environment variable)",
+          e);
+    }
+    checkLibraryVersion();
+  }
+
+  private LibFaissC() {}
+
+  private static MethodHandle getMethodHandle(
+      String functionName, MemoryLayout resLayout, MemoryLayout... argLayouts) 
{
+    return Linker.nativeLinker()
+        .downcallHandle(
+            SymbolLookup.loaderLookup().find(functionName).orElseThrow(),
+            FunctionDescriptor.of(resLayout, argLayouts));
+  }
+
+  private static void checkLibraryVersion() {
+    MethodHandle getVersion = getMethodHandle("faiss_get_version", ADDRESS);
+    String actualVersion = callAndGetString(getVersion);
+    if (LIBRARY_VERSION.equals(actualVersion) == false) {
+      throw new UnsupportedOperationException(
+          String.format(
+              Locale.ROOT,
+              "Expected Faiss library version %s, found %s",
+              LIBRARY_VERSION,
+              actualVersion));
+    }
+  }
+
+  private static final MethodHandle FREE_INDEX =
+      getMethodHandle("faiss_Index_free", JAVA_INT, ADDRESS);
+
+  public static void freeIndex(MemorySegment indexPointer) {
+    callAndHandleError(FREE_INDEX, indexPointer);
+  }
+
+  private static final MethodHandle FREE_PARAMETER_SPACE =
+      getMethodHandle("faiss_ParameterSpace_free", JAVA_INT, ADDRESS);
+
+  private static void freeParameterSpace(MemorySegment parameterSpacePointer) {
+    callAndHandleError(FREE_PARAMETER_SPACE, parameterSpacePointer);
+  }
+
+  private static final MethodHandle INDEX_FACTORY =
+      getMethodHandle("faiss_index_factory", JAVA_INT, ADDRESS, JAVA_INT, 
ADDRESS, JAVA_INT);
+
+  private static final MethodHandle PARAMETER_SPACE_NEW =
+      getMethodHandle("faiss_ParameterSpace_new", JAVA_INT, ADDRESS);
+
+  private static final MethodHandle SET_INDEX_PARAMETERS =
+      getMethodHandle(
+          "faiss_ParameterSpace_set_index_parameters", JAVA_INT, ADDRESS, 
ADDRESS, ADDRESS);
+
+  private static final MethodHandle INDEX_IS_TRAINED =
+      getMethodHandle("faiss_Index_is_trained", JAVA_INT, ADDRESS);
+
+  private static final MethodHandle INDEX_TRAIN =
+      getMethodHandle("faiss_Index_train", JAVA_INT, ADDRESS, JAVA_LONG, 
ADDRESS);
+
+  private static final MethodHandle INDEX_ADD =
+      getMethodHandle("faiss_Index_add", JAVA_INT, ADDRESS, JAVA_LONG, 
ADDRESS);
+
+  public record Index(MemorySegment indexPointer, int[] ordToDoc) {}
+
+  public static Index createIndex(
+      String description,
+      String indexParams,
+      VectorSimilarityFunction function,
+      FloatVectorValues floatVectorValues) {
+
+    try (Arena temp = Arena.ofConfined()) {
+      int size = floatVectorValues.size();
+      int dimension = floatVectorValues.dimension();
+
+      // Mapped from faiss/MetricType.h
+      int metric =
+          switch (function) {
+            case DOT_PRODUCT -> 0;
+            case EUCLIDEAN -> 1;
+            default -> throw new UnsupportedOperationException("metric type 
not supported");
+          };
+
+      // Create an index
+      MemorySegment pointer = temp.allocate(ADDRESS);
+      callAndHandleError(INDEX_FACTORY, pointer, dimension, 
temp.allocateFrom(description), metric);
+      MemorySegment indexPointer = pointer.get(ADDRESS, 0);
+
+      // Set index params
+      callAndHandleError(PARAMETER_SPACE_NEW, pointer);
+      MemorySegment parameterSpacePointer =
+          pointer.get(ADDRESS, 0).reinterpret(temp, 
LibFaissC::freeParameterSpace);
+      callAndHandleError(
+          SET_INDEX_PARAMETERS,
+          parameterSpacePointer,
+          indexPointer,
+          temp.allocateFrom(indexParams));
+
+      // Allocate docs in native memory
+      MemorySegment docs = temp.allocate(JAVA_FLOAT, (long) size * dimension);
+      FloatBuffer docsBuffer = 
docs.asByteBuffer().order(ByteOrder.nativeOrder()).asFloatBuffer();
+
+      int[] ordToDoc = new int[size];
+      KnnVectorValues.DocIndexIterator iterator = floatVectorValues.iterator();
+      for (int i = 0; i < size; i++) {
+        ordToDoc[i] = iterator.nextDoc();
+        docsBuffer.put(floatVectorValues.vectorValue(iterator.index()));
+      }
+
+      // Train index
+      if ((int) INDEX_IS_TRAINED.invokeExact(indexPointer) == 0) {
+        callAndHandleError(INDEX_TRAIN, indexPointer, size, docs);
+      }
+
+      // Add docs to index
+      callAndHandleError(INDEX_ADD, indexPointer, size, docs);
+
+      return new Index(indexPointer, ordToDoc);
+    } catch (Throwable t) {
+      throw new RuntimeException(t);
+    }
+  }
+
+  private static final MethodHandle INDEX_WRITE =
+      getMethodHandle("faiss_write_index_fname", JAVA_INT, ADDRESS, ADDRESS);
+
+  public static void indexWrite(MemorySegment indexPointer, String fileName) {
+    try (Arena temp = Arena.ofConfined()) {
+      callAndHandleError(INDEX_WRITE, indexPointer, 
temp.allocateFrom(fileName));
+    }
+  }
+
+  private static final MethodHandle INDEX_READ =
+      getMethodHandle("faiss_read_index_fname", JAVA_INT, ADDRESS, JAVA_INT, 
ADDRESS);
+
+  public static MemorySegment indexRead(String fileName, int ioFlags) {
+    try (Arena temp = Arena.ofConfined()) {
+      MemorySegment pointer = temp.allocate(ADDRESS);
+      callAndHandleError(INDEX_READ, temp.allocateFrom(fileName), ioFlags, 
pointer);
+      return pointer.get(ADDRESS, 0);
+    }
+  }
+
+  private static final MethodHandle INDEX_SEARCH =
+      getMethodHandle(
+          "faiss_Index_search", JAVA_INT, ADDRESS, JAVA_LONG, ADDRESS, 
JAVA_INT, ADDRESS, ADDRESS);
+
+  public static void indexSearch(
+      MemorySegment indexPointer,
+      int[] ordToDoc,
+      float[] query,
+      KnnCollector knnCollector,
+      Bits acceptDocs) {
+    try (Arena temp = Arena.ofConfined()) {
+      // Allocate queries in native memory
+      MemorySegment queries = temp.allocate(JAVA_FLOAT, query.length);
+      
queries.asByteBuffer().order(ByteOrder.nativeOrder()).asFloatBuffer().put(query);
+
+      // Faiss knn search
+      int k = knnCollector.k();
+      MemorySegment distancesPointer = temp.allocate(JAVA_FLOAT, k);
+      MemorySegment idsPointer = temp.allocate(JAVA_LONG, k);
+
+      MemorySegment localIndex = indexPointer.reinterpret(temp, null);
+      callAndHandleError(INDEX_SEARCH, localIndex, 1, queries, k, 
distancesPointer, idsPointer);
+
+      // Retrieve scores
+      float[] distances = new float[k];
+      
distancesPointer.asByteBuffer().order(ByteOrder.nativeOrder()).asFloatBuffer().get(distances);
+
+      // Retrieve ids
+      long[] ids = new long[k];
+      
idsPointer.asByteBuffer().order(ByteOrder.nativeOrder()).asLongBuffer().get(ids);
+
+      // Record hits
+      for (int i = 0; i < k; i++) {
+        int ord = (int) ids[i];
+        if (ord < 0) {
+          break;
+        }
+
+        // TODO: This is like a post-filter, include at runtime?
+        int doc = ordToDoc[ord];
+        if (acceptDocs == null || acceptDocs.get(doc)) {
+          knnCollector.collect(doc, distances[i]);
+        }

Review Comment:
   @benwtrent +1, filtering is super important..
   
   I pulled the above PR + some more changes (explained in 
https://github.com/facebookresearch/faiss/pull/4167) locally, and got a 
filtered search working!
   
   Filtered searches in Lucene primarily use a 
[`FixedBits`](https://github.com/apache/lucene/blob/e4321619bba8669e93311ffb9456fa043d519b21/lucene/core/src/java/org/apache/lucene/util/FixedBits.java#L20)
 (in case of live docs) or 
[`FixedBitSet`](https://github.com/apache/lucene/blob/e4321619bba8669e93311ffb9456fa043d519b21/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java#L32)
 (in case of pre-filter). In both cases, these are backed by a `long[]` where 
each bit in a `long` represents whether a doc is filtered or not
   
   For i=0, we pick the least significant bit of the 1st `long`
   For i=1, we pick the second-least significant bit of the 1st `long`
   For i=64, we pick the least significant bit of the 2nd `long`
   .. and so on 
([reference](https://github.com/apache/lucene/blob/e4321619bba8669e93311ffb9456fa043d519b21/lucene/core/src/java/org/apache/lucene/util/FixedBits.java#L31-L38))
   
   Consequently in Faiss, we can use an 
[`IDSelectorBitmap`](https://github.com/facebookresearch/faiss/blob/6c046992a71e672df504a0101cddf6f2f2e90601/faiss/impl/IDSelector.h#L101)
 which takes `uint8_t*` (list of bytes) as input
   
   For i=0, we pick the least significant bit of the 1st `byte`
   For i=1, we pick the second-least significant bit of the 1st `byte`
   For i=8, we pick the least significant bit of the 2nd `byte`
   .. and so on 
([reference](https://github.com/facebookresearch/faiss/blob/6c046992a71e672df504a0101cddf6f2f2e90601/faiss/impl/IDSelector.cpp#L117-L123))
   
   i.e. we can bulk-copy the `long[]` from Java -> the native process in the 
[`LITTLE_ENDIAN`](https://en.wikipedia.org/wiki/Endianness) byte order and 
_directly use the resulting byte array as a filter!_
   
   Lucene:
   ```
   recall  latency (ms)    nDoc  topK  fanout  maxConn  beamWidth  quantized  
index s  index docs/s  force merge s  num segments  index size (MB)  
selectivity  filterType  vec disk (MB)  vec RAM (MB)
    0.880         1.830  200000   100      50       32        200         no   
143.77       1391.13           0.01             1           236.93         0.50 
 pre-filter        228.882       228.882
   ```
   
   Faiss:
   ```
   recall  latency (ms)    nDoc  topK  fanout  maxConn  beamWidth  quantized  
index s  index docs/s  force merge s  num segments  index size (MB)  
selectivity  filterType  vec disk (MB)  vec RAM (MB)
    0.792         1.000  200000   100      50       32        200         no   
140.22       1426.38           0.00             1           511.97         0.50 
 pre-filter        228.882       228.882
   ```
   
   Added in the latest commit



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org

Reply via email to