KR-20260066799-A - TRANSACTIONALLY-CONSISTENT HNSW INDEX

KR20260066799AKR 20260066799 AKR20260066799 AKR 20260066799AKR-20260066799-A

Abstract

Techniques for providing transaction-consistent Hierarchical Navigable Small Worlds (HNSW) indexes are described. In one technique, an HNSW index for multiple vectors is stored. In response to receiving a set of changes for multiple vectors, the set of changes is stored in a shared journal instead of applying it to the HNSW index. In response to receiving a vector query containing a query vector, a subset of the set of changes in the shared journal is identified based on the query vector. Additionally, a subset of multiple vectors is identified based on the query vector and the HNSW index. A result of the vector query is generated based on the subset of the set of changes and the subset of multiple vectors.

Inventors

라히리, 티르탄카
브루그나라, 마틴
알라지아니스, 요아니스
하프리안, 블라드 요안
데인즈, 로렌트 필립
공, 웨이웨이
로아이자, 주안 알.
바리아, 프라나브
보세, 슈브하
크리쉬나파, 친마이
차반, 샤샹크 키산
미쉬라, 아우로시쉬
펜제, 수카다 샤샹크
사하, 아그니보
아가르왈, 로한
왕, 샨치
브리토, 베니타 캐슬린
아르나볼디, 마르코

Assignees

오라클 인터내셔날 코포레이션

Dates

Publication Date: 20260512
Application Date: 20240916
Priority Date: 20240914

Claims (16)

As a method: A step of storing the first version of the vector in a vector object; A step of identifying a second version of the vector that is different from the first version and is not stored in the vector object; In response to receiving an instruction to save the second version to the above vector object: A step of identifying the above vector object; A step of updating the vector object to include the second version in addition to the first version; and The method includes the step of inserting a value representing the location of the first version or the second version within the vector object into the next version reference field of the vector object; The above method is performed by one or more computing devices.
In claim 1, prior to receiving the instruction, the vector object includes a first model version field including a first value representing a first version of the model that generated the first version of the vector, and the method is: The method further includes the step of inserting a second value representing the second version of the model that generated the second version of the vector into the second model version field of the vector object; The second version of the above model is different from the first version of the above model; The above second value is different from the above first value, method.
In claim 1, updating the vector object includes appending the second version to the vector object, and the method is: A step of identifying a third version of the vector that is different from the first version and the second version and is not stored in the vector object; In response to receiving the second instruction to save the above third version to the above vector object: A step of identifying the above vector object; The step of appending the above third version to the above vector object; and A method further comprising the step of inserting a value representing the location of the third version of the vector into the second next version reference field of the vector object.
In claim 1, updating the vector object includes prepending the second version to the vector object, and the method is: A step of identifying a third version of the vector that is different from the first version and the second version and is not stored in the vector object; In response to receiving the second instruction to save the above third version to the above vector object: A step of identifying the above vector object; The step of transposing the above third version to the above vector object; and A method further comprising the step of inserting a value representing the location of the second version into the second next version reference field of the vector object.
In paragraph 1, In response to receiving a second instruction to search for a specific version of the above vector: A step of identifying the above vector object; A step of identifying a value within the next version reference field of the above vector object; A step of identifying the location within the vector object based on the above value; and A method further comprising the step of searching for the specific version based on the above location.
In paragraph 5, A step of storing a first value representing the first version of the model that generated the first version of the above vector in the first model version field of the above vector object; A step of storing a second value representing the second version of the model that generated the second version of the above vector in the second model version field of the above vector object; In response to receiving the above second instruction: A step of identifying a specific model version associated with the above specific version; and After identifying the vector object, the method further comprises the step of (1) performing a comparison between the specific model version and (2) (a) the first value in the first model version field of the vector object or (b) the second value in the second model version field of the vector object; Searching for the specific version mentioned above is also a method based on the comparison above.
In paragraph 5, the above second instruction is a method for specifying the above specific version.
A method according to paragraph 5, wherein the second instruction does not specify the specific version, and the specific version is a default version associated with the second instruction.
In paragraph 1, It further includes the step of receiving a database statement that modifies a column of a table and stores multiple vectors; The above database statement is a method for designating a specific version among a plurality of versions as the current version of each of the plurality of vectors in the column.
A method according to claim 1, wherein the vector object is a binary large object (BLOB).
In paragraph 1, It further includes the step of receiving a table specification that specifies a column having the VECTOR data type; The above specification does not specify the number of dimensions for the vectors to be stored in the above column; A method in which the first version has a first dimension, and the second version of the vector has a second dimension different from the first dimension.
In paragraph 1, It further includes the step of receiving a table specification that specifies a column having the VECTOR data type; The above specification does not specify a dimension format for the vectors to be stored in the above column; A method in which the first version has a first-dimensional format, and the second version of the vector has a second-dimensional format different from the first-dimensional format.
In paragraph 1, A step of deciding to store the first version of the second vector in a logical vector object; In response to the decision to store the first version of the second vector in the logical vector object: A step of storing the first version of the second vector in an extent dedicated to the first vector; A step of storing a first version reference referencing the location of the first vector-only extent in a row of a table; A step of deciding to store a second version of the second vector in the logical vector object; In response to the decision to store a second version of the above second vector in the above logical vector object: A step of storing a second version of the second vector in an extent dedicated to the second vector; and The method further includes the step of storing a second version reference referencing the location of the second vector-only extent in a row of the table; The above method is performed by one or more computing devices.
In paragraph 13, the method wherein the second vector-only extend is different from the first vector-only extend.
One or more storage media, wherein the storage media stores instructions that cause the execution of any one of claims 1 to 14 when executed by one or more computing devices.
As a system, One or more computing devices; A system comprising one or more storage media storing instructions that cause the execution of a method described in any one of claims 1 to 14 when executed by one or more of the above-mentioned computing devices.

