SQL query utilizes processor up to 100% and ends with timeout

[ratermir]

I have quite a lot bookmarks in several "root" folders. After some time when all worked perfectly, Bookmarks started to utilize SQL servar to the maximum. Every attempt to synchronize starts new query on the server, which doesn't finish and the sync ends with timeout. I didn't perform any update or changes on the server side between the time when all worked well and time when this issue started.

Nextcloud version: 20.0.13 (Docker - php FPM)
Bookmarks version: 4.4.1 and also the latest (surprisingly marked as 10.0.0)

I analyzed SQL queries on the MySQL (resp. Mariadb) and I found the SQL query which utilizes processor, which is this one:

SELECT b.id, b.url, b.title, b.description, b.lastmodified, b.added, b.clickcount, b.last_preview, b.available, b.archived_file, b.user_id, b.text_content, b.html_content, 
	GROUP_CONCAT(tree.parent_folder) AS folders, GROUP_CONCAT(t.tag) AS tags FROM oc_bookmarks b LEFT JOIN oc_bookmarks_tree tree ON b.id =tree.id AND tree.type = 'bookmark' 
	LEFT JOIN oc_bookmarks_tags t ON t.bookmark_id = b.id LEFT JOIN oc_bookmarks_tree tr ON tr.id = b.id AND tr.type = 'bookmark' LEFT JOIN oc_bookmarks_shared_folders sf ON tr.parent_folder = sf.folder_id 
	LEFT JOIN oc_bookmarks_tree tr2 ON tr2.id = tr.parent_folder AND tr2.type = 'folder' 
	LEFT JOIN oc_bookmarks_shared_folders sf2 ON tr2.parent_folder = sf.folder_id WHERE ((b.user_id = 'radek') OR (sf.user_id = 'radek') OR (sf2.user_id = 'radek')) AND (b.user_id IN ('radek')) 
	GROUP BY b.id, b.url, b.title, b.description, b.lastmodified, b.added, b.clickcount, b.last_preview, b.available, b.archived_file, b.user_id, b.text_content, b.html_content, b.id 
	ORDER BY b.lastmodified DESC, b.id ASC LIMIT 300 
	;

