Nested hierarchy using common table expressions

[seanmrich]

I'm trying to generate a hierarchical structure with an indeterminate depth. The schema is a folder table and another table with contents of the folders - let's call it the widget table. The folder table has a belongsTo association to itself with a column named parent. The widget table has a belongsTo association to the folder table. I am ultimately trying to populate the following type:

struct FolderInfo {
  let id: Int64?
  let widgetCount: Int
  let subfolders: [FolderInfo]
  let title: String
}

The request should generate all root folders with their nested subfolders. Since this is a recursive structure, I thought a Common Table Expression would be a good path to getting what I need. I am familiar with the basics of SQL and have spent a bit of time with GRDB, but I'm still getting my head around advanced topics like CTEs. As I'm working through trying to generate SQL that would get me to my goal, I came across this note in the documentation:

Note: common table expressions currently only define "to-one" associations, so the including(all:) joining method is unavailable.

I assumed that somewhere along the way I would have to include a to-many association using including(all:). Does this note mean that I can't achieve my goal using GRDB or am I just misunderstanding?

For what it's worth, I've been trying to build up a SQL statement that handles this case and translate it to GRDB. I realize I'm not that close here, but perhaps it'll illuminate the hole in my understanding?

WITH RECURSIVE subfolders AS (
  SELECT id, parentId, title
  FROM folder
  WHERE deleteDate IS NULL AND parentId IS NULL
      
  UNION ALL
      
  SELECT f.id, f.parentId, f.title
  FROM folder f
  JOIN subfolders sf ON f.parentId = sf.id
  WHERE f.deleteDate IS NULL
)
SELECT sf.id, sf.parentId, sf.title
FROM subfolders sf

If the including(all:) join isn't available, is there a way to do it in SQL?
Apologies if the question is naive, and I appreciate any guidance you can give.

[groue]

Hello @seanmrich,

I'm afraid you'll have to write your own code in order to fetch your tree of FolderInfo structures.

Even though CTEs can express recursion, the GRDB query builder can not. Any given GRDB request executes a fixed number of SQL queries (1 + the number of including(all:) in the request), and can only build that many arrays.

For example, take a request with one including(all:):

let parentInfos = Parent
    .including(all: Parent.children)
    .asRequest(ParentInfo.self)
    .fetchAll()

It mechanically translates into the following code, which involves two SQL queries:

// Fetch parents
let parents = Parent.fetchAll(db)

// Fetch children
let children = Child
    .filter(parents.map(\.id).contains(Column("parentId")))
    .fetchAll(db)

// Merge the two arrays together
let childrenByParentId = Dictionary(grouping: children, by: \.parentId)
let parentInfos = parents.map { parent in
    ParentInfo(
        parent: parent
        children: childrenByParentId[parent.id, default: []])
}

(As you can see, it is not magical at all - GRDB associations are just a convenient way to avoid such boilerplate in applications.)

CTEs do not change this picture. CTE means "Common Table Expressions", where "Table" is a flat array of rows and columns, like all SQL tables. The recursion in the definition of a CTE does not change this: the CTE is still flat. It is not, in essence, different from the "child" table in the above example.

Since the recursion involved in the creation of a CTE is erased as soon as the table nature of the CTE is involved, I'm not sure it is possible for GRDB to provide a general solution.

To sum it up: the recursion must be expressed in Swift, in complement or in replacement or the SQL recursion.

Your way forward is to build the tree recursively out of flat arrays fetched from the database.

[seanmrich]

Thanks for such a thoughtful answer. I was afraid that is the case. I already have a version that does as you describe since that is what I could get my head around. I was concerned that repeat fetches were affecting the performance and hoped for something I could do in one go. Thanks again.

[groue]

Cool, I'm glad you could make it work 👍 Your initial question was quite natural. Maybe some support for tree fetching will ship one day. This will require some new apis (so that recursion can be expressed in Swift).

I would not be too afraid about performances, until some benchmark reveals an actual issue. If this happens, please open a new issue or discussion, and we'll address it specifically.