11 ms·
Creating a search engine with PostgreSQL
- esafak 3y agop50/p99 retrieval times at realistic loads or it didn't happen. A search engine that returns results in, say, a minute is not "advanced". Of course a relational database like Postgres can do it on paper.
- deleted 3y ago[deleted]
- nanidin 3y agoI interviewed somewhere with an ex-Googler who revealed they cache all of the search results for terms they have seen before, then when they update the index they also update the cached results. 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. This caching and response time seem orthogonal to the speed of the actual act of calculating search results.
- TX81Z 3y agoAlmost everything is faster if you can precompute.
- bshipp 3y agoFor sure, but the approach is quite viable. If 19 out of 20 searches by a user are almost instantaneous and single novel one requires a few seconds, they'll assume a hiccup in their internet connection and still view the site as "really fast". It's certainly useful for limiting demands on expensive hardware.
- teej 3y ago20% of all Google searches are brand new
- andrelaszlo 3y agoAnd use 80% of the resources?
- TX81Z 3y agoEh, a non trivial % of those are likely just brand new misspellings.
- bagels 3y agoThen 80% aren't, and those ones will perform very well.
- paxys 3y agoThe other 20% also perform well. I have quite literally never encountered a Google search that took more than some tens of milliseconds for a round trip.
- bshipp 3y agoYou're absolutely correct. Caching common search queries allows the site to allocate hardware for processing "expensive" queries, with the objective of having both complete at near the same time. Without caching, the cost of operating the site would dramatically escalate.
- winrid 3y agoYup, all FastComments threads are precomputed for all sort directions! Each page comes from the DB in < 1.5ms 75% of the time. It gets tough with pages with 100k+ comments though, so there are different tricks and switches for different flows and data sizes.
- qingcharles 3y agoYour site is killing me. Every page I visit I have to accept the cookies :(
- winddude 3y agowhich is why es uses multiple levels of caching
- magicalhippo 3y agoI recall reading about the local transit department which had gotten some fancy accelerator card to help with route searches, ie when a customer wanted to go from A to B, which busses, trams etc to take. 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...
- nosefrog 3y agoI work on Google Search infrastructure. Of course, caching is important, but a large percentage of queries don't hit the cache. The backend that serves results that aren't cached has very strict latency bounds. > 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.
- karmakaze 3y agoLucene (what Elasticsearch and Solr use) are based on inverted indexes which is what the GIN in the article also uses. 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.
- tudorg 3y ago(disclaimer: author of the post) 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.
- bshipp 3y agoUsing measured comparisons and making informed choices is certainly the best way. 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.
- vlovich123 3y agoI think you’re being ungenerous in the reasoning. The initial setup to get something running is similar while a specific technology may scale better. From that perspective, you may be better off picking ES to avoid paying back technical debt if you do need to grow. Early strategic investments help - sure, you won’t get everything right, but getting enough things right can be the difference between the sales channel being bottlenecks on deal flow vs on engineering. The former can be a lot faster to resolve than the latter.
- sebmellen 3y agoNo failed company ever failed because of a lack of technical complexity, nor have successful companies been held back by not adopting complex architectures early. > "It is hard for less experienced developers to appreciate how rarely architecting for future requirements / applications turns out net-positive." — John Carmack https://en.m.wikipedia.org/wiki/You_aren%27t_gonna_need_it https://en.m.wikipedia.org/wiki/You_aren%27t_gonna_need_it
- ramraj07 3y agoWe use postgres fts and it works fine, you just gotta how you rank order the rows in the query - if you only use ts_rank then it's perfect but you likely want to use some other relevance metric to adjust the ranking but then you can't rank order primarily by that metric. Once you nail this the results are as fast as any other typical db table query with an index.
- glintik 3y agoActually good ranking is the most valuable thing in search engine.
- qingcharles 3y agoGood ranking is what made Google a trillion dollar company. 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...
- dgb23 3y agoYou’re right. But at the same time that quality seems to decline or at least stagnate. I think they face the hard problem of an decreasing signal to noise ratio. Ranking is definitely easier when you also provide and moderate the content. That implies the technical solutions might differ qualitatively.
- ramraj07 3y agoWhat I mean is you can't do select * from table where ts_query(...) order by relevance_metric but instead do select * from ( select * from table where ts_query(...) order by ts_rank(...) limit 1000 ) order by relevance_metric limit 10
- deleted 3y ago[deleted]
- lelanthran 3y ago> p50/p99 retrieval times at realistic loads or it didn't happen. Therein 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.
- gleenn 3y agoOne actual solution is to use historical search logs. Just because "random" is a bad answer doesn't mean people don't try and make reasonable reproductions of load to replay and benchmark. Cacheing is also a big factor.
- joking 3y agoI don't know if this is true for elasticsearch, but at least with solr, when you update an index, the default is to run some of the queries in the cache of the old searcher to warm up the new one.
- boesboes 3y agoI've tried using PG FTS in a real application, it didn't scale very well. It worked well for 100s-1000s of records, but after that queries would quickly go from a few ms to like 500ms. And another 400ms for highlighting. 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.
- hot_gril 3y agoI've built something like this before, and it was pretty fast. What load could one node have supported, I have no idea, but read-only operations can be spread across replicas easily.
- asadawadia 3y agohttps://rcs.aawadia.dev/ https://rcs.aawadia.dev/ is also using pg search
- rane 3y agoHow does SQLite fare against PostgreSQL for this particular use case?
- shortrounddev2 3y agoWhy do I see so much discussion about SQLite on HN? I've literally never seen it used in production, my usage of it is purely as a database for local testing
- bshipp 3y agoSqlite is extremely powerful for any locally-embedded databases, such as apps with an offline component. For example, searching text in notes, books, cached news, etc. It's very simple to implement inside Sqlite with much less overhead than including a Postgres/Mysql instance.
- klysm 3y agoIt’s used in production quite a bit, probably just not in your field as much. Anytime I’m thinking about storing something in a file I use SQLite instead
- TX81Z 3y agoLol, you’re using it “in production” right now! SQLite is everywhere, almost definitely in the browser you’re using to view this post.
- shortrounddev2 3y agoI guess it's a difference in industry. Everything I do is accessed over a network, and for caching we use simpler key-store libraries rather than relational databases. I don't develop client software
- TX81Z 3y agoOh I don’t currently have it in my stack per se, more that it is all over the damn place and can do a ton.
- b1zguy 3y agoI've been meaning to attempt running a custom search engine for particular sites I've 'bookmarked'. Some sites contain gold that could be useful in the future and is not often discovered in Google results. Should I go the Postgres/Elasticsearch route or are somewhat out-of-the-box solutions available?
- Alifatisk 3y agoSearchkick gem + Elasticsearch is a good combo
- sudobash1 3y agoI am wanting to do something similar. Archivebox seems to be the best solution for this sort of self-hosted, searchable web archive. It has multiple search back-ends and plugins to sync browser bookmarks (or even history). I haven't finished getting it set up though, so take this recommendation with a hefty grain of salt.
- SpriglyElixir12 3y agoHow would something like this work in practice? Would you generate any tags or summaries per site when inserting it into the db?
- janalsncm 3y agoYou could run a full text search or search against an auto-generated summary. Or if you want to be fancy, use semantic search like in Retrieval Augmented Generation.
- sudobash1 3y agoArchiveBox can extract text from HTML (and possibly PDFs too). I think it can be configured to extract subtitles from YouTube videos as well. So it can do full text searches. Basically you could have your own, offline & curated search-engine.
- bshipp 3y ago
- lettergram 3y agoI’ve actually done this before and made it pretty damn fast - https://austingwalters.com/fast-full-text-search-in-postgresql/ https://austingwalters.com/fast-full-text-search-in-postgres... The website is https://askhn.ai https://askhn.ai for the moment
- lionkor 3y agoFYI the askhn.ai sub-title "Discover, Manage, Query...." is kerned[1] horribly [1]: https://en.wikipedia.org/wiki/Kerning https://en.wikipedia.org/wiki/Kerning
- quartz 3y agoYou can also marry these techniques with pgvector to find related content through embeddings. I've found this to be pretty magical.
- jstummbillig 3y agoCould you get into some more detail or point at something that does?
- kaycebasques 3y agohttps://supabase.com/blog/openai-embeddings-postgres-vector https://supabase.com/blog/openai-embeddings-postgres-vector https://supabase.com/blog/chatgpt-supabase-docs https://supabase.com/blog/chatgpt-supabase-docs
- binarymax 3y agoIt's interesting that folks go down this hacky route when they can use something like Vespa, which is orders of magnitude better from a performance, relevance, scalability, and developer ergonomics perspective.
- deleted 3y ago[deleted]
- moomoo11 3y agoIs that a different system? 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 $$
- binarymax 3y agoWhen it comes to search I cannot disagree more. https://vespa.ai 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.
- endisneigh 3y agoFor something like this I'd use FoundationDB to store the entries redundantly and consistently with high availability and TypeSense for searching through the records and regenerating the index as necessary from FDB.
- esafak 3y agoDoes Typesense work with external vector databases?
- jabo 3y agoTypesense has a vector store / search built-in: https://typesense.org/docs/0.24.1/api/vector-search.html https://typesense.org/docs/0.24.1/api/vector-search.html 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.
- esafak 3y agoI see you run hnswlib but do you (plan to) support external vector databases, so users can upgrade?
- 0xbadcafebee 3y agoWhen I was a teenager I made a search engine and database from scratch, not knowing anything about either. I just wanted to see how far I could get, how fast I could make it, returning somewhat relevant search results. 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.
- gomezjdaniel 3y agoIt is open sourced anywhere? I am curious
- paxys 3y agoWhen building a search engine the biggest problem isn't QPS but the size of the data set you are indexing. If your search structures can fit in memory of a single machine then you can serve effective infinite QPS with ~zero latency. When it grows beyond that you have to get creative, and that's when all the different tradeoffs come into the picture.
- vlovich123 3y ago250k RPS seems like a lot when SQLite can’t do that today and I feel like inverted indices are more expensive (eg RocksDB gets to ~130k RPS but I think their numbers are on beefier hardware than my laptop or my machine isn’t set up well). Are you sure you wrote a general purpose database and those numbers are correct? I’m curious what you did to outperform these engines (I agree it’s possible, but I’m curious what techniques you employed)
- lionkor 3y ago
- daitangio 3y agoVery nice and clear article. Also SQLite offers advanced indexing functionality and stemming with a standard plugin. For english SQLite works well too
- paulryanrogers 3y agoI wonder if a FDW could do this. Since just replicating the to-be-searched data should have only a few writers it could work well for moderately sized data.
- daitangio 3y agoI have found my experiments with SQLite here https://github.com/daitangio/knowledge https://github.com/daitangio/knowledge Give it a try, it is very powerful
- _s_a_m_ 3y agoHas the word "advanced", must be good ..
- jsdwarf 3y agoLooking forward for part 2 / postgres vs elasticsearch. One application at my company uses PG for CRUD on objects and elastic for searching them. We completely underestimated the effort of keeping the two datastores in sync and are actually contemplating to get rid of elasticsearch.
- cameronpm 3y agoNormally best practice is to return primary keys in ES and then do a lookup query in the db. Did you attempt this?
- rajamaka 3y agoGot any links or documentation about this method by any chance? Not sure if you are talking about querying or syncing data here.
- lyu07282 3y agoI think what they just mean is that you only have all your searchable fields indexed in ES and then, when you do a search query, the only thing ES returns is PKs which you then do a second roundtrip to the database (or cache) with to get all the actual records from. Which means you don't have to worry too much about all the record information being in sync perfectly.
- dqv 3y ago>We completely underestimated the effort of keeping the two datastores in sync and are actually contemplating to get rid of elasticsearch. 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.
- valzam 3y agoI had a similar setup at a previous gig and didn't find it particularly challenging. Whenever an update happens to an entity in PG we send a message to async replicate that entity in ES (via ID lookup in PG). As always you need good monitoring and retries for async computation but ES is quite stable and fast so we rarely had any issues. 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.
- fizx 3y agoOne of the many problems with search inside Postgres is that search is very CPU-heavy (and starting to become GPU-heavy). Ideally, you'd like to reserve CPU in your database for transactional updates to your core data model. 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.
- nbgoodall 3y agoCould you solve this by searching on a read-only replica?
- Spivak 3y agoConvincing your devs to keep two handles two the db, one for reads one for writes from the beginning is a blessing.
- dgb23 3y agoCan you elaborate?
- Spivak 3y agoDetermining whether a query is appropriate to hit the read replica is something I've never seen done automatically and well. But if you design your system from the beginning that when you make queries the developer chooses whether to hit the reader or writer by way of essentially do_query / do_query_reader then it's a million times easier scale reads and it doesn't have to come with any additional operational complexity when you're small you can just have both handles point to the writer but have a read-only user or set TRANSACTION READ ONLY on the session.
- hot_gril 3y ago
- v0idzer0 3y agoFYI it’s “Darth” Vader not “Dark” Vader. I too thought it was “Dark” as a kid
- topato 3y agoI couldn't concentrate on anything in this post, it was so distracting. How can you know Yoda quotes, but you're still saying Dark Vader?!
- remram 3y agoIt's actually Dark Vador in some translations such as French, which makes the "error" common.
- tudorg 3y agoThanks, fixed it. That was embarrassing :)
- catsarebetter 3y agoThis is the first I'm seeing this. So it's abstracting the business logic of the API (ie. GraphQL) into the database? What are we trading off here?
- xhax 3y agoThis looks cool as heck. +1
- deleted 3y ago[deleted]
- kaveh_h 3y agoNice article, although the part on fuzzy search not being supported by PostgreSQL is partly incorrect. The pg_trgm extension and an GIN trigram index supports the use case of fuzzy search like in the example in this article: https://www.postgresonline.com/article_pfriendly/169.html 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.
- almost 3y agoPostgreSQL’s pg_trgm extension is also very useful. If you want to be able to search and find partial words etc then trigram indexes can be more useful than full text indexes. I’ve made the mistake of just chucking full text search at the problem before and often it doesn’t give the results you might want.
- clothval 3y ago[dead]
- some_developer 3y agoEvery time I read blogs like this I'm tempting to get back to the product, still in use, where we scraped the search integration due to the issues we had with pgsql (performance). Although ElasticSearch (nowadays: OpenSearch) is available, we never deemed it important enough for this part of the product. In case you care, my comment from a few years: https://news.ycombinator.com/item?id=27977526 https://news.ycombinator.com/item?id=27977526
- renegade-otter 3y agoPlease do not try to do this while attempting to mirror Elastic Search capabilities. 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.
- bshipp 3y agoI think this comment highlights the two separate discussions going on in this thread. If you're building a customer-facing search engine, avoid reinventing the wheel by leveraging powerful tools like elastisearch. 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.
- indigo945 3y agoYou 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; There's really no need to use a function here. It does nothing and makes the code at the call site harder to understand. Additionally, using a function might incur unintended performance penalities. At the very least, the function should be marked IMMUTABLE LEAKPROOF PARALLEL SAFE.
- pcthrowaway 3y agoWhy does this site break keyboard navigation? Having to scroll with my mouse only is kind of annoying, but also means I can't page-up and pain-down
- bunkerstake 3y agothanks for this!