It could be hard to reproduce this issue - I may provide copy of my bookmarks (there's nothing secret there), but for the first look the query seems to be quite complex and complicated which could lead to non - optimal performance. MySQL is fast for simple queries, but sometimes really slow for more complex queries with bigger data quantity.

Process list on the SQL server luuks like this:

MariaDB [nextcloud]> SHOW PROCESSLIST;
+-----+-------------+-----------+-----------+---------+------+--------------------------+------------------------------------------------------------------------------------------------------+----------+
| Id  | User        | Host      | db        | Command | Time | State                    | Info                                                                                                 | Progress |
+-----+-------------+-----------+-----------+---------+------+--------------------------+------------------------------------------------------------------------------------------------------+----------+
|   1 | system user |           | NULL      | Daemon  | NULL | InnoDB purge worker      | NULL                                                                                                 |    0.000 |
|   2 | system user |           | NULL      | Daemon  | NULL | InnoDB purge coordinator | NULL                                                                                                 |    0.000 |
|   3 | system user |           | NULL      | Daemon  | NULL | InnoDB purge worker      | NULL                                                                                                 |    0.000 |
|   4 | system user |           | NULL      | Daemon  | NULL | InnoDB purge worker      | NULL                                                                                                 |    0.000 |
|   5 | system user |           | NULL      | Daemon  | NULL | InnoDB shutdown handler  | NULL                                                                                                 |    0.000 |
| 157 | nextcloud   | localhost | nextcloud | Query   | 3739 | Creating sort index      | SELECT `b`.`id`, `b`.`url`, `b`.`title`, `b`.`description`, `b`.`lastmodified`, `b`.`added`, `b`.`cl |    0.000 |
| 180 | nextcloud   | localhost | nextcloud | Query   | 3679 | Creating sort index      | SELECT `b`.`id`, `b`.`url`, `b`.`title`, `b`.`description`, `b`.`lastmodified`, `b`.`added`, `b`.`cl |    0.000 |
| 226 | nextcloud   | localhost | nextcloud | Query   | 3547 | Creating sort index      | SELECT `b`.`id`, `b`.`url`, `b`.`title`, `b`.`description`, `b`.`lastmodified`, `b`.`added`, `b`.`cl |    0.000 |
| 245 | nextcloud   | localhost | nextcloud | Query   | 3487 | Creating sort index      | SELECT `b`.`id`, `b`.`url`, `b`.`title`, `b`.`description`, `b`.`lastmodified`, `b`.`added`, `b`.`cl |    0.000 |
| 286 | nextcloud   | localhost | nextcloud | Query   | 3376 | Creating sort index      | SELECT `b`.`id`, `b`.`url`, `b`.`title`, `b`.`description`, `b`.`lastmodified`, `b`.`added`, `b`.`cl |    0.000 |
| 319 | nextcloud   | localhost | nextcloud | Query   | 3316 | Creating sort index      | SELECT `b`.`id`, `b`.`url`, `b`.`title`, `b`.`description`, `b`.`lastmodified`, `b`.`added`, `b`.`cl |    0.000 |
| 438 | nextcloud   | localhost | nextcloud | Query   | 3016 | Creating sort index      | SELECT `b`.`id`, `b`.`url`, `b`.`title`, `b`.`description`, `b`.`lastmodified`, `b`.`added`, `b`.`cl |    0.000 |
| 461 | nextcloud   | localhost | nextcloud | Query   | 2955 | Creating sort index      | SELECT `b`.`id`, `b`.`url`, `b`.`title`, `b`.`description`, `b`.`lastmodified`, `b`.`added`, `b`.`cl |    0.000 |
| 545 | nextcloud   | localhost | nextcloud | Query   | 2830 | Creating sort index      | SELECT `b`.`id`, `b`.`url`, `b`.`title`, `b`.`description`, `b`.`lastmodified`, `b`.`added`, `b`.`cl |    0.000 |
| 586 | nextcloud   | localhost | nextcloud | Query   | 2711 | Creating sort index      | SELECT `b`.`id`, `b`.`url`, `b`.`title`, `b`.`description`, `b`.`lastmodified`, `b`.`added`, `b`.`cl |    0.000 |
| 601 | nextcloud   | localhost | nextcloud | Query   | 2650 | Creating sort index      | SELECT `b`.`id`, `b`.`url`, `b`.`title`, `b`.`description`, `b`.`lastmodified`, `b`.`added`, `b`.`cl |    0.000 |
| 605 | root        | localhost | nextcloud | Query   |    0 | Init                     | SHOW PROCESSLIST                                                                                     |    0.000 |
| 677 | nextcloud   | localhost | nextcloud | Query   | 1329 | Creating sort index      | SELECT `b`.`id`, `b`.`url`, `b`.`title`, `b`.`description`, `b`.`lastmodified`, `b`.`added`, `b`.`cl |    0.000 |
+-----+-------------+-----------+-----------+---------+------+--------------------------+------------------------------------------------------------------------------------------------------+----------+

The result od the "EXPLAIN" command is this:

explain SELECT b.id, b.url, b.title, b.description, b.lastmodified, b.added, b.clickcount, b.last_preview, b.available, b.archived_file, b.user_id, b.text_content, b.html_content,  GROUP_CONCAT(tree.parent_folder) AS folders, GROUP_CONCAT(t.tag) AS tags FROM oc_bookmarks b LEFT JOIN oc_bookmarks_tree tree ON b.id =tree.id AND tree.type = 'bookmark'  LEFT JOIN oc_bookmarks_tags t ON t.bookmark_id = b.id LEFT JOIN oc_bookmarks_tree tr ON tr.id = b.id AND tr.type = 'bookmark' LEFT JOIN oc_bookmarks_shared_folders sf ON tr.parent_folder = sf.folder_id  LEFT JOIN oc_bookmarks_tree tr2 ON tr2.id = tr.parent_folder AND tr2.type = 'folder'  LEFT JOIN oc_bookmarks_shared_folders sf2 ON tr2.parent_folder = sf.folder_id WHERE ((b.user_id = 'radek') OR (sf.user_id = 'radek') OR (sf2.user_id = 'radek')) AND (b.user_id IN ('radek'))  GROUP BY b.id, b.url, b.title, b.description, b.lastmodified, b.added, b.clickcount, b.last_preview, b.available, b.archived_file, b.user_id, b.text_content, b.html_content, b.id  ORDER BY b.lastmodified DESC, b.id ASC LIMIT 300;
+------+-------------+-------+-------+---------------------------------------------------------------------+-------------------------+---------+----------------------------------+------+--------------------------------------------------------------+
| id   | select_type | table | type  | possible_keys                                                       | key                     | key_len | ref                              | rows | Extra                                                        |
+------+-------------+-------+-------+---------------------------------------------------------------------+-------------------------+---------+----------------------------------+------+--------------------------------------------------------------+
|    1 | SIMPLE      | b     | range | IDX_3EE1CD04A76ED395,bookmarks_deadbyuser,bookmarks_user_clickcount | IDX_3EE1CD04A76ED395    | 258     | NULL                             | 1164 | Using index condition; Using temporary; Using filesort       |
|    1 | SIMPLE      | tree  | ref   | PRIMARY                                                             | PRIMARY                 | 90      | nextcloud.b.id,const             | 2    | Using where; Using index                                     |
|    1 | SIMPLE      | t     | ref   | PRIMARY,bookmark_tag                                                | PRIMARY                 | 8       | nextcloud.b.id                   | 1    | Using index                                                  |
|    1 | SIMPLE      | tr    | ref   | PRIMARY                                                             | PRIMARY                 | 90      | nextcloud.b.id,const             | 2    | Using where; Using index                                     |
|    1 | SIMPLE      | sf    | ref   | bookmarks_shared_folder                                             | bookmarks_shared_folder | 8       | nextcloud.tr.parent_folder       | 1    | Using where                                                  |
|    1 | SIMPLE      | tr2   | ref   | PRIMARY                                                             | PRIMARY                 | 90      | nextcloud.tr.parent_folder,const | 2    | Using where; Using index                                     |
|    1 | SIMPLE      | sf2   | index | NULL                                                                | bookmarks_shared_user   | 1022    | NULL                             | 1    | Using where; Using index; Using join buffer (flat, BNL join) |
+------+-------------+-------+-------+---------------------------------------------------------------------+-------------------------+---------+----------------------------------+------+--------------------------------------------------------------+

[marcelklehr]

Yeah, that query has been problematic. Basically the problem is that for each bookmark we retrieve we want to get its tags and the folders it's in. The query you pasted does this in one go. Which loads the bulk of the work off to the database. The other option is to use a separate query for each bookmark, but that obviously results in O(n) queries :/

[marcelklehr]

How many users do you have and how many bookmarks do they have on average?

Looking at the EXPLAIn output, sorting 1164 rows doesn't sound too problematic, in theory, I think 🤔

[ratermir]

At he time I tested it only one user was active (me), otherwise totally 5 users, 2 has similar bookmarks quantity (around 1000), the rest only a few

[ratermir]

Now I realized that the cause of this may be an issue in the data, since when the query ran, MariaDB server consumed disk space until exhausted it (about 30 TB). The space has been released when I killed these queries. This could indicate to neverending loop (parent-chield cycle in the tree). But - of course - I didn't do any manual changes to the DB, so the cause must lay in the app (either server or client) .

[ratermir]

I've investigated my data a bit an I found several uncleaarances. How it is possible that one item has many (very very many in some cases) parents ?
For example: select count(*) from oc_bookmarks_tree where id=6286 returns 616 records (something like this:)

... etc

That tmeans that there must be something wrong in the logic how you identify the parent folder.
Every bookmark MUST HAVE only one (and exactly one) parent.

And it also corresponds with what I did - I rearranged bookmarks and folder (even if not so massive :) )
I don't know the sync logic, but I think id could be useful to remove all parents of particular bookmark / folder except the last one (from the latest sync).

