[SQL] Optimize the database statements

[tbe]

Requirements

• Is this a feature request? For questions or discussions use https://lemmy.ml/c/lemmy_support
• Did you check to see if this issue already exists?
• Is this only a feature request? Do not put multiple feature requests in one issue.
• Is this a backend issue? Use the lemmy-ui repo for UI / frontend issues.

Is your proposal related to a problem?

Lemmy's SQL statements have some major issues. Besides the one that surfaced in #3306 , there are a number of others:

paging is unstable

Paging in the database is unstable. For example: We fetch 100 comments, ordered by hot ranking. The user reads those comments and scrolls on. In the meantime, comment on position 101 gets upvoted, climps the ranking is now in position 90. The user will not see this comment, because the database content and as such, the order is now different.

paging hurts the database

ORDER BY, LIMIT and OFFSET are a bad combination. The Database does the following steps (in this order)

1. Execute the statement
2. Sorts the WHOLE result set (if we have many columns, we sort many columns. If they are wide, we sort a bunch of data)
3. Seeks to the offset position
4. returns $LIMIT number of entries

If the result set is large, and PostgreSQL can not fit it in the work memory, it sorts on disk. If the topic is hot, each request will start a sort on disk, killing the server with IO

ultra wide joins

There are many statements that do a huge bunch of joins. The PostgreSQL query optimizer is based on statistics for tables. While queries can be planned very efficiently with some joins, the plans can go bad really fast, if there are many joins.

The reason for this is, that the planner does not know about the correlation between to columns in different tables.

Fulltext search

There is no fulltext search index on the whole schema

Describe the solution you'd like.

paging

Avoid paging in the database at all costs. One way to do this is for example:

1. Fetch all ID's to show (only the ID's), if required, order them first
2. Store these ID's somewhere (session, return via API, whatever fits)
3. The client takes the first 100 ids, and requests them to view
4. For the next page, the client requests the next 100 ids

The ordering stays stable, no paging is required on the database side.

Joins

The join issue is a bit more difficult to solve. But a good approach are CTE's. Materialized CTE's can be used to force an execution order, while normal CTE's leave it to the planner but provide readability and features that are not otherwise possible (like recursion for comment trees)

Fulltext search

Using tsvector operations should fix this.

Describe alternatives you've considered.

There is none. The current statements are a real issue, if not the biggest issue, for lemmys performance and stability

Additional context

I'm willing to help here. But this requires a deep understanding of the logic behind the queries, and what should be archived with them.

