Vector Databases Are Not Real Databases With Yujian Tang at AIE 2024

Hello everyone, my name is Chen Tang and I'll be talking to you about vector databases and how they're not real databases today. So my name is Chen Tang. A little bit of background about me.

Um, currently a senior developer advocate at Zillow. And if you would like, you can scan that QR code to the right, it'll take you to my LinkedIn where you can find me and reach out with any questions that you might have. Uh, before I was at Zillows, uh, I started my software career at uh, IBM back in 2013.

Uh, I did some research on machine learning and then I published some papers and went to Amazon where I worked on the auto ML system there. Uh, after some time at Amazon, I decided, hey, uh, I think it's time to do something with more scope, more creativity, and I got into startups and that's how I found myself working on vector databases. And, uh, over the last year, I've built many, many different kinds of applications on top of vector databases and a lot of applications in the gen AI space.

So let's cover what we're gonna talk about today. So first we're gonna do an introduction to semantic similarity, and then we're gonna talk about some of the things that go into vector search and the challenges that come across in vector databases or really why vector databases aren't really databases, but actually compute engines. And then we'll go into a deep dive of bu.

So let's start by talking about semantic similarity. Seman similar data is data that means the same thing. And so I put these three sentences on the screen here, and they are apple made profits of 97 billion in 2023.

I like to eat apple pie for profit in 2023. And apple's bottom line increased by record numbers in 2023. So if you're using traditional keyword search and you were to look up apple profits 2023, you would get back the first two results.

But really, if you want to know about Apple's profits in 23 and 2023 and how well they did, you actually want the first and the third sentence. And that's semantic similarity, right? The keywords there may not be the same, but the semantic similarity of profits and bottom line are the same.

And based on the sentence itself, you can tell the second sentence is about apple pie, which is a food and not apple, the company. And it's not just text data. You can also do this with images.

So here I've got four images that all look like Taylor Swift. And so, so typically, um, to do image search you have, you can look for some sort of like features or pixels or faces or things like that, but it's really hard to tell which one is the fake Taylor Swift out of these pictures. Uh, but we as humans or it's really hard for machines to tell, but we as humans can tell, uh, which one is the fake Taylor Swift.

So, um, the first one looks a lot like Taylor Swift and typically everyone says this one is Taylor Swift. The second one looks also quite a bit like Taylor Swift. The third one and the second one are typically the ones that people say don't look too much like Taylor Swift.

People tend tend to agree the first and fourth ones are Taylor Swift, but in reality, the second one isn't Taylor Swift. So if you looked at these pictures and you thought, you know that second one looks out of place, then you got it right. So what is, what is actually being calculated when we talk about semantic similarity vectors introduce the ability to calculate, uh, quantify the difference between some words or images or audio or video things that aren't originally numbers.

And that's the basics behind semantic similarity. Here you have things like words that can be represented as vectors in the form of numbers. So on this side we see queen minus woman plus man equals king.

And before we get into the exact, you know, um, demonstration of the math here, I want to know one thing that is particularly important, which is that, um, although queen and woman and king and man have the same value on the x axis on the first dimension of the vector, it doesn't necessarily mean anything about what that dimension means. It doesn't mean that that's a dimension is gender or sex, it's just telling us that these words along this dimension have the same meaning, the same relationship. So let's get into some of this math here.

5. 7, which just so happens to equal K. So here what we've done is we've shown a very basic example of how you can add and subtract vectors so that you can get the, uh, quantifiable difference between the meanings of words.

So let's get into vector search basics. The first thing that we're gonna learn about here are similarity metrics. So there's actually different ways to, to organize and measure the difference between vectors.

And unlike the typical un unlike the scenario that we just showed with the two, um, with the two dimensional vectors, typical vectors actually have hundreds of dimensions. So this example is a toy example just meant to illustrate, uh, a formula for you. So L two or Euclidean distance is a way to measure the difference of vectors in space.

So this measures the magnitude of the difference between two vectors. Okay? And the formula here is basically, you can think of this as, hey, I've got a triangle.

I'm trying to find the hypotonus in a sense. Next we've got ip, which is inner product. And inner product measures both the magnitude and the angle.

It's the projection of one vector onto another. And so in this case, you can think of it as measuring like, Hey, I've got the hypo ous and the leg of a triangle. Now I'm trying to get the distance of the other leg.