Description

Transactionally Consistent HNSW Index The present disclosure generally relates to vector embeddings, and more specifically, to database systems that support a specific type of vector index on multiple nodes within a cluster. A vector is a fixed-length sequence composed of numbers, typically floating-point numbers, such as the 5-dimensional vector [21.4, 45.2, 675.34, 19.4, 83.24]. Embeddings are a means of representing objects (e.g., text, images, and audio) as points within a continuous vector space, where the locations of these points within the space are semantically meaningful to one or more machine learning (ML) algorithms. Embeddings are often represented as vectors. Generally, vector embeddings represent points within an N-dimensional space. Vector embeddings are intended to capture important "features" of the data they represent (or embed). The data represented by a vector embedding can be one of many types of data, such as documents, emails, images, or videos. Examples of features include color, size, category, location, texture, semantics, and concepts. Each feature is represented by one or more numbers (dimensions) within a vector embedding. Hereinafter, "vector embedding" is referred to as "vector". Today, vectors are often generated by machine learning models (e.g., neural networks), and the features they represent are often difficult for humans to understand. One way vectors are produced by neural networks is to capture the outputs of neurons within the penultimate layer—that is, the outputs of the neural network immediately before the final processing layer. Distance between vectors An important property of vectors is that the distance between two vectors serves as a good proxy for the similarity of the objects they represent. Two vectors representing similar data must be close to each other in vector space. The opposite is also true: dissimilar data is represented by vectors that are far apart in vector space. For example, the distance between the vector for the word "cat" and the vector for the word "dog" must be smaller than the distance between the vector for the word "cat" and the vector for the word "plant". The distance between two vectors is often calculated by summing the squares of the differences between the numbers at their respective positions: The property that vector distance indicates object similarity allows similar data to be found using a vector database. For example, when a vector representing a picture of a dog is searched within a vector database, the closest vectors will be those representing other dogs, rather than vectors representing plants. Vector processing workloads Vector processing workloads (not to be confused with SIMD vector processing) have been used in Natural Language Processing (NLP), image recognition, recommendation systems, and the like. Vector processing workloads have two subcategories that require separate optimization strategies: indexing and searching. Regarding indexing, vector embeddings (or simply vectors) are indexed using approximate indexing techniques. Unlike B-tree indexes, vector indexes return many matching values ranked by similarity. Index creation and rebuilding tend to be CPU-intensive tasks and are optimized for throughput. In relation to search, the stored vectors are retrieved using a class of algorithms known as "Similarity Search" or "Approximate Nearest Neighbor (ANN)" to find the vectors closest to the query vector. The search is designed to minimize CPU usage to minimize response time. Vector processing patterns Vector similarity search is similar to online transaction processing (OLTP) in that end users submit vector queries and expect immediate responses. Vector similarity search requires millisecond response times to find nearby (representing similar data) vectors, even if the database storing the vectors holds billions of vectors. One exemplary query is "Find products similar to this photo [refer to digital image]." Another exemplary query is "Find in-house documents that conceptually match this natural language prompt: [NL prompt]." Providing fast response times requires the use of specialized vector indexes and high-speed algorithms to calculate distances between vectors. In some use cases, it is necessary to combine vector similarity search with relational data. For example, a query might request data on homes that match a natural language prompt, are valued at over $1 million, are located in zip code 94070, and whose owners have recently declared bankruptcy. Additionally, it may be necessary to have the capability to insert new vectors into a database, delete vectors from a database, and index vectors in real time. Vector databases Early vector workloads often used flat files or object stores to store vectors. Applications would load vectors from their backend repositories into memory and then perform vector processing using third-party libraries such as FAISS. Generative artificial intelligence (AI) has significantly