Feel free to contact me on lemmy (vapeloki@lemmy.{ml,world} or visit us in !lemmyperformance@lemmy.ml

[dessalines]

@tbe You can pull down the code and run it locally, to check the DB to see the current indexes and such.

The current index on the path column is "idx_path_gist" gist (path)

ltree's are postgres's official way to store / query tree-like data.

The difficulty, which is out of my SQL depth, is how to do tree paging. I do have a setup in place which is able to page depth, but not the top-level comments. Its a very complicated topic that I could definitely use some assistance with.

I've re-opened that issue here because I clearly did not solve it, now that we're getting comment threads with thousands of top-level comments. #949 .

[dessalines]

As to the wide join speed issue, @johanndt found a great way to optimize the existing queries: to do a subselect before the rest of the heavy joins. #2994

Implementing that for a lot of the tables is a priority for me when I get done with a few other things.

I also don't see why you think fetching ALL results is going to be faster than limit and offset. Some comment tables have hundreds of thousands of comments. Fetching and loading them all in memory, then sorting in code, is not a good solution. Best to leave SQL to do what its good at: querying data.

[tbe]

The difficulty, which is out of my SQL depth, is how to do tree paging. I do have a setup in place which is able to page depth, but not the top-level comments. Its a very complicated topic that I could definitely use some assistance with.

I had some more thoughts about it this weekend. And the best i can come of with is still the same: Don't page inside the database.

I had a look around how others system page. Paging is fine, as long as our order does not change. For example for ordering by old, this may work. But: As soon as we have trees, that will not work.

So, there are two options:

• Don't page at all. But this would do no good to API consumers on huge topics.
• Page on the client side. As recommended before: We build one tree, but without the contents, only the ID's, and let the client request the contents and metadata as required.

I know, this will introduce breaking API changes, but i don't see an alternate route.

Added bonus: We can later on cache the contents of comments, and only ask the database if we don't have a specific comment yet. Caching paged trees does not work on active discussions.

[tbe]

I also don't see why you think fetching ALL results is going to be faster than limit and offset. Some comment tables have hundreds of thousands of comments. Fetching and loading them all in memory, then sorting in code, is not a good solution. Best to leave SQL to do what its good at: querying data.

1. Ordering only the ID's based on 2 or 3 columns needs far less memory (or disk) then ordering the whole result set
2. It is stable. We only have to do this once per caller, not for each call
3. ORDER, LIMIT and OFFSET is bad, as state above, because it always needs to sort the whole dataset first, before applying LIMIT and OFFSET. So, there is no difference here in runtime, but as it has to be done for each call, a huge difference in the time that it is executed.

Also, even if we find a way to do this better inside the database, we would still run in the issue, that ordering may change between request for page 1 and page 2, leading to duplicate shown and "hidden" comments.

[tbe]

As to the wide join speed issue, @johanndt found a great way to optimize the existing queries: to do a subselect before the rest of the heavy joins.

This is a pretty good way to do it. I would recommend rewriting this to use CTE's instead of subselects, but the outcome should be the same.

Why CTE?

• Better readability
• Easier to maintain
• CTE's can be used for different statements, without worrying about nesting and such

[tbe]

It means that the database has to do the filtering for each individual user doing blocking of other users, and some people really like to ignore other human beings and have large lists of blocks.

And this is fine with negative joins. PostgreSQL is really amazing here on the generated plans. I wouldn't worry about this, as, like @dessalines wrote, that is what the database is good at.

From a performance perspective, sorting makes repeat queries difficult to cache alone, but having each user ask the database to filter on every fetch is heavy and a potential denial of service opening.

The idea should be, that later on we can cache as much as possible. But at least a TOC for the current comments must be fetched fresh. And those, uncacheable, queries, should be as light wight as possible.

[johanndt]

paging is unstable

Paging in the database is unstable. For example: We fetch 100 comments, ordered by hot ranking. The user reads those comments and scrolls on. In the meantime, comment on position 101 gets upvoted, climps the ranking is now in position 90. The user will not see this comment, because the database content and as such, the order is now different.

I don't see why this is a problem? Literally every other forum software works this way. Even Reddit works this way. If you view the front page, and then after a while load page 2 (old reddit at least) then the posts might've moved around as you say and you might've missed something. But it does not really appear to be a big issue, since most people will scroll scroll scroll... or page page page, and then go back to the front page and reload.

I don't feel like this is surprising to the user, and in fact is probably what they would expect.

Ultimately it's not up to me, but I don't think paging is broken and adding lots of complexity is not worth it. Or maybe I'm misunderstanding the issue.

[tbe]

I don't see why this is a problem? Literally every other forum software works this way. Even Reddit works this way. If you view the front page, and then after a while load page 2 (old reddit at least) then the posts might've moved around as you say and you might've missed something. But it does not really appear to be a big issue, since most people will scroll scroll scroll... or page page page, and then go back to the front page and reload.

This is not so much an issue for Posts. But it is for comments. And reddit does not work this way on comments. They don't page on comments in this way. If i click on "show more replies", the client side JS sends a token, containing the information to identify the first paging data, and proceeds from there.

Also, some "forum" software does not need to order stuff like lemmy does. There is no "hot", "active", "top" ordering. The ordering is always "oldest first". So there is no paging issue regarding the order.

[johanndt]

This is not so much an issue for Posts. But it is for comments.

Ah okay! I was thinking of posts, yes. You're right.

[tbe]

One of the major problems it that there is little to no caching at all, no second-teir caching that is routine in server applications.

You can cache the contents of comments, if you are willing to "hide" edits for a few seconds or so. But you can not cache the comment tree, as this is a thing that changes fast. Only caching requested stuff makes sense, so filtering in the database is a viable thing, at it is for a non-cachable result anyways.

[tbe]

The Rust code is hiding the problems, and the application crash logs of lemmy_server is a platinum mine of scaling problems.

Can we please limit this discussion to SQL/Database stuff? The API issue, that the error handler of the rust server does not return JSON, is a separete topic

[tbe]

If it isn't the SQL faulting, what is it?

We have trouble with SQL, that's why i'm here after all. Yes. But that an error handler on the HTTP side, does not respond in JSON, that can happen on everything, and is clearly not SQL related.

[tbe]

Last time i try this @RocketDerp :

Yes, that the JSON API Errors are not JSON in many cases is an issue, but not this one. It also isn't about who has done what.

This is an issue tracker. Not a post on a lemmy instance. Open a new issue for the error messages, and keep this issue clean. Else, it become unhandable by the maintainers, and people that are willing to contribute.

[tbe]

During load testing, i have seen, that there is one statement, that is executed far to often, and leads to duplicate entries on the database:

INSERT INTO "local_user_language" ("local_user_id", "language_id") VALUES ($1, $2) RETURNING "local_user_language"."id", "local_user_language"."local_user_id", "local_user_language"."language_id"

This statement is responsible for the most writes, and most WAL records of all:

I tried to track it down, but i can not find the source. I don't understand the ORM.

@dessalines : any clue where to start?

[L3v3L]

maybe this:

lemmy/crates/db_schema/src/impls/actor_language.rs

Line 108 in ad6f244

insert_into(local_user_language)

[tbe]

Thank you @L3v3L ! Not as bad as i thought, but also: not good. If a user signs up without a given language, all 184 ID's are inserted in this table.

[dessalines]

That local_user_language is kind of a mess, and it very much needs simplifying.

[dessalines]

There's a matrix chat for that you can join, where people are providing logs and showing slow queries. You can also do that here, just make an issue and use the DB tag, so that people can work on it.

Also @RocketDerp be respectful, or we will block you from this repo.

[JustAnotherSoftwareDeveloper]

@RocketDerp so read back the comment thread from the top. The two other main contributors from this thread are more or less having a discussion on their own. While they have not explicitly said so, I'm under the impression that they don't feel your contributions are necessary on this ticket and would rather you move off this ticket.

This isn't any reflection of you as a person. Most of the other voices on this thread have deep domain-specific technical knowledge of what's going on. Ultimately, some conversations need to be left up to people with specific expertise on said conversations.

I do not have the expertise to contribute to this process. I am, however, a professional software engineer. At basically every job I've worked at there has been a situation where this an "obvious fix" that is actually prohibitively difficult or wholly ineffective. I would not be surprised if your suggestions fall into that category (though again I have no direct insights).

@dessalines would you say that is a pretty accurate description of what's going on? That's my read of it but obviously you can speak for yourself.

[dessalines]

I think we're all good now. The scope on this one is a bit too large, to I encourage ppl to open up separate issues for specific DB related issues.