And inner product is probably the most efficient way to measure vector similarity. Um, as you can tell compared to the last formula, there's much less going on in this formula. And so it is computationally less expensive than the last formula than L two.

Now we have a third one, which is cosign. And you can see the co-sign actually looks quite a bit like ip, but co-sign is actually IP with a few additional computations thrown in. Its normalized ip.

So if your vectors are already normalized, that means if the magnitude of your vectors is already one, then you should just use in a product. And cosign measures the angle between two vectors as the name would suggest. So let's just cover all of that.

So with vector similarity metrics, Euclidean measures the spatial distance, the magnitude cosign measures the orientational distance, the angle and inner product measures both. And if you have normalized vectors, inner product is equivalent to cosign. Okay, now let's look at indexes.

Indexes are the ways that we organize and retrieve our data. The first index we're gonna look at here is inverted file index or IVF. And this index is probably the most intuitive vector index as essentially what we're doing here is getting some vectors near some OIDs.

So OIDs are like the, you know, the, the, the middle, the vector, the middle point of a bunch of these different vectors. And, and an organized IVF map looks kind of like the image shown in the slide. And essentially what's done here is you run something like a K means algorithm.

K means is a machine learning algorithm that, um, gets you a certain number of OIDs and finds all of the vectors that are close to it. And so that's what IVF is IVF is a relatively memory inexpensive, uh, way of organizing vectors. It doesn't add any memory, uh, that you have to keep, uh, in your ramp, but it doesn't add any memory that you have to keep in your ramp.

Um, but the trade off is that unless you search through all your centralized, you're not guaranteed a hundred percent accuracy. You're not guaranteed like a super high accuracy level. The next one that we look at is H and SW or hierarchical navigable small worlds.

This is a graph based vector index. And so what that means is that we're gonna take all our points and we're gonna insert them into a graph. And the way that HNSW works is as we insert them into the graph, we're gonna label them with a uniform random variable.

And that, and the value of that variable determines what layer they'll go up to in our hierarchical navigable small worlds. 9. 99 up, all those layers go into layer two, and so on and so on and so on.

And then at search time, when we search for these vectors, we start at the top most layer that we've created and we search for the closest vector in that layer. And then we go down to the next layer and we use the graph so we don't have to recalculate a lot of these different things. We can use the graph to find the next closest vector and compare that and then go down and go down and go down until we find the closest vector.

And so in this case, we have a near 100%, uh, accuracy. We can almost always find the closest vector. And the trade off here is that this introduces a lot of extra memory.

You have to keep this graph in your memory and you also have to keep multiple copies of the same vector. So HSW is high memory, but it's quite fast and it's quite accurate. Next, let's look at scaler quantization.

So scaler, quantization or quantization in general you can think of as just a bucketing algorithm. So essentially if we have the realm of real numbers and we were to reduce the realm of real numbers, let's say we have the real numbers from negative 10 to 10, and we were to reduce these into the realm of integer, then that is an example, uh, of how quantization could be done. 4, you would say, oh, this is close to zero, we're gonna call it zero.

And so this is one way that you can reduce the amount of memory that you have because now you don't have to represent numbers as floats, but rather as integers. And, um, you can reduce the amount of memory that you use, but the trade off is that you won't always get as accurate of a result. So next we have product quantization, which is kind of like scaler quantization, but it's not just across, uh, a vector, let's say.

But also it takes into account the whole range of values in the, in a set of vectors. And so in this case, we quantize across two different vectors, two different, we quantize across two different dimensions of the vectors. And what we'll see with product quantization is that we will actually get a much, much smaller compressed version of the same amount of, uh, vectors in memory size.

But in the trade off, once again, is that the, uh, the search is not as accurate. Okay, so let's go back over the indexes again, right? So there's IVF, which is intuitive, doesn't take a lot of memory, pretty performant.

HSW is graph based. Um, it takes a lot of memory, but it's very performant. And there's flat, which I didn't cover, but flat is basically just, I'm just gonna look through all of the vectors.

That's just your brute force. Say no change in memory, no indexing. Um, very, very a hundred percent, uh, reco recall, it's just slow and it's takes, it's very computationally expensive.

And then we have sq, which allows you to scale a quantization, which allows you to basically do a accuracy from memory trade off, and then pq, which does both again. So in mils we actually have a way to kind of deal with, uh, uh, the problems that come up with all of these different indexes by allowing you to combine different indexes. So you can do IVF with QUANTIZATION or HNSW with quantization.

