Grdb.swift: FetchedRecordsController collection view and multiple sections

[simme]

Hey,

So, I've read and understood that the FetchedRecordsController is basically only tested with table views and that there's no current support for multiple sections. And also that the performance might be so-so on bigger data sets.

I'm writing an app that could benefit from all of the above sooner rather than later and was wondering if you put any thoughts into how it could work and how it would be implemented. I _might_ have the possibility of helping out and contributing to something like this — depends a little on how my spare time can be allocated. Not impossible that I could actually get my work to sponsor some time for this too.

I had one thought, that might be helpful or misguided :P What if: instead of fetching full records the initial query only fetches row ids for each record? Could this help with up-front performance? The data source prefetch APIs of UIKit might help with fetching items from the data store. Might make other things like diffing harder though..

CoreData uses a key path to determine the sectioning of items. So I guess one query that groups items on one of the record's properties and then uses that to render the sections could be one solution.

"The problem" with all ideas I can come up with is that it "burdens" the developer with constructing a query that does what the controller expects. But maybe that's not too much to ask? Maybe it could be formalized in some way using the query interface or an initializer that builds the query based on input parameters.

I'm just spewing out ideas. I haven't spent _too_ much time thinking about this or looking at the internals of the current FetchedRecordsController to really come up with anything useful at this point. Which is why I'm asking if you, @groue, have done any thinking already? :)

[groue]

Welcome back, @simme!

So, I've read and understood that the FetchedRecordsController is basically only tested with table views and that there's no current support for multiple sections. And also that the performance might be so-so on bigger data sets.

Yes, this describes pretty well the FetchedRecordsController situation. Collection views are supported, though, because they accept the same diffs as table views.

One of the earliest GRDB observation tool, FetchedRecordsController shows it direct inspiration from Core Data. It hasn't been touched in years. Its inner implementation is not very easy to analyse and change. It looks like it lacks some love.

But it is a great high level tool, because diffing is difficult. It is central in the demo app.

I'm writing an app that could benefit from all of the above sooner rather than later and was wondering if you put any thoughts into how it could work and how it would be implemented. I might have the possibility of helping out and contributing to something like this — depends a little on how my spare time can be allocated. Not impossible that I could actually get my work to sponsor some time for this too.

That's generous of you, and that would be great! All right, let's make sure our energy is well spent :-)

Please give me a little time, I'll come back shortly.

[simme]

Collection views are supported, though, because they accept the same diffs as table views.

What I meant by this is basically that the trackChanges() method doesn't really lend itself that well to updating a collection view because it has the batch API, rather then the begin/end way that table views use.

Please give me a little time, I'll come back shortly.

👍

[groue]

Please excuse me if I write several messages before we really dive in.

Today I start with a list of some interesting FetchedRecordsController features that I find valuable. Not everybody use all of them, but they all fill use cases. And they will remind us what we aim at.

• Core Data inspiration, and imperative style

  I start with the most subjective "feature". GRDB has several APIs that target "traditional" developers, and aim at recycling the skills they have already acquired.

  The Record class is there and ready for developers who are not familiar with Swift protocols, and expect their application models to subclass a root model class. This is what they are used to.

  DatabaseQueue and DatabasePool look a lot like FMDB, because many developers are familiar with this style (and this excellent style could be extended into the robust concurrent SQLite API we currently enjoy).

  And FetchedRecordsController has been designed to look familiar to developers who know Core Data's FetchedResultsController.

  All those "traditional" apis have an imperative style, unlike more "modern" apis that follow a more functional/declarative programming style (like ValueObservation).

  I've been exploring table view diffing based on ValueObservation in https://github.com/groue/GRDBDiff. But this is not conclusive at all. I'm not impressed with the current results, which expose much too much guts into application code, require extra protocol conformances, and remove features, compared to the raw-row-based FetchedRecordsController.

  So far, the very high-level FetchedRecordsController presents the best opportunities for implementation optimizations, and remains the best playground to exercize our diffing skills: I'm convinced you have chosen the best iron to strike.

