3

In sqlite, minimal schema is as follows:

CREATE TABLE IF NOT EXISTS "images" (
  `id` integer not null primary key autoincrement
);

CREATE TABLE `folders` (
  `id` integer not null primary key autoincrement,
  `path` varchar(255) NOT NULL
);

CREATE UNIQUE INDEX `index_folders_on_path_unique` on `folders` (`path`);

CREATE TABLE `files` (
  `id` integer not null primary key autoincrement,
  `basename` varchar(255) NOT NULL,
  `parent_folder_id` integer not null,
  foreign key(`parent_folder_id`) references `folders`(`id`)
);

CREATE UNIQUE INDEX `index_files_on_parent_folder_id_basename_unique` on `files` (`parent_folder_id`, `basename`);
CREATE INDEX `index_files_on_basename` on `files` (`basename`);

CREATE TABLE `images_files` (
  `image_id` integer NOT NULL,
  `file_id` integer NOT NULL,
  `primary` boolean NOT NULL,
  foreign key(`image_id`) references `images`(`id`) on delete CASCADE,
  foreign key(`file_id`) references `files`(`id`) on delete CASCADE,
  PRIMARY KEY(`image_id`, `file_id`)
);

Edit: I omitted what I think to be a necessary index, which I have since added:

CREATE INDEX `index_images_files_on_file_id` on `images_files` (`file_id`);

Also changed index_files_on_parent_folder_id_basename to be a unique index.

Executing an EXPLAIN QUERY PLAN for the following query:

SELECT DISTINCT `images`.`id`
  FROM `images`
  LEFT JOIN `images_files` ON (`images`.`id` = `images_files`.`image_id`) 
  LEFT JOIN `files` ON (`images_files`.`file_id` = `files`.`id`) 
  ORDER BY `files`.basename ASC LIMIT 40 OFFSET 0;

I'd expect the index_files_on_basename index to be used. However, the explain plan is output as follows:

QUERY PLAN
|--SCAN TABLE images
|--SEARCH TABLE images_files USING COVERING INDEX sqlite_autoindex_images_files_1 
(image_id=?)
|--SEARCH TABLE files USING INTEGER PRIMARY KEY (rowid=?)
`--USE TEMP B-TREE FOR ORDER BY

The images table is potentially large (I'm using 4M rows in my test database) and this query can take a very long time to return. Please note also that there may be where filtering depending on user query inputs.

My end goal is to order by folder path then basename, but I can't even optimise the basename scenario. Why isn't the path indexed used to order these results? How can I improve performance when ordering on these joined tables?

Edit: this is the query for sorting by folder path then basename:

SELECT `images`.`id`
  FROM `images`
  LEFT JOIN `images_files` ON (`images`.`id` = `images_files`.`image_id`) 
  LEFT JOIN `files` ON (`images_files`.`file_id` = `files`.`id`) 
  LEFT JOIN `folders` ON (`files`.`parent_folder_id` = `folders`.`id`)
  ORDER BY `folders`.path, `files`.basename ASC LIMIT 40 OFFSET 0;

This results in the following query plan:

QUERY PLAN
|--SCAN TABLE images
|--SEARCH TABLE images_files USING COVERING INDEX sqlite_autoindex_images_files_1 (image_id=?)
|--SEARCH TABLE files USING INTEGER PRIMARY KEY (rowid=?)
|--SEARCH TABLE folders USING INTEGER PRIMARY KEY (rowid=?)
`--USE TEMP B-TREE FOR ORDER BY

Other query plans:

EXPLAIN QUERY PLAN SELECT `files`.`id`
  FROM `files`
  LEFT JOIN `folders` ON (`files`.`parent_folder_id` = `folders`.`id`)
  ORDER BY `folders`.path, `files`.basename ASC LIMIT 40 OFFSET 0;

QUERY PLAN
|--SCAN TABLE files
|--SEARCH TABLE folders USING INTEGER PRIMARY KEY (rowid=?)
`--USE TEMP B-TREE FOR ORDER BY

Changing this to INNER JOIN gives the following query plan:

QUERY PLAN
|--SCAN TABLE folders USING COVERING INDEX index_folders_on_path_unique
`--SEARCH TABLE files USING COVERING INDEX index_files_on_parent_folder_id_basename (parent_folder_id=?)

This query plan looks similar to what I would expect from the original query - using the covering index to perform the sorting.

I tried eliminating images from the query altogether (not really feasible for my use case):

EXPLAIN QUERY PLAN SELECT `images_files`.`image_id`
  FROM `images_files`
  INNER JOIN `files` ON (`images_files`.`file_id` = `files`.`id`) 
  INNER JOIN `folders` ON (`files`.`parent_folder_id` = `folders`.`id`)
  ORDER BY `folders`.path, `files`.basename ASC LIMIT 40 OFFSET 0;