So HSW has a lot of memory. You quantize it, you get much, much less memory that it takes up, but you trade off some of that performance. But in the end, perhaps you end up with something that's more performant than either, and it just depends on your use case and your requirements and what you need in terms of latency and, uh, recall and um, memory and all these different aspects of search.

Okay, so let's look at some of the challenges that are involved in vector databases. Before we get into this, let's look at what vector data looks like. So this is a screenshot of a entry that I have in Zillow, which shows you an id.

And embedding these two are two keys that must be in every entry of a vector database. You need the ID because you need to be able to pull specific vectors sometimes, such as for deletion or upsert, and need the embedding so you can compare the vectors to each other. So this kind of shows you that vector embedding is just a series of numbers and that an ID can be anything, it can be a string, it can be a number, it can be anything.

In this case I have a string. The rest of it is what we call metadata. Metadata can be used to, um, enhance your search results such as if you're doing rag, you need to have metadata that includes the sentences so that when you pull your results from the vector database, the LM can get these sentences back.

And then what if you want to, you know, say search in a certain date range, maybe you want the data publication or maybe you want to filter in some other manner. Metadata can also be used to help you filter your data. So some of the challenges, and this, this is like not even including some of the filtering challenges, but some of the challenges with vector databases in general is indexing, which is can be computationally expensive.

How do you do this at a different time? How do you do this with different compute? How do you do this effectively?

How do you do it efficiently? And then scaling rights. So, you know, once you have multiple instances, and if you've worked in databases long enough, you probably are familiar with having multiple instances or multiple replicas.

You have to be able to have some sort of consistency across them. And so scaling rights becomes a challenge because now you have to write your data and you have to get it into the right replicas in the right instances and make sure they're all up to date. And then you have scaling reads.

Well, we also need to be able to read all of that data that we put in and are we reading the data that's coming in that hasn't been indexed? Are we reading the data that's from an existing index? Where are we reading the data from?

How are you reading that data? And then you have updating data. So what happens when you update your data once you delete it, you have to make sure that your, uh, read that your query engine can't find that data and you also have to make sure that the new data gets put into some sort of index.

So updating data also becomes difficult. And then there's, you know, of course the classic enterprise ready features like role-based access control, auto-scaling, that type of thing. So some of these challenges are basically the reasons why we wouldn't use an underlying SQL or no SQL database and just build the compute engine on top.

Remember at the beginning I said vector databases are not real databases. So you could build a vector database on top of some other database like a SQL database or no SQL database. But the real, the real value add of a vector database is actually the way the compute engine is structured and how it handles the data for you.

But the TLDR of why you wouldn't use a SQL or no SQL database, vector operations are too computationally expensive for traditional database infrastructures. Traditional databases look for key to key comparisons. Basically during some sort of key search vectors are doing a number to number search.

Remember at the beginning we showed all those different vector metrics and the way that the vectors were, uh, could be compared and how they had to do some additions, some subtractions, some multiplication, things like that. Well, that is the real value out of the vector database. And so having a no SQL or SQL database is fine, but really adds no value in terms of your vector search.

Okay, what about vector search libraries? So vector search libraries can be put on top of NoSQL and SQL databases, but now what you've got to do is you've got to combine the infrastructures together. And oftentimes you might have to play around with a couple of different indexes or a couple of different, um, vector metrics or other things like that in order to find the correct you, the correct setup for your use case.

And in that case, you may have to learn how to use multiple vector search libraries, but the TLDR here is the Vector search Libraries just don't have the infrastructure that can help you actually put one of these vector databases into production. So let's talk about viss. This is a high level overview of Mil Vista's architecture.

And in a second we're gonna go in and we're gonna break down how some of these pieces work. But essentially what you need to know here is that viss is a distributed system that sits on top of permanent storage that provides this vector database capability. And the way it does it is very special and very unique in that it has a full separation of concerns, of search concerns in the query the data and the indexing, as you can see in this worker node layer.

And also it has a access layer that does proxies, that has distributed system so that you can distribute your calls and scale and it uses some sort of message store that acts like a hub subsystem to write data. Okay, so let's look into some of these different pieces. Like I said earlier, one of the things that makes VIS so scalable is that it has a separation of concerns in its worker layer.