• Support for all requests, including raw SQL requests

  Steady and obstinate support for raw SQL is a key feature of GRDB, one that makes it a "pro" tool.

  let request: SQLRequest<Player>(sql: "SELECT ...") // Because I feel like it
  let controller = try FetchedRecordsController(dbQueue, request: request)
  

  SQL is also the language used by the Room Android library. Some developer teams are happy sharing requests at the most fundamental layer of their apps: the model layer.

• It is possible to change the tracked request

  A typical use case is search interfaces:

  func updateSearchResults(for searchController: UISearchController) {
      let request = Player.filter(queryString: searchController.searchBar.text)
      try! controller.setRequest(request)
  }
  

  In the demo app, it lets the user change the order of rows:

  @IBAction func sortByName() {
      try! controller.setRequest(Player.orderedByName())
  }
  
  @IBAction func sortByScore() {
      try! controller.setRequest(Player.orderedByScore())
  }
  

• Synchronous reload

  By default, FetchedRecordsController notifies database changes in an asynchronous way. After every impactful commit, the diff is computed in a background dispatch queue, and eventually dispatched on the main queue to the trackChanges closures, so that the table view is updated.

  But some apps need synchronous notifications. For example, an app may need to select a row after an item has been added.

  This use case is provided by the performFetch() methods, which performs an immediate reload, and cancels asynchronous callbacks:

  @IBAction func addPlayer() {
      // Insert
      let player = Player(...)
      try dbQueue.write(player.insert)
  
      // Reload TableView
      try controller.performFetch()
      tableView.reloadData()
  
      // Select and push
      if let indexPath = controller.indexPath(for: player) {
          tableView.selectRow(at: indexPath, ...)
          performSegue(withIdentifier: ...)
      }
  }
  

• Individual row changes

  Another feature directly imported from Core Data. I did not take the time to fully document it in the main README, but it is there, and should stay.

  On record updates and movs, the app is given a dictionary of the changed columns, in the rowChanges variables below:

  controller.trackChanges(
      onChange: { (controller, record, change) in
          switch change {
          case let .update(indexPath, rowChanges): ...
          case let .move(indexPath, newIndexPath, rowChanges): ...
          }
      })
  

  Row changes are a [String: DatabaseValue] which contains the changed columns and their previous values. One use case is optimizing the table view update, for example by avoiding redrawing a cell when the displayed values have not changed.

[groue]

What I meant by this is basically that the trackChanges() method doesn't really lend itself that well to updating a collection view because it has the batch API, rather then the begin/end way that table views use.

All right, we'll handle this.

[simme]

What follows is basically me agreeing a bunch:

Please excuse me if I write several messages before we really dive in.

That's to be expected! :D It's important that we identify all of the things that needs to be there.

• Core Data inspiration, and imperative style
  And FetchedRecordsController has been designed to look familiar to developers who know Core Data's FetchedResultsController.

I agree that this is valuable.

I've been exploring table view diffing based on ValueObservation in https://github.com/groue/GRDBDiff. But this is not conclusive at all. I'm not impressed with the current results, which expose much too much guts into application code, require extra protocol conformances, and _remove_ features, compared to the raw-row-based FetchedRecordsController.

Interesting. I'll take a look when I get the chance. Maybe it'd be possible to make the diffing algorithm "pluggable". A base implementation that is good enough for typical sized data sets could be included. But for specialized cases it might be useful to be able to provide a custom diffing algorithm. This could also simplify testing. Maybe this is already possible today?

• Support for all requests, including raw SQL requests
  Steady and obstinate support for raw SQL is a key feature of GRDB, one that makes it a "pro" tool.
  Some developer teams are happy sharing requests at the most fundamental layer of their apps: the model layer.

Agreed. This is what makes it possible to do highly performant and customized queries for each specific use case.

• It is possible to change the tracked request

Yup.