QUERY PLAN
|--SCAN TABLE images_files USING COVERING INDEX sqlite_autoindex_images_files_1
|--SEARCH TABLE files USING INTEGER PRIMARY KEY (rowid=?)
|--SEARCH TABLE folders USING INTEGER PRIMARY KEY (rowid=?)
`--USE TEMP B-TREE FOR ORDER BY

Things I've tried:

  • changing the left joins to inner joins and removing the DISTINCT. This isn't really feasible for my use case, as there may be rows in the images table without a corresponding file. In any case, it doesn't change the query plan. Edit: it adds USING COVERING INDEX sqlite_autoindex_images_files_1 to the scan table clause, but does not appear to improve performance.
  • joining on a ordered subquery: LEFT JOIN (SELECT * from `files` ORDER BY `files`.basename ASC) as `files` ON (`images_files`.`file_id` = `files`.`id`). No difference.

Edit: As mentioned at the top, I had omitted an index on images_files which I thought would prevent ordering the files table first and searching images_files, but it does not seem to have had any impact on the query plans.

2
  • The optimizer thinks it's more efficient to use the primary key index than your index on basename. What happens when you ORDER BY "folder path then basename" as you stated? This would definitely be a different query, so you may find it worth testing exactly what you want, not something you don't want.
    – J.D.
    Jul 26, 2022 at 12:36
  • 1
    @J.D. I've added some extra queries and information. I was trying to keep the question as simple as possible.
    – tvStatic
    Jul 27, 2022 at 0:14

1 Answer 1

0

It should be noted that Sqlite stores table data in a b-tree structure which is orderer by ROWID. Thus, accessing a row by rowid is really fast. If a table has a column defined as INTEGER PRIMARY KEY, then that column is used as a substitude for ROWID, so that table is stored ordered by that column and there is no need to build an index on that column. In your example, "images", "folders" and "files" all have an "id" column which is an integer primary key, so an index on that column is never created because is not necessary (the table itself is the index).

Now, the query plan proposed by sqlite seem to me the best possible, because:

  1. "images" is the master table of the LEFT join, so every row of it must be read regardless of the number of joined rows in the other tables. Since there is no "id" index on "images", even if the only column needed is "id", sqlite must read the table (which will be read in id order, since that is the rowid of the table)
  2. "image_files" is than searched for every "id". Since we only need to retrieve file_id, sqlite reads only the index, which contains both image_id and file_id, without accessing the "image_files" table (the index is marked as COVERING).
  3. for each file_id found, we need to retrieve the basename from files. Since file_id is the rowid primary key, we can get to the corresponding row directly without using any index. "SEARCH TABLE files USING INTEGER PRIMARY KEY (rowid=?)" actually means that a binary search is used, the table is not scanned.
  4. Now that we have all basenames, we can sort them and take the first 40

The index_files_on_basename can not be used because you don't want the first 40 basenames, you want the first 40 images.id that, due to the LEFT JOIN clause, could be all linked with no files, so sqlite cannot select the top 40 rows until the join is executed.

So, what can you do to speed up your query?

Step 1: Leverage your knowledge that you will need AT MOST 40 basenames to pre-filter your files table with a subquery that will select only the first 40 basenames, then run the main query against this subset instead of the full files table.

SELECT DISTINCT `images`.`id` FROM `images`
LEFT JOIN `images_files` ON (`images`.`id` = `images_files`.`image_id`) 
LEFT JOIN (SELECT id, basename FROM `files` ORDER BY `files`.basename ASC LIMIT 40 OFFSET 0) AS f ON (`images_files`.`file_id` = `f`.`id`) 
ORDER BY `f`.basename ASC LIMIT 40 OFFSET 0;

This will speed up the lookup of the basenames, but sqlite still needs to do a full table scan of 'images' due to the LEFT join.

Step 2: Substitute the LEFT join with an INNER join You can use an INNER join to get the rows for images associated with files and then use UNION to add those images without a file:

SELECT DISTINCT `images`.`id`, f.basename
FROM `images`
JOIN `images_files` ON (`images`.`id` = `images_files`.`image_id`) 
JOIN (select id, basename from `files` ORDER BY `files`.basename ASC LIMIT 40 OFFSET 0) as f ON (`images_files`.`file_id` = `f`.`id`) 
UNION
SELECT DISTINCT `images`.`id`, NULL as basename
FROM `images`
LEFT JOIN `images_files` ON (`images`.`id` = `images_files`.`image_id`) 
WHERE `images_files`.`image_id` is NULL 
ORDER BY `f`.basename ASC LIMIT 40 OFFSET 0;

Please note that the subquery after the UNION still needs a full scan of table 'images'.

Step 3: Rewrite your tables. I assume that an image can have more than one associated files (otherwise you wouldn't need a separate 'image_files' table). However, is it possible for you to populate image_files even for images that have no files? image_files.files_id would be NULL in such cases (you have to remove the NOT NULL constraint), but this way you would have at least one row in image_files for each image and you could user an INNER join instead of a LEFT one and searching for images without files would just be an index search in image_files primary key index.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.