1921394 - Database structure for folder hierarchy

Status: ASSIGNED

(MailNews Core :: Database, task)

Description

[Geoff Lankow (:darktrojan)]

In this bug I'll be posting my patches relating to storing folders in the global database. At this point it's experimental, does nothing with actual mail folders, and isn't connected to anything. Nothing about this is finalised, especially the names of various things, but we are pretty happy with the structure so far.

Comment 1

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Implement the core of the new database for folders. r=BenC!,#thunderbird-reviewers

Comment 2

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Implement moving existing folders around. r=BenC!,#thunderbird-reviewers

Comment 3

[Ben Campbell]

I've been thinking about this a bit, and here are some more thoughts:

• Folders are mostly reflection of structure on a remote server or (in the case of local folders) the filesystem.
• We need the concept of folders in a global database so we can associate messages with them (messages are inside one or more folders).
• We get folder names and hierarchy from the server (or filesystem). But network traffic is slooooooow, so it makes sense to cache names/hierarchy locally once we have them.
• The server always holds the Authoritative Truth (tm).
• We have local, not-on-the-server data associated with folders too, eg ordering, view settings, localised names for special folders etc.
• In the current database-per-folder system, there is a folderInfo struct which holds such stuff (although I don't think that captures hierarchy - I think the code uses the filesystem structure for hierarchy, updated with info from server when available).
• For folders, we are synchronising three things: the server state, the in-memory state and the database state. Keeping the latter two in step isn't so bad as long as you're ruthless in guarding access to the mechanisms of change. It'll suck if you can update one representation without updating the other :-)

I would be trying to think of terms of the folders in the database being cached representations of server-side objects, plus some extra non-server app-side data stuck onto them (and presumably add-ons would like the ability to slap extra custom data onto folders too).

So to me, the interesting kinds of questions are:

• how do we discover folders (from remote servers and local folder filesystem)
• how do we deal with server-side folder changes? eg think of a yahoo IMAP account where the user renames a folder through the webmail interface while not using TB. What happens the next time TB runs?
  • I don't think a client can catch this with vanilla IMAP... It'll just be one folder disappearing (deleted!) a new one showing up, containing messages to (re)download.
  • I'm pretty sure ews and jmap would have some kind of immutable server-assigned id for folders so they can be moved around and reparented without fuss. So we should support that.
  • I'd bet there are IMAP extensions which support that too (objectID?).
• How do we resolve local "speculative" operations with eventual server success/failure - eg a user reparents a folder locally:
  • we want to update our local representation immediately (we're a native app - everything should be instant, dammit!)
  • we kick off a network operation to do the same thing on the server
  • if the server succeeds, great, all done here.
  • if the server operation fails... then we need to roll things back and make sure our local folder data (and the messages therein) are still in sync with the "true" state on the server.
  • There's the ugly case where we don't know if it succeeded or failed! Start operation, network goes down... what to do in such cases? (we need general sync-with-server code to sort it out - such a sync mechanism should probably also be used by the initial connection to the server) What does the IMAP code handle this? No idea - I'm sure it mostly all just works, but I bet there's lots of duplication and ugly corner cases in there, with lots of potential to go horribly wrong. It'd be nice to think about this in a more protocol-neutral way.

Comment 4

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Implement functions for flag handling. r=BenC!,#thunderbird-reviewers

Comment 5

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Add functions and guards for working with multiple roots. r=BenC!,#thunderbird-reviewers

Each server will be represented as a separate root in the folders table.

Comment 6

[Toby Pilling [:tobyp]]

I'm still very nervous about the use of the nested set model when we have recursion at our disposal. Please read up on the risks of the large updates necessary when new folders are created on accounts with many folders. The overhead and risk involved in so many write operations just doesn't seem to be worth it when read performance is the same when using recursive CTEs.

https://lars.yencken.org/hierarchy-in-sql
https://en.wikipedia.org/wiki/Nested_set_model#Performance

Comment 7

[Geoff Lankow (:darktrojan)]

I'm not concerned about the performance. This table will have a small number of rows in it – probably less than 10,000 in the worst cases (we know some users have 100 accounts, but have they got 100 folders in each?) and less than 100 for the vast majority of users. Even if there were 10,000 rows, SQLite can update that many in milliseconds.

As the quote in that Wiki article says, "It’s best used when you need to query a tree more frequently than you need to modify the tree." which is what we'll be doing.

That said, most of what I'm working on at the moment doesn't depend on which database model we use. We'd still want all of the functionality I'm building out around the database, and all of the test cases are still valid. We could change out the database model without a lot of work.

Comment 8

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Sort folders as they are read in from the database. r=BenC!,#thunderbird-reviewers

A folder in the database can either have an ordinal value or null. Folders with ordinals are sorted
first, in ascending order, then folders without ordinals in alphabetical order. The order of those
with null will be further refined in a later patch, as it needs to account for non-ASCII characters
and the ordering of special folder types.

Comment 9

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Implement folder lookup by path. r=BenC!,#thunderbird-reviewers

Comment 10

[Geoff Lankow (:darktrojan)]

I did end up moving away from the nested set model, but not for performance reasons. I realised that to have a folder's children be manually ordered (we store the order as specified by the user), automatically ordered (based on the folder type and name), or some combination of both. In the nested set model the children have to be stored in some order and that just made it too complicated. I'd rather store no order where necessary and deal with it as the database is read.

Comment 11

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/comm-central/rev/f89f51302a93
Implement the core of the new database for folders. r=BenC,aleca
https://hg.mozilla.org/comm-central/rev/11e7ffe6e93e
Sort folders as they are read in from the database. r=BenC,aleca
https://hg.mozilla.org/comm-central/rev/1005945049c0
Implement moving existing folders around. r=BenC,aleca
https://hg.mozilla.org/comm-central/rev/7e9b1129eb86
Implement functions for flag handling. r=BenC,aleca
https://hg.mozilla.org/comm-central/rev/b517801bcbae
Add functions and guards for working with multiple roots. r=BenC,aleca
https://hg.mozilla.org/comm-central/rev/e1a1ba99d17c
Implement folder lookup by path. r=BenC,aleca

Comment 12

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Make C++ shortcuts to infallible Folder properties. r=BenC!,#thunderbird-reviewers

PIDL will do most of the work for us, but not the string properties.

Comment 13

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Load folders from the database off the main thread. r=BenC!,#thunderbird-reviewers

This does the database read off the main thread. Subsequent patches will add the initial reconciliation of on-disk folders to the task thread.

Comment 14

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/comm-central/rev/46abd41e1cc1
Make C++ shortcuts to infallible Folder properties. r=BenC
https://hg.mozilla.org/comm-central/rev/31f948947954
Load folders from the database off the main thread. r=BenC, mkmelin

Comment 15

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Create panorama.sqlite if it doesn't exist when FolderDatabase starts. r=BenC!,#thunderbird-reviewers

All of this start-up code is probably going to get moved out of here eventually, but for now we need it.

Also featuring logging and comments.

Comment 16

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Add functions for inserting and deleting folders. r=BenC!,#thunderbird-reviewers

Comment 17

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Initialise folder database entries from the filesystem at start-up. r=BenC!,#thunderbird-reviewers

Comment 18

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Clean up leaked objects in FolderDatabase. r=#thunderbird-back-end-reviewers

Comment 19

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Fix a mistake in a test. r=#thunderbird-back-end-reviewers

These lines accidentally passed because null == undefined. I didn't realise I'd given the folders the wrong parent when rearranging the database.

Comment 20

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/comm-central/rev/eb3fa51e18d2
Clean up leaked objects in FolderDatabase. r=mkmelin
https://hg.mozilla.org/comm-central/rev/38219568f4e4
Fix a mistake in a test. r=mkmelin

Comment 21

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Move the common database functions into their own class. r=#thunderbird-back-end-reviewers

We're going to want to use these functions for multiple tables soon, so I've dragged the common
stuff out into a separate class that can be shared. This class will be the only entry point to gain
access to database-handling classes (e.g. via DatabaseCore::GetFolders), which means we can be sure
there's only one of each of them.

Comment 22

[Geoff Lankow (:darktrojan)]

Attachment: Bug 1921394 - Handle non-ASCII characters when sorting folders and comparing paths. r=#thunderbird-back-end-reviewers

• Strings should be normalised to Unicode canonical composition form before being inserted into the database.
  This will prevent mistakes when comparing strings containing non-ASCII characters.
• Folders (that have no explicit ordering) should be ordered in a case-sensitive and locale-aware way.