Well you could store numbers all fine, but indexing vectors for similarity queries seems fairly recent and not all that widespread in the transactional world.

As the traditional db move forward in the space the need for dedicated vector databases will likely shrink, except for some very specific implementation that offer unique enough features (I.e. deeplake does vector search over object storage, which is very convenient for certain specific scenarios)

sqlite has r-trees for instance [0]. Could it be good enough for most use cases? If it's to query a knowledge base for instance, a couple dimensions should be sufficient. With the added benefit of being able to query your data in other ways.

[0] https://www.sqlite.org/rtree.html

r*-trees work doesn't work well when the number of dimensions stored in the index is much higher than the logarithm of the number of indexed entries, and this is a prevailing property of divide-and-conquer spatial index types when the keyspace is divided based on a single dimension at a time. As vectors regularly have 100+ dimensions, normal spatial indexing methods applied to vectors wouldn't be very efficient for anything with much less than 2^100 index entries; which is quite suboptimal for most datasets that you would want to have indexed.

Also the distance metric for r*-trees is just plain wacky for anything other than low-dimensional Euclidean space.

Even if you could make it perform well, it would not do what you want.

Are you saying this because r-trees expect a proper metric space, and people have the need to index datasets over non-metric spaces?

The curse of dimensionality creates a seemingly paradoxical situation where you have a vast vast search space, but everything is incredibly close to each other. Space subdivision algorithms become ineffective.

Here is a SQLite extension that uses Faiss under the hood.

https://github.com/asg017/sqlite-vss

Not associated with the project, just love SQLite and find it very useful.

What is "vector search over object storage?" Does deeplake performs some computations on objects and search on their embeddings?

It stores everything on cheap storage, with no compute associated (i.e. S3) and uses the client to compute the query embeddings and to retrieve the embedding index and to run an indexed search to identify the data to be retrieved, and likewise the client does the work of updating the index structure on writing.

The benefit is that you don't have to pay for the compute part of a database, and the storage layer is as cheap as it could be on the cloud.

At the expense of latency ? when in fact latency is the most important aspect for any search. Any idea on how fast the searches from the client are ?

retrieve the embedding index and to run an indexed search to identify the data to be retrieved. Please bear with the layman like questioning -

