Creating a search engine with PostgreSQL
xata.io
xata.io
I know what I am talking about. Back in 2000's I was asked to build a search engine. Parsing data from image EXIF information and indexing that into a taxonomy - three levels down and with counts. In MySQL 3.x.
Before that, the company went through multiple vendors who charged fortunes and were not capable of doing this properly, quite shockingly. One was Autonomy, and that thing just straight up could not do a taxonomy even at the top level.
It was 6 weeks of doing the impossible, writing very fragile SQL queries where performance was different literally if you rearranged the SELECT columns. We did it, amazingly, but this is not something I will ever do again. Databases are essentially the same, but search engines have come a long way.
As an intellectual exercise, please go head. "You just tokenize and then you are done!"
No, a search engine does a LOT more than just splitting your corpus of text into tokens. Soon after you are "done", new requirements come in. Taxonomy navigation? Multiple languages support? Automatic synonyms? Spellcheck "Did you mean" functionality? Performance at massive scale?
You will engineer yourself right into a corner. Just use a search engine for your own sanity.
Finally, there are things for syncing PG and ES data - ZomboDB, PGSync.
On the flip side, if you're a data analyst or developer who has a large database with one or more text columns they want results from in a more flexible way than using "LIKE/ILIKE" SQL queries, it's probably easier and faster to create an FTS index/table in that database to get them 90% of the way there.
Can you expand on this? Is it that it's tedious to write code that updates both? I've been meaning to play around with meilisearch and was trying to think about the synchronization issue.
Now, we had pretty lax consistency requirements, as long as the "latest state" of PG ended up in ES within a reasonable timeframe everything was fine so maybe your requirements are different.
This is especially useful if you have lots of different teams/code paths that may update your DB - just set up a trigger that causes a NOTIFY message to get sent, then have a client responsible for reading for PG and populating ES. Alternatively, if you can accept a bit more latency, just have a trigger that sets a "needsESIndexing" dirty column somewhere and have a polling process that picks rows WHERE needsESIndexing = TRUE and just updates this to FALSE when the indexing is complete.
https://docs.confluent.io/platform/current/connect/index.htm...
That’s a significant risk for things that need to be in sync between two systems, so we stuck with listen/notify for info-level ops things and used polling/queue systems that offered better guarantees for more important tasks. Don’t want to be in a position where a quiet hiccup with a deploy or something results in fun bugs like 0.5% of rows being silently out of sync between ES and Postgres.
We do something like this with our systems. External events get written to the event bus but all operations are idempotent on the event bus. So at night we send another round of the days events to clean up any inconsistencies.
[1] https://www.postgresql.org/docs/current/warm-standby.html#ST...
And any modifications to any field that was indexed, or having to update how things were indexed, was a chore thanks to referential integrity enforcement at the DB level: I had to remove and afterwards reapply things like foreign key constraints, triggers, stored procs, etc.... for both the "up" AND the "down"! Fortunately, since Postgres lets you make schema changes in a transaction, there usually wasn't anything to worry about integrity-wise.
The GIN index has some similarities to Elasticsearch's inverted indices (last I knew anyway), which also can be quite expensive to write to. If you're doing heavy writes, something to test and consider carefully.
TLDR; writes get a lot more expensive with GIN indices.
A cron runs every 5 minutes that looks at your database for any objects you're indexing where last_modified_at timestamp > last_indexing_started_timestamp.
Index the objects into Elasticsearch, then update the last_indexing_started_timestamp value to be when you started the original sync process, so we catch any modified objects between the start/end of the update run, next run.
Then if Elasticsearch needs rebuilding you can just clear out the last indexing timestamp and resync from the start of time, and its self-recovering / won't get out of sync.
Your record in ES might include data from many different tables, and figuring out what to (efficiently) update when there is a change in Postgres is not a simple task.
Are there any generic, algorithmic or even just heuristics that help with this?
It’s something I‘ve been thinking about over some time now. Any pointers, strategies and tips are appreciated.
Anything that is a dependency in the elastisearch index should trigger a job to export to it. And since it is idempotent it doesn't matter if it accidentally exports two or ten times the same index in a bg job. Just make sure before writing that you do a quick check that you're not overriding a fresher one. So just have a freshness timestamp which is the latest timestamp of any record used in the indexing data.
Furthermore you can do a daily job to just re export a critical part of the index. Doesn't matter if it is or isn't fresh. So let's say you query all records that were modified in the last day, and trigger the export job thatnmaynincludebthat record. Even if it causes duicate work. Idempotency saves you there.
https://joist-orm.io/docs/advanced/full-text-search
Granted, currently we still do pgsearch against this derived field, but could sync it over to ES.
In my case I'm using Solr and my last_indexed field isn't written to until the Solr index call completes without error. I have a very basic lock on the indexing process which hasn't failed me yet, and if it ever did fail the consequences would only be wasted CPU cycles. I consider that a lower risk than updating last_indexed only to have the actual indexing fail unexpectedly.
In the rare instances I've needed to re-index from scratch the process has been incredibly simple:
1. Start a new instance of Solr on a powerful AWS instance and direct index updates to it
2. Set all last_indexed fields to NULL
3. Wait for the scheduled task to complete the re-indexing
4. Reboot the new Solr instance on a sufficient AWS instance
5. Shift to the new Solr instance for search engine reads
There's also pgsync[0], but again, this is just from some preliminary research on my part, can't speak to relative or absolute quality for either option.
Overall it was a success - our ops work is very much reduced, enough so to have easily paid for the engineering time invested. Not to be undertaken lightly though.
Depending on your needs, you may be better served by materialised views, normal views, or triggers. The builtin text search may not suit your use cases; it’s not necessarily hard to come up with alternative schemes.
Without caching, the cost of operating the site would dramatically escalate.
It gets tough with pages with 100k+ comments though, so there are different tricks and switches for different flows and data sizes.
Can't recall if it was "just" a bunch of FPGAs but it was a big-ass PCI card.
Some years later I tried to find this story again, and to check if they still used it. Turned out they had ditched it after just a couple of years. As memory sizes had increased, they could just precompute all possible routes for the next day and keep them all in memory...
> From that perspective, fast search results aren't actually that exciting since you can constantly run a background task to update the cached results and just serve those as the requests come in.
If that's how it worked, I agree, it wouldn't be that impressive (every search result would just be a 1-1 cache lookup). That's not how it works, though, and as someone who works adjacent to the system, it is pretty impressive how fast it is when the work it's doing is actually pretty expensive.
So the benefits of ES/etc are being able to scale horizontally scale across nodes or any additional features it adds on top of the main index.
I plan a follow up to compare it with Elasticsearch, however, I don't think I'm going to attempt benchmarking, because whatever realistic scenario I come up with, it will not necessarily be relevant to your use case.
I mostly agree with you and I probably wouldn't use this at large scale (say, more than a few million records). I was primarily interested how much of the functionality I can replicate. Because for small search use cases this has some clear advantages: less infra to maintain, strong consistency, joins, etc.
Also, at Xata we're thinking about having a smooth transition between using Postgres at small scale, then migrating to use Elasticsearch with minimal breaking changes.
If you can start with Postgres to have a relational database with the benefit of Full Text Search (i.e. avoid Elastisearch) as well as JSON fields (i.e. avoid MongoDB) then you end up simplifying initial hardware/software requirements while retaining the ability to migrate to those solutions when user demand requires it.
So many developers seem to build with the idea that they'll become the next FAANG when actual (or reasonably forecasted) user load doesn't remotely require such a complex software stack.
> "It is hard for less experienced developers to appreciate how rarely architecting for future requirements / applications turns out net-positive."
— John Carmack
My only point is that making an architecture decision because it will immediately reduce complexity is much more sensible than basing your choice on potential future needs.
Evaluating needs from a "complexity reduction" standpoint is safe and will net returns. Evaluating needs from a "potential risks" standpoint is a lot harder, and easy to do wrong; the true risk is not growing at all, so the heuristic for any new project should be to do the simplest possible thing that solves the problem and starts the scaling process (i.e. whatever produces a saleable product).
The other benefit to starting with uncomplicated architecture is that you leave yourself with more scaling vectors, so once you deeply understand the problem(s) you actually need to solve, you can pick the right tool.
For us, Postgres FTS covered 95% of our use-cases. If we had started by just using ElasticSearch, we would have had a lot more complexity to maintain, and we would never have discovered our current (surprisingly elegant) architecture.
Then if FTS won't scale to unpredictable future needs it should be easier to rip out and replace with ES or anything else. And one doesn't have to pay that cost if/until it's certainly a requirement.
It ended up that doing a offline batch job to boil down the much bigger dataset into a single pre-optimized table was the best approach for us. Once optimized and tsvectored it was fairly performant and not a huge gain with Elastic. Still keeping the elastic code around “in case”, but yeah, Postgres search can be “good enough” when you aren’t serving a ton of clients.
Google indexed the same sites as Altavista, but Google Page Rank made the right sites bubble to the top and made Sergey and Larry billionaires...
Ranking is definitely easier when you also provide and moderate the content. That implies the technical solutions might differ qualitatively.
select *
from table
where ts_query(...)
order by relevance_metric
select *
from (
select *
from table
where ts_query(...)
order by ts_rank(...)
limit 1000
)
order by relevance_metric
limit 10Therein lies the problem - how do you generate actual realistic loads for a search engine without having a large number of people use it for searches? Simply hitting it with random search terms isn't realistic.
Some people will be on slow connections, search terms for something specific might spike in only a certain region (earthquake, etc), etc.
If your terms are too random, it'll perform worse than it should (results not in the cache), and if not random enough it will perform better than it should.
Mind you, this was 10-15 years ago, so thing will have changed and improved. I know the indices have become a lot faster since then.
It's actually very easy to make a fast basic database and search engine, even as an amateur programmer. As long as you understand basic CS algorithms and how to exploit the operating system and hardware, you can put one together in a month or two. Speed is not bad even with high-level languages; something like 250K QPS, back in 2003, on a laptop. Scalability isn't much of an issue either if you shard it. Indexing, locking, and consistency are more complicated than the storage and retrieval parts.
The big problem to overcome is the subjective nature of search. What do I really want to find? How do I find something when I don't know what I'm looking for? How do I get around people trying to game the system? How do I handle complex queries and datasets? That's when it gets orders of magnitude harder.
- everything was in RAM,
- it was written in a compiled language, and
- probably skipped worrying about too many crazy edge cases
I've seen a lot of ES and Solr clusters operating at 100% of 10+ nodes during a re-index, or just 30-50% of 10+ nodes during normal operation. The corresponding database would be say an AWS L/XL instance at 50-100GB of data and 30% CPU utilization. Moving all of the search CPU into your primary DB means now you'd have to shard it.
But I love PG extensions for search, recursive joins, vectors, etc on side projects. It can keep things fun and simple.
But in practice, you want to fix a bug in chinese tokenization, or OpenAI releases the next version of its embeddings, or you want to add a few synonyms, or change the aggressiveness of the stemmer.
Then you have to rewrite your whole search index, and if its part of your primary db, you're pretty sad.
https://austingwalters.com/fast-full-text-search-in-postgres...
The website is https://askhn.ai for the moment
Sorry I’m on spotty mobile that can’t open anything besides HN lol (God bless this website).
Sometimes it is just easier to use the existing systems and squeeze them as much as possible. Especially when it’s a small team or solo without much $$
https://vespa.ai is a purpose built search engine.
If you start bolting search onto your database, your relevance will be terrible, you'll be rewriting a lot of table stakes tools/features from scratch, and your technical debt will skyrocket.
It makes much more operational sense to use pg_vector if your use case can be implemented tha way.
You're going to spend a bunch of time writing integrations that already exist for actual search engines, and you're going to be stuck and need to back out when search becomes a necessity rather than an afterthought.
From my vantage point, you’re both right in the appropriate context.
If you have two systems, then you have two (unique) answers for HA,DR,Shard,Replica,Backup - the PG set and the Vespa.
That's more complicated, from an operational perspective.
PG FTS is quite good, and there are in-pg methods that can improve it.
And, from experience, when it's item to upscale to Solr/ES/etc it's not a very heavy lift.
Give it a try, it is very powerful
https://www.postgresonline.com/article_pfriendly/169.html
This could wastly speed up query but with added cost of more memory usage and operation time during updates.
Should I go the Postgres/Elasticsearch route or are somewhat out-of-the-box solutions available?
I haven't finished getting it set up though, so take this recommendation with a hefty grain of salt.
Elasticsearch is heavy, and relational databases with search bolted on (like Postgres or SQLite) aren't great.
Here's a git repo someone can modify to do a cross comparison on a specific dataset, if they are interested. It doesn't seem to indicate the RMDBs are outclassed in a small-scale FTS implementation.
Typesense
[timing] phrase [superman]: returned [28] results in 4.222797.ms
[timing] phrase [suprman]: returned [28] results in 3.663458.ms
[timing] phrase [superman]: returned [47] results in 0.351138.ms
[timing] phrase [suprman]: returned [0] results in 0.07513.ms
This adds a step between query entry and text search where you find the similarity of query words to unique lexemes if the word is not a lexeme. Seems like a reasonable compromise to me?
Podcastsaver.com (click on the nerds tab in the top right)
Never got to it but there are a bunch of other search engines worth adding — Sonic, Typesense, etc. Maybe some day
Scraping is a separate subject, but once you write one you can generally reuse relevant portions for many others. If you can get adept at a scraping framework like Scrapy you can do it fairly quickly, but there aren't many tools that work out of the box for every site you'll encounter.
Once you've written the spider, it's generally able to be rerun for updates unless the site code is dramatically altered. It really comes down to how brittle the spider is coded (i.e. hunting for specific heading sizes or fonts or something) instead of grabbing the underlying JSON/XHR that doesn't usually change frequently.
https://github.com/mozilla/readability
Btw, readability, is also available in few other languages like Kotlin:
You can also design more complex boosters, for example, boost by the rating,
but only if the ranking has a certain number of votes. To do this, you can
create a function like this:
create function numericBooster(rating numeric, votes numeric, voteThreshold numeric)
returns numeric as $$
select case when votes < voteThreshold then 0 else rating end;
$$ language sql;
In case you care, my comment from a few years: https://news.ycombinator.com/item?id=27977526
On top of that SQLite is now viable in the browser with WASM and the "origin privet file system" api. And so people are increasing looking at moving more state and persistence to the browser with an eventually consistent sync. This is what the "Local First" movement, myself included, are excited about.
It was not designed for "AI usage" or as a "AI database"
SQlite is from 2000 and is more comparable to a single file postgres/mysql database.
It's also on literally billions of devices including whatever you're reading this on.
Depending on the use case it can scale incredibly well, and is tiny and battle hardened.
It's the most deployed database, it's on every smartphone, "smart device", computer, it's inside of many of your apps, powers many of the websites you use, etc.
---
tl;dr - If you're following "use the simplest, but reliable tool for the job" then sqlite is a valid option for a crapload of use cases, most people aren't aware of what it can actually do because it doesn't "web scale".
Sqlite isn't new, it's old, and it's "used in production" count is in the literal billions.
Probably not something you want to run a multi tenant SaaS database with, but it is useful if you are going the one tenant per database route.
Of course, CoreData sucks, but that's for unrelated reasons.
It was incredibly fast, so much so that I found it more useful than github search. The index is pretty out of date now but I still use it purely based on convenience and speed
In the upcoming version, we've also added the ability to automatically generate embeddings from within Typesense either using OpenAI, PaLM API or a built-in model like s-bert or E5. So you only have to send json and pick a model, Typesense will then do a hybrid vector+keyword search for queries.