Repository navigation
Discussion for: Native VECTOR Store and VECTOR INDEX Support for MySQL #6
Replies: 2 comments 1 reply
|
Hi Inaam, Thank you for the detailed proposal. I had one preliminary design question. What is the main reason for choosing the hidden sub-table approach to store vector index leaf data, instead of modelling the vector index as a native InnoDB index with its own page format? For example, suppose the vector index had custom InnoDB pages: a root/metadata page containing the centroid information, and each centroid/partition pointing to posting pages containing the vector entries, base-row PK reference, and any needed metadata. These pages would still live in the buffer pool, be REDO logged, be part of the flush list, and be modified synchronously during base-table DML, similar to other InnoDB index pages. My understanding is that by making custom vector pages buffer-pool managed and REDO logged would solve persistence/crash recovery at the page level. However, it would not automatically give the vector entries normal row-level MVCC/UNDO/Purge semantics. A custom design would likely be needed for its own handling for rollback, purge, delete-marking, old-version visibility, and crash-recovery-rollback. Is that the main concern with the custom vector index-page approach, or were there other issues? |
|
Hi all I believe there's an interest to understand better how to implement an index structure for a graph based structure like HNSW, with the assumption that keeping the entire dataset in RAM is not an acceptable solution. My knowledge of the topic is rather superficial, but in my past I did manage a team that was supporting a graph database in maintenance mode. In particular, my nuggets of graph knoweldge are based on reading this book https://www.oreilly.com/library/view/the-practitioners-guide/9781492044062/ and working as a peer to one of the authors for a year. (Btw I believe both authors are available for consulting...) optimal cutI assume readers here know or can intuition about basics about graphs: Given a starting node (which could have been found through a normal b-tree or hash lookup against id or property fields) you follow outgoing edges that match other filtering criteria, to neighboring nodes,new edges, ... until the result set is found. As we already established, many Graph database products expect their data to be in RAM, because at that point you can hop around all you want, and the cost will be constant regardless of how you physically ordered the graph. So, how do we do the same efficiently so that data is stored on disk? Or, it turns out, the same answer also is the solution to efficient sharding. The key word to look out for is optimal cut. This means, we want to divide the full graph into sub-graphs (pages, shards...) so that the number of edges that traverse from one sub-graph to another is minimised. In the basic case each edge is worth the same, but they could also be weighted. In this case if we have statistics on how often or likely it is that an edge is used, we would use that as a weight on each edge when executing the optiimal cut algorithm. supernodesAnother common problem, and I don't know if this is a problem for our use case but... , is the so called "justin bieber" problem: Many real world graph datasets tend to have so called supernodes, which have a high number (n) of outgoing edges. And in a graph traversal, you may need to follow each edge to see what is on the other side. Hitting a supernode or two when doing such traversal may quickly become as expensive as scanning the entire table, or worse. The solution to this problem is to add extra structure to the graph, specifically the neighboring nodes, which enabled avoiding the supernode. Essentially a neihbor node to a super node will augment its own outgoing edges with information about what is the next hop after the supernode. Often this might require workload specific knowledge to create only a small subset of the combinations of edges, as the goal is to shortcut the need to traverse n^2 paths. Tree-Graph equivalenceFinally, an encouraging thought: The problem of storing a graph as pages on this is actually no worse than storing a tree (IVF or otherwise). As a proof, a thought exercise: Given a set of vectors V = {v1, v2...vn} we first use the IVF algorithm, the same k-means clustering, to divide V into k subsets P. k = |P| << |V| = n The algorithm produces k clusters each holding approximately n/k vectors. Yet these are exactly the same vectors we could have indexed into a graph G, using HNSW. So now, keep the same set of subsets P, and add the edges from graph G next to their nodes. (since the edges are bidirectional, add each edge to two nodes). We have now created a cut of graph G that we know we can use at least somewhat efficiently to store G as pages on disk, because we would have used the exact same pages for the IVF algorithm. The obvious criticism against the above cut of G is that there's no guarantee, and in fact it is likely, that a query of k nearest neighbors will follow edges out of their pages into another pages, and maybe back again. And this will add latency that IVF doesn't have. Yet this is the flip side of the well known criticism of IVF, that it is less precise at the edges of its clusters. The identically cut HNSW graph will be more precise because it can more easily include nodes from an adjacent cluster/page, but of course this improved accuracy had a cost. Indexing nodes or also edgesFinal thing to consider is whether the application intends to query for nodes, and the edges are merely there to connect and provide the path between the nodes, or, is it also possible to query edges? For example a graph modeling an ethernet network could be used to query all network links with speed 1Gbps or more. There's nothing weird with this, you just add an index, or two, or three, over the properties of the edge: the starting node, the end node, the property "bandwidth" and any other properties that need to be searchable. Just like any other database with multiple secondary indexes, here too index maintenance is a list of chores: delete a node, and you have to delete all the properties indexed of that node, and then also all the edges connected to it, and in case of bidirectional edges, also delete the reverse edge. Note that just like in a relational database, note everything needs to be indexed, just the properties that application needs to find as a starting point / set. If we just want to do a query "Find all routers that have at least one port with 1 Gbps bandwidth, and if this port is connected to another router, follow that link, and..." This query does not (necessarily) need an index over the edges at all. |
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
Originally submitted by Mayank Prasad of Oracle
Abstract:
This proposal aims to evolve MySQL VECTOR support from write-only metadata into a fully functional native vector store with indexing and similarity search. The goal is to support ACID-compliant AI retrieval workloads directly in MySQL, reducing the need for an external vector database.
This discussion relates to issue: #3
All reactions