Additionally I'd recommend to use hierarchical query - it is now supported by PostgreSQL, MariaDB and also by MYSQL.
Something like this:

WITH RECURSIVE folder_tree(level, folder_id, parent_id, folders, tags) AS
(
  SELECT 
  	0 as level, folder_id, 0 as parent_id, 
  	cast('' as char(250)) as folders,
  	cast('' as char(250)) as tags
  from 
  	oc_bookmarks_root_folders a
  where (1=1)
  	and a.user_id = 'radek'
  UNION ALL
  SELECT 
  	e.level+1, b.id as folder_id, b.parent_folder as parent_id, 
  	cast(concat(e.folders,b.parent_folder,',') as char(250)) as folders,
  	cast(concat(e.tags,t.tag,',') as char(250)) as tags
  FROM 
  	folder_tree as e 
  	left outer join oc_bookmarks_tree b on e.folder_id = b.parent_folder
  	left outer join oc_bookmarks_tags t ON t.bookmark_id = e.folder_id
  where level < 20
)
SELECT
    a.level, a.folder_id, a.parent_id,
	b.id, 
	b.url, 
	b.title, 
	b.description, 
	b.lastmodified, 
	b.added, 
	b.clickcount, 
	b.last_preview,
	b.available, 
	b.archived_file, 
	b.user_id, 
	b.text_content, 
	b.html_content, 
	a.folders, 
	a.tags