You will never have your query nodes, your data nodes, and your index nodes all running the same amount of compute because querying is for finding data. Data. The data note is for ingesting data.

And the index note is for looking for ways to put your data correctly into an index so that it's easily, uh, and computationally efficiently retrievable. And so it is almost never going to happen that you're gonna have all of these running at the same amount. And so by having separate nodes with separate responsibilities, you were able to scale these more effectively, more efficiently and take advantage of all the resources that your system has.

Now, let's look at writing. So writing, there's actually two slides on here. So writing first, the first thing you need to look at in writing is the right stream.

When you write data into vus, VUS acts as a pub sub system. It is a publishing system that uses the rights right log as a publishing system and the subscriber system at the node level where the query and node and the data node will both receive the data. So the query node receives the data because VIS keeps your data in these things called segments.

And segments are logical partitions, basically, uh, logical pieces of data that get indexes built on top of them and get searched. So the query node has to keep track of the segment that hasn't been indexed yet, and the data node has to keep track of that segment as well so that I can adjust that data. So in here, this is the streaming part of the right data, it gets pushed into the write ahead log, and then it gets subscribed to from the nodes.

And then what happens once that segment hits a certain size, typically the default size is 512 megabytes. But as you grow the amount of data that you work with, you're gonna want a larger segment size. But as it comes in, it goes into the data node, it reaches a certain segment, the data node kicks that out, and then it tells the control, the coordinator service, Hey, um, the data has reached a certain size, call the index node.

The index node says, okay, I know that the data has reached a certain size, I gotta go find that data and then I'm gonna index that data and then kick the index file out. And it also tells the query node, Hey, that growing segment of data that you have is now ready to be indexed and turn into what we call a seal segment. So once the growing segment hits that size, when the data node has started, kicked it out, the query node, uh, once it's indexed, kicks that out, kicks that out, and instead just keeps track of the way that that, uh, uh, that data is indexed.

So that, uh, query time, it just has to check the index to get the right, um, to get the right data back for you. So what about reading data? Well, reading data happens basically entirely in the query node, right?

So in the growing segment, that's the data that's still coming in that hasn't been indexed yet, that's read basically in a flat way in a, uh, uh, bracelet brute force, right? The index that we talked about earlier, this would be flat up until it hits a certain size. And, uh, this is, you know, control based on your segment size, in which case every time a growing segment hits a certain size, it gets indexed so that it's efficient to read the rd uh, it gets indexed to a temporary index so it's sufficient to read that data.

And what happens here is that the data is read from all of the different segments, and it is you basically do a parallel search across all the segments and then you combine all that data and you put it into the query node and that goes, actually, that goes back to the proxy. And the proxy says, okay, actually here's all of the different nodes that have sent me their results that have sent me their segment results. Now I'm gonna combine all this data and I'm going to, uh, aggregate it and make it, make it make sense so that I'm only, let's say you're looking for the top 10, maybe you'll get top 10 results back from multiple nodes from multiple segments, and it gets all coalesced into the real true top 10 at the XI layer where it gets kicked back to you.

Okay? So let's cover some of the types of searches that we can use in mild this. So one is top K, which I just talked about, right?

So this is basically like what are the closest results? The top five results are highlighted here. And then you have range search which says, okay, I know that I only want results in a certain, within a certain distance of my vector.

And that's what range search is, right? So that's why there's this circle here. All of the dots within the circle are returned.

And then there's expression filtering which says, Hey, I actually, you know, I don't care about the vector. What I care about is whether or not it was, uh, you know, published in the last 10 days or published 10 days before that. Or maybe it, uh, has been, maybe there's a published by a certain person or whatever.

And then what happens is you actually just run a bit mask and you get an expression filter. So everything that fits the expression, uh, is returned. And then you have filtering search, which is an expression filter with a top K or a range search.

And then you've got this thing called CRA by id, which essentially allows you to find different, um, allows you to find different vectors by their id, which is incredibly important for up asserting or deleting. Okay? So that's all there is to this, uh, talk.

Find me on LinkedIn, uh, on the left, um, find Novis and give it a star on GitHub on the right. Uh, thank you very much for listening and uh, if you have any questions, please feel free to reach out to me. Or if you run into any bugs while you are using vis, please go to the, uh, viss GitHub repo and open and issue, and we'll be happy to fix that for you.

Thank you.