So if the data is {obj: "obj1, "data": {"name": "atlas", "embedding": "1123124234" } What is an embedding index ? Is it something like {"1123124234": "obj1"} ?

From what I understand the query will be "geography" whose embedding will be "12311111" and now you have to run a KNN for a match which will return {"name": "atlas", "embedding": "1123124234"}

Not sure where the embedding index comes into play here.

Eh, sure latency is suboptimal. But if you have a LLM in the mix, that latency will dominate the overall response time. At that point you might not care about how performant your index is, and since performance/cost is non linear, it can translate to very significant savings

How is indexing a vector different from indexing a varchar or an integer ? If you convert a vector into a byteaarray it should be no different from a bytearray of varchar but for the bytearray contents.

Now if you want to do similarity search you have to measure the distance between 2 or more vectors and that's independent of the indexing. No ?

So any database with sufficient memory should be able to accomplish this as evidenced by the vector similarity search feature of Redis. ( I don't know how Redis folks have implemented vector similarity but they do support KNN search )

Mostly the number of dimensions. Assuming your vectors are float16, so 2 bytes each, you’d run into Postgres’ B+tree index limit (2704 bytes) very quickly. You could index a 512-dimension vector fine, but I believe most models are well beyond that.

There are alternative index types, of course, or you could index the hash of the vector. These both come with tradeoffs.

Btree isn't a very useful index type for a vector, though. GIN, GIST, and the handful of new extensions optimizing for vector search are what you'd want (and don't have this limitation).

Aside, you can increase the size of tuples you can index in a postgresql btree by increasing the postgresql page size (requires a recompile and creating a new database instance).

Agreed to the first, but you have to first know that those exist (and what they’re good for). This leads into my second point: IME, the Venn diagram for “people making AI stuff” and “people capable of compiling and running their own DB in a reliable manner” has no overlap.

The distance computation could be separate from the indexing, but it will be inefficient relative to having an index organized to support the task.

Indexing in a vector engine is what gives you similarity search faster than brute force. The type of engine is what gives you various different distance measures (often approximate). Redis specifically has two choices: brute force (which is precise and slow), or HNSW (which is approximate and fast, but space-consuming for interesting dimensionality).

To be fair, Vector databases does sound more official as "new and important technology" compared to the last db hype of NOSQL.

I mean NOSQL was hype with no substance but "you can scale more if you deal with not having ACID" is just generally true.

Of course ACID scales to well into the Fortune 500 scale so...

"No substance" seems a bit harsh.

They mostly seem a tarted up associative array, sure, but a key-value store is a thing.

But don't you prefer your key value stores to be wearing red lipstick and a pushup bra?

> but a key-value store is a thing

DynamoDB underpins much of AWS which in turn underpins a ridiculous number of web services.

So definitely more than just a thing.

A naturally distributed key/value store. NoSQL wasn't a product, it was a radical rethinking of the balance between what we wanted and what we needed. Turns out some absolute necessities of using a RDBMS or even using SQL are not that important, and relaxing those actually-not-requirements allows massive scalability, something we desperately needed, or some evolved data structures and computation, like what redis provides.

Hype with no substance? Hold on ;)

I know it hurts, but remember that we were still writing XML way too often in 2013. Document stores were purpose-built for a thing we needed. And the execs bought in, to boot.

At the time, it was very convenient to shove JSON and similar in an indexable and aggregate-able database. I implemented a lot of very very large-scale code analytics via mongodb--about 10 years ago.

There wasn't really support for unstructured types in mysql or postgres or oracle without some additional transformation pipelines or db extensions back then. We usually just wrote stupidly complicated SQL schemas that took up our whole conference room, and only that one stressed-out guy really understood.

So it was neat. I would choose something better today.

> compared to the last db hype of NOSQL

NoSQL has been around for over 20+ years.

Since then Cassandra, DynamoDB, FoundationDB, MongoDB, Neo4J, Redis etc are not only still around but widely used and powering many of the services you use today.

That's true, but 13 or 14 years ago, the NoSQL hype was calling for widespread abandonment of RDBMSs. They were claiming key-value stores and document databases would replace traditional relational databases the same way Reddit replaced Digg. That "MongoDB is web scale" video was lampooning the very real hype that people had, and how difficult it was to pick through it. It was as bad as the more recent blockchain hype.

Even looking at HN's reactions to that video show a few comments that did not age very well (although most of them did): https://news.ycombinator.com/item?id=1636198

The sensible takes were that NoSQL would supplement and enhance RDBMSs, but the hype was much more than that.

The difference is that today those DBs are generally considered as complements to SQL databases targeting specific use cases. Back in the peak NoSQL days people were pushing the narrative that you'd never need to use a SQL database for anything ever again.

IMO this is the deal:

RDBMS is such a mature and powerful technology, and with the vast power in modern single-node hardware, they will scale to considerable sizes. But there is a limit.

Once a table or set of tables hit a certain scale, it needs to be distributed. Once you get to those scales, you are likely dealing with the threat of exponential data growth, so doing the "distributed Postgres" will bandaid the problem ... but you are starting to run into the CAP theorem's problems.

You'll need to AP-scale the biggest data tables, and since that almost always means a big coding change lift and introduction of an AP-scaling database, it will almost always be a six months to a year transition, and possibly adding an entirely new DB technology (Cassandra / DynamoDB / maybe FoundationDB).

I have yet to have anyone explain how joins scale on an AP distributed database except in limited situations where the joined data is somehow node-local to the other tables, usually some hierarchical situation. Otherwise you are pulling data from lots of nodes and aggregating and comparing the different sets to account for node drift / partitions / network failures. Cassandra and Dynamo basically say "you are scaling a single table/query/update/pre-joined data table".

Which really isn't fun for RDBMS folks. Because it is a shitload of denormalization on top of all the AP headaches and distributed transactions / updates.

As I said, megahuge machines really make that an outside case unless your use case really emphasizes the "A" in CAP, where write speed can be tolerated to be low and you want to tolerate entire cloud or datacenter outages.

But yeah, nosql was never going to kill the rdbms. The functionality/power of rdbms/SQL is so so so so much higher. Just be aware when you're about to shoot over the limit and prepare for the code changes to handle true scale in the (unlikely) event you're going to need it.

Great explanation, and I agree with one caveat - from my experience if you get to a truly large single RDBMS you have already lost, even if you have a powerful enough machine to run it on.

Massive RDBMS instances are awful to manage. Hard to backup/restore/fork. Hard to migrate tables and schemas without causing downtime. Accidental downtime happens all the time due to locks, bad indexes, bad query plans , etc etc. at large scale they are capricious beasts, care and feeding and most importantly changing them becomes a dark art.

Don’t let them get too big you’ll regret it :)

Oh, they're still at it. In my relatively recent experience Mongo will still try to sell you on the idea of abandoning relational workloads because migrations are hard and schemas are optional.

What would you use to compute proximity of vectors, for example?