• Synchronous reload
  By default, FetchedRecordsController notifies database changes in an asynchronous way. After every impactful commit, the diff is computed in a background dispatch queue, and eventually dispatched on the main queue to the trackChanges closures, so that the table view is updated.

Ah, nice. I didn't know this. So is this what the initializer provided queue is for?

But some apps need synchronous notifications. For example, an app may need to select a row after an item has been added.

This use case is provided by the performFetch() methods, which performs an immediate reload, and cancels asynchronous callbacks.

Right. That makes sense. Would it be possible to load all of the raw row data for a request without instantiating the records themselves? To avoid doing all of the heavy lifting upfront.

Is diffing today done on the raw rows or on the record instances?

• Individual row changes
  Another feature directly imported from Core Data. I did not take the time to fully document it in the main README, but it is there, and should stay.
  On record updates and movs, the app is given a dictionary of the changed columns, in the rowChanges variables below:

  controller.trackChanges(
    onChange: { (controller, record, change) in
        switch change {
        case let .update(indexPath, rowChanges): ...
        case let .move(indexPath, newIndexPath, rowChanges): ...
        }
    })
  

  Row changes are a [String: DatabaseValue] which contains the changed columns and their previous values. One use case is optimizing the table view update, for example by avoiding redrawing a cell when the displayed values have not changed.

That's a neat feature that should be supported for sure.

---

I've imagined the sectioning to be done on a record property. But maybe it makes more sense to provide a database column that should be used to group items into sections? Or support both?

Section computation

The pragmatic and straight forward approach is probably to fetch all rows in the performFetch() method and then loop through the result and create the sections up front. But it might be interesting to provide an API for more specialized use cases where the records controller could ask a delegate for queries to calculate section counts etc to avoid having to load all data at once. But maybe this is complicating things too much?

[simme]

Do you think extending and refactoring the current implementation will be sufficient or do you think a rewrite is required?

Also, I'm sorry if I'm posing dumb questions. Haven't dove in to the GRDB internals enough to know exactly how everything works yet :)

[groue]

Hi @simme,

Sorry for this late response!

Do you think extending and refactoring the current implementation will be sufficient or do you think a rewrite is required?

I admit I dread the current implementation. I guess you have looked at it, and was confused. I sure am, too. I wouldn't mind a rewrite.

OK, let's give some practical advice.

Basically, here is the general process:

1. User submits a request to observe. Let's say Player.orderByPrimaryKey() or SELECT * FROM player ORDER BY id.

   In order to accept all those kinds of requests, you may need to get familiar with the Custom requests chapter, and particularly the FetchRequest protocol, and the AnyFetchRequest type.

2. We observe changes in this request, and fetch raw database rows whenever it is modified.

   For observation itself, please check the full ValueObservation doc, because I think we'll need it all. You don't have to worry about GRDB internals, because FetchedRecordsController was fully built from public APIs, and we'll do the same. We already have all the necessary tools. I admit they are not used every day, and we enter rather "advanced" GRDB :-)

3. We apply a diff algorithm between the previously fetched rows, and the new rows.

   There are many, many, diff algorithms. FetchedRecordsController currently uses one which has a terribly high quadratic complexity. We need an algorithm with a much lower complexity. I don't know which one. I have compiled a list over time:

   • https://github.com/RxSwiftCommunity/RxDataSources (check this one closely)
   • https://github.com/jflinter/Dwifft
   • https://github.com/wokalski/Diff.swift
   • https://github.com/andre-alves/PHDiff
   • Surely others

   Don't expect the algorithm to be 100% ready-made. We target table and collection views, which support four basic operations: insertion, deletion, update, and update+move (in the last one, a cell changes both content, and position). We want a high quality diff output that is able to perform all of those operations

4. We nicely pack the output of the diff algorithm for the user so that he can update his table/collection view. And yeah, it's done :-D

To start, there are three topics I suggest we become reasonably confident with:

1. Get familiar with what a GRDB request is.
2. Find a suitable diffing algorithm.
3. Decide what is a section, and find an API that lets the user describe how rows should be grouped in section.