FROM 
	folder_tree a left outer join oc_bookmarks b on a.folder_id = b.id
-- where exists (select 1 from folder_tree t where a.parent_id=t.parent_id and t.level!=a.level)
-- where parent_id=2168
order by level

If I understood your goal correctly, this query should return the same data (first 3 columns are added to better orient in it), and it is significantly ore efective. Even on my very poor data It finishes in approx. 4 sec (which which isn't a moment's of glory but it us acceptable).

[marcelklehr]

Every bookmark MUST HAVE only one (and exactly one) parent.

This is not the case in this project. Bookmarks can be in multiple folders.

select count(*) from oc_bookmarks_tree where id=6286

Note that this will also include tree entries where type is not bookmark.

parent-chield cycle in the tree

That would be bad indeed :/

Something like this

Wow, that's some serious SQL-fu! 👍 I think currently nextcloud supports

MySQL / MariaDB
PostgreSQL
Oracle
SQLite (?)

[ratermir]

Ad "WITH RECURSIVE": It is an ANSI SQL standard, SQLite should support it (I didn't test), Oracle supports this type of query also, but it has (perhaps like almost always :( ) a bit different syntax - they use CONNECT BY PRIOR (already for a quite long time).

Ad Single parent for every child: I created many tree structures in the past and never the child had more parents. If so, it is not a tree structure (but a net). Also in Bookmarks API (if I am correct) every child has only one parent. If the same URL is used on multiple places, it always should have its own "envelop" with unique ID (the parent may be the same or different, but the ID of the bookmark should be unique). This is a general lule how tree structures are built.
But I don't want to teach you - it is only my experience and opinion. If everything works, it doesn't matter how :)

[marcelklehr]

This is a general lule how tree structures are built.

Touché. I'm not infallible :)

parent-chield cycle in the tree

Could you verify whether this is the case in your data? If so, I'll have to write a repair step for this.

WITH RECURSIVE

I'm a bit uncertain about how to tackle this. It seems like a good idea (and I've been looking for a recursive querying technique before), but it seems to be non-trivial to integrate it into the code: https://github.com/nextcloud/bookmarks/blob/master/lib/Db/BookmarkMapper.php#L200 If you'd like to help out with this, that would be great!

[ratermir]

I looked at it, but I don't know PHP almost at all, and also I am not familiar with with Nextcloud development environment and supporting classes.
This functionality would probably must be implemented in implementation of "OCP\DB\QueryBuilder\IQueryBuilder", which I can't find anywhere.

Or the other option would be that the QueryBuilder allowed to put "direct SQL" (which is possible for example in java Hibernate which I worked with), but thewre would be need to write variant for ANSI SQL and for Oracle.

If I found source of QueryBuilder (or any documentation about it) I would look at options. Or someone from here who knows it.

[marcelklehr]

@ratermir Indeed, direct SQL seems to be the only solution as the QueryBuilder does not support Recursive queries, afaik. :/

Could you still verify whether this is the case in your data?