Fortunately, they are all independent, and can be achieved in any order 😉

[groue]

Also, I'm sorry if I'm posing dumb questions

Please don't be. Adding sections to FetchedRecordsController is not an easy task. Keep on asking questions, as soon as something is not clear to you!

[groue]

I'm afraid I'm overwhelming you with too much information. You know, you can jump in straight ahead and run this code in some app:

// A record type
struct Player: Codable, FetchableRecord, PersistableRecord {
    var id: Int64
    var name: String
    var score: Int
}

// Database setup
let dbQueue = DatabaseQueue()
try dbQueue.inDatabase { db in
    try db.create(table: "player") { t in
        t.column("id", .integer).primaryKey()
        t.column("name", .text)
        t.column("score", .text)
    }

    try Player(id: 1, name: "Arthur", score: 100).insert(db)
    try Player(id: 2, name: "Barbara", score: 110).insert(db)
}

struct Diff { /* TODO */ }

// The observed request
let request = Player.all()

// The observation
let observation = ValueObservation.tracking(request, reducer: { (db: Database) -> AnyValueReducer<[Row], Diff> in
    // Used for comparison
    var oldRows: [Row] = []

    // The reducer is invoked each time the observed request is changed:
    return AnyValueReducer(
        fetch: { (db: Database) -> [Row] in
            // Fetch fresh rows (in a dispatch queue able to access the database)
            try Row.fetchAll(db, request)
        },
        value: { (newRows: [Row]) -> Diff in
            defer {
                // Ready for next change
                oldRows = newRows
            }
            // Compute diff (in a background dispatch queue)
            print("Old rows: \(oldRows)")
            print("New rows: \(newRows)")
            return Diff() /* TODO */
    })
})

// Start
print("Start observation")
let observer = try observation.start(in: dbQueue, onChange: { (diff: Diff) in
    // Handle diff (on the main queue)
    print("Diff computed")
})

// Modify the database
print("Insert row")
try dbQueue.write { db in
    try Player(id: 3, name: "Craig", score: 50).insert(db)
}

print("Delete rows")
try dbQueue.write { db in
    try Player.deleteAll(db)
}

It prints:

Start observation
Old rows: []
New rows: [[id:1 name:"Arthur" score:"100"], [id:2 name:"Barbara" score:"110"]]
Diff computed

Insert row
Old rows: [[id:1 name:"Arthur" score:"100"], [id:2 name:"Barbara" score:"110"]]
New rows: [[id:1 name:"Arthur" score:"100"], [id:2 name:"Barbara" score:"110"], [id:3 name:"Craig" score:"50"]]
Diff computed

Delete rows
Old rows: [[id:1 name:"Arthur" score:"100"], [id:2 name:"Barbara" score:"110"], [id:3 name:"Craig" score:"50"]]
New rows: []
Diff computed

The actual printing order may be different because observations compute their values asynchronously.

[simme]

I'm afraid I'm overwhelming you with too much information.

No worries. The beauty of text communication is that one can read a sentence many times ;)

Regarding the diffing algorithms, I assume we don't necessarily want to impose another dependency on the user? So embedding the code within GRDB is preferred?

[groue]

Yes, embedding the diff algorithm is OK.

[simme]

So a ValueObservation doesn't actually give me any information about what changed? Only the "current state" of the watched request?

[groue]

So a ValueObservation doesn't actually give me any information about what changed? Only the "current state" of the watched request?

Yes. A ValueObservation provides four services:

1. Tell that the tracked requests have been impacted by a transaction.
2. Give an opportunity to fetch values from the database before any other transaction has further modified the database (guarantee that no transaction is missed)
3. Give an opportunity to process the database values, by ignoring them, or by turning them into notified values (in a dispatch queue that does not block the database, or the main queue)
4. Schedule the notified values so that they are all dispatched on the desired queue (the main queue, by default).

Let's now look at a particular observation:

let observation = ValueObservation.trackingOne(Player.filter(42))
let observer = try observation.start(in: dbQueue) { (player: Player?) in
    print("Fresh player: \(player?.name ?? "deleted")")
}

Each time player 42 is modified (1), it (2) fetches a raw row. Then (3), if this row is different from the previously fetched row, it turns this row into a Player. And this player is printed on the main queue (4).

Eventually, we are notified of all changes to Player 42. But we do not know what has changed in the player. Because this is not what this observation does

But what a ValueObservation does can be configured.

The steps 1 and 4 are performed by the ValueObservation itself. The steps 2 and 3 are performed by the observation's "reducer". The reducer "reduces" fetched values into notified values:

protocol ValueReducer {
    associatedtype Fetched
    associatedtype Value

    /// Fetches a database value
    func fetch(_ db: Database) throws -> Fetched

    /// Returns a notified value, if any
    mutating func value(_ fetched: Fetched) -> Value?
}

In ValueObservation.trackingOne(Player.filter(42)), the type of the reducer is FetchableRecordReducer.

In the diffing sample code in the previous comment, I used an AnyValueReducer. You have already met this "Any" prefix in Swift, with AnySequence, for example. One advantage of those "Any" types is that you can build a value that conforms to a protocol without defining a full type beforehand. It has helped me keeping the sample code terse.

Let's rewrite the sample code, but display where the four observation steps are performed:

// Build an observation which tracks all players (step 1)
let request = Player.all()
let observation = ValueObservation.tracking(request, reducer: { (db: Database) -> AnyValueReducer<[Row], Diff> in

    // Return a reducer responsible for steps 2 and 3
    var oldRows: [Row] = []
    return AnyValueReducer(
        fetch: { (db: Database) -> [Row] in
            // Step 2
            try Row.fetchAll(db, request)
        },
        value: { (newRows: [Row]) -> Diff in
            // Step 3
            defer {
                oldRows = newRows
            }
            print("Old rows: \(oldRows)")
            print("New rows: \(newRows)")
            return Diff() /* TODO */
    })
})

// Start
print("Start observation")
let observer = try observation.start(in: dbQueue, onChange: { (diff: Diff) in
    // Step 4
    print("Diff computed")
})

[groue]

I suggest we use ValueObservation because it encapsulates a difficult job which is the scheduling of the various steps 1, 2, 3 and 4. One of the reasons why FetchedRecordsController is not easy to read is that it has to do this job by itself. ValueObservation did not exist at the time FetchedRecordsController was written.

A few years later, I have learned that the four steps 1, 2, 3, 4 are a good general observation pattern. They are gathered in ValueObservation. It is our friend, even if we have to deal with this advanced "reducer" concept. It may look abstract and intimidating, but we are granted with an API that efficiently uses the database.

We don't have to worry performing heavy computations that could block the main queue, because ValueObservation makes sure all steps are performed in dedicated dispatch queues. And when the user uses a DatabasePool instead of a DatabaseQueue, ValueObservation takes care of maximizing the benefits of multi-threaded database access.

With ValueObservation, you can focus on your data and how you want to transform it. All the heavy plumbing is already done for you.

[simme]

Haha. If I keep asking question you'll just have this thing written yourself ;)

Thank you for the thorough answers. I'll be doing some work on this today. Starting out by doing a basic implementation that covers the needs in my app, and then when I have that working I can start refactoring to generalize it.

[groue]

That's an excellent technique :-)

[simme]

It fast became very obvious that the tricky part of this is going to be the diffing/sectioning code, not anything actually related to the database. Haha.

From my fairly brief research I can't seem to find a Swift implementation of a diffing algorithm that has all of the granularity that we need (insert/delete vs change). And to also get that for a nested list seems even harder.

I'm thinking that perhaps it would be possible to run a diff algorithm to find inserts and deletes on the list of un-sectioned rows first. _Then_ section and then map the diff upon that sectioned list. And similarly detect updates as a separate step.. There's no way around the fact that this operation will eat a couple of CPU cycles. Hopefully with "normal" datasets and the new modern iOS CPUs it shouldn't be that big of a deal.

I've also thought about how to actually section the rows. My current thinking was to let the user provide a column name to use for sectioning. And then do something like this (psuedo code):

for row in rows {
  // Grabs the last added section unless the value of `row[sectionColumn]` is different than the last.
  var section = self.section(for: row[sectionColumn])
  section.append(row: row)
}

Ie. basically loop through each row and put them in a section. This would however require the user to provide a query that correctly groups rows in a section. But I don't think that's a problem. Do you? Otherwise diffing would also require sorting first.

[groue]

It fast became very obvious that the tricky part of this is going to be the diffing/sectioning code, not anything actually related to the database. Haha.

Good, this sounds like a good news to me :-)

From my fairly brief research I can't seem to find a Swift implementation of a diffing algorithm that has all of the granularity that we need (insert/delete vs change). And to also get that for a nested list seems even harder.

I'm not surprised this research phase is not very easy. I suggest you do focus on https://github.com/RxSwiftCommunity/RxDataSources, because I think it does most of what we need. Maybe not everything, but a fairly great deal of it. Take care of checking the license, I'll do it too.

I'm thinking that perhaps it would be possible to run a diff algorithm to find inserts and deletes on the list of un-sectioned rows first. Then section and then map the diff upon that sectioned list. And similarly detect updates as a separate step.

You'll get more confident about the way to do it as you discover the area and find inspiration. I can't really provide any guidance, here.

There's no way around the fact that this operation will eat a couple of CPU cycles. Hopefully with "normal" datasets and the new modern iOS CPUs it shouldn't be that big of a deal.

FetchedRecordsController becomes completely unusable after a few hundreds items. That will be our test for the new algorithm. This topic is the topic of complexity.

FetchedRecordsController uses a quadratic algorithm: when you double the number of elements, the algorithm becomes four times as slow (2->4, 3->9, 4->16, etc). This is terrible. On the other side, RxDataSources claims to be linear, which is a nice low complexity.

Thanks to ValueObservation, those CPU cycles will run in the "reducing" phase (step 3), which won't block the main queue or the database.

We'll have Instrument as a way to check the bottlenecks.

And we have the Demo Application which is a great test bed.

I've also thought about how to actually section the rows. My current thinking was to let the user provide a column name to use for sectioning.

A column name an excellent starting point. We may have to rediscuss this later, when we'll actually wonder how people may use the feature, and try to accommodate reasonable use cases. But I'm really OK with a single sectioning column right now.

This would however require the user to provide a query that correctly groups rows in a section. But I don't think that's a problem. Do you? Otherwise diffing would also require sorting first.

This is not a problem: it is natural that users provide a request that has the same ordering as the one used in the view: Player.order(Column("team"), Column("score").desc) can feed a table/collection view whose sections are team names, sorted by team name, and then by score.

[simme]

Seems like this could potentially be worth waiting for...

https://github.com/apple/swift-evolution/blob/master/proposals/0240-ordered-collection-diffing.md

[groue]

We'd still have to handle sections. But I'm sure SE-0240 is an interesting read as well!

[groue]

No issue remains open here unless it's a bug that needs fixing, or someone is actually busy making some progress on the topic. So I'm closing this one. Feel free to reopen it when you feel like it, @simme!

[simme]

I still have this issue to reference whenever I make (slow) progress on an implementation. Thank you for the feedback and idea bouncing. I will need this for my project sooner or later, my planning didn't pan out this particular time though.

[gennaios]

Hello. Interesting discussion. I was thinking about sections. Currently I agree it is perhaps best to define it from one column but with the addition of a query. Or maybe just merely a query as well as perhaps a way to tag or name the section such that one could access it by key.

I think common section use cases might be column values such as date range, e.g. day, month, year, etc., some set of values in a colimn such as city, state, country, or what is very common such as what you see in default apps like Music, grouping alphabetically by first letter. Perhaps there are other use cases and for more flexibility, a query that defines a section may provide the most liberty allowing the developer to choose.