Efficient Container Hierarchy Traversal

[ormsbee]

(I'm creating this ticket from the initial discussion that happened in a PR, along with a couple of minor thoughts I've had since then.)

Requirements

We need to quickly and efficiently do hierarchy traversals for things like outline display. This is a very common need in courses.

• The solution must provide fast reads for all descendants of a node or all ancestors of a node.
• The solution must be performant for these reads, even when there are 10K nodes (maybe 20 ms?)
• Write speed is less critical. We should still be able to update a course with 10K nodes in time for a synchronous request.

High level considerations

1. It makes sense to add this in Learning Core itself, since it's of great interest to plugin writers and it can operate on containers directly.
2. The APIs should be more QuerySet/model based, i.e. there's something like a ContainerPath model that can be returned, so that other APIs can extend that queryset to add more select_related calls to it.
3. It's okay to assume that a certain type of thing is always at a particular level of the hierarchy, e.g. a Component is always at the bottom layer, and a Unit is always one layer above that.
4. We should not assume that a given layer always maps to a particular container type. A plugin may one day implement a custom container type that holds Components but is not a Unit. This should still work. We will likely also introduce Files and Uploads as a type that sits at the bottom layer.
5. We can probably get away with only tracking the expanded form for the current Draft and Published versions.

Modeling

A containers app (or publishing for now) might have a model like:

class PublishedContainerPath(models.Model):
    # level_0 is the lowest/leaf layer, e.g. the Component.
    # This is a DAG, so we can have many duplicates of level_0_entity, and the
    # only UNIQUE restriction would be on the entire row, i.e. exact duplicates
    # of everything would be a race condition. Even having the same entity at
    # multiple versions might be allowable for pinned child references in the
    # future.
    #
    # It feels unintuitive to model the hierarchy from bottom-up like this, but
    # as Braden pointed out, this would let us avoid the issue of having Units
    # show up in multiple columns, since a Unit would always be at level_1 in
    # this type of model.
    level_0_entity = models.ForeignKey(models.PublishableEntity)
    level_0_version = models.ForeignKey(models.PublishableEntityVersion, null=True)
    level_0_order = models.PositiveSmallInteger(null=True)  # or PositiveInteger?

    # Continue this pattern for at least Component -> Unit -> Subsection ->
    # Section -> OutlineRoot (0-4), but probably at least to 6 to give a little
    # headroom?
    level_1_entity = models.ForeignKey(models.PublishableEntity)
    level_1_version = models.ForeignKey(models.PublishableEntityVersion, null=True)
    level_1_order = models.PositiveSmallInteger(null=True)

    # highest level doesn't have an ordering (because it's never a peer child
    # of anything)
    level_6_entity = models.ForeignKey(models.PublishableEntity)
    level_6_version = models.ForeignKey(models.PublishableEntityVersion, null=True)

    # This is going to be very index heavy, but hopefully the table itself
    # doesn't grow too large if we constrain it to only show published and draft.
    # We can do incremental updates as drafts are updated, i.e. we should never
    # be rewriting a whole course's hierarchy when a single subsection changes.

    # ForeignKeys mean implicit indexes already, so we can do searches for
    # individual containers easily enough. We'd need to add indexes for
    # efficient ordered traversal, which in this model would be a composite
    # index with ordering, e.g. (level_6_entity, level_5_order, level_5_entity,
    # etc.)

This model isn't fully baked, but I think the basic idea is workable. Something flat that represents hierarchy, is easily filterable, and where callers can efficiently tack joins onto the queryset to add whatever data they think is relevant. I think that we can potentially do some really good caching once I can land the publishing/draft dependency stuff, but that the caching would mostly happen at the edges (e.g. content_libraries), while the inner pieces like containers would continue to pass QuerySets to make things more extensible.

Model Considerations and Tradeoffs

Limitations

1. There is a fixed hierarchy limit, so content of arbitrary depth cannot be represented.
2. The representation makes reads fast, but it does waste a fair amount of space because sibling nodes are very redundantly encoded. This makes it inappropriate for historical data.

How to handle containers that may exist at different levels of the hierarchy?

There are containers like OutlineRoot which may hold children at different levels of the hierarchy. I think that there are a couple of options:

1. Treat these containers as special, existing in its entirely separate table.
2. Reserve the top level for these containers that aren't fixed to a particular level of the hierarchy. That would make it so that some of these rows would be sparse, e.g. (component_1, unit_1, subsection_1, section_1, None, None, outline_1)

Do we need separate tables for Draft and Published hierarchies, or can we unify them?

There's a lot of commonality there, but a unified table is going to need a boolean field in every index. I still feel like they're different models from the point of view of their relationships with other things, but maybe that just really means they're two proxy models on top of the same underlying one. I'm currently leaning towards making separate concrete tables that are derived from the same abstract model, to centralize the code but still give separate tables to index, join to, and receive signals from.

[ormsbee]

(Also copied from the original ticket):

Random, unbaked thought: In our LC-courses prototype, we mapped course usage keys to publishable entities. I think this is quite reasonable for state management. But one of the other things we use the usage keys for is jump_to links, and right now there's no single identifier for "go to this component in this particular part of the course". Instead, we do some graph traversal to find the left-most appearance and always take you there. Likewise, inheritance has to figure out the authoritative path to this component in order to map out what its attributes are going to be when it's being rendered by itself, with the weird side-effect that a component can seemingly break inheritance rules because you're not looking at it in its first instance in the course.

But we could map usage keys to rows in PublishedContainerPath instead, or have some decorated usage key convention so that we could keep the same user state, but have two different URLs and maybe even two different sets of inherited fields for the same content.

I don't know if this is necessarily a good idea. But it's a dimension of flexibility that we haven't really had before, and it maps pretty squarely onto something like this model.

[ormsbee]

Intersection with Dynamic Content

@kdmccormick: Wanted to bring this to your attention especially:

I don't know how this proposal would interact with dynamic content. My initial thinking was that we would encode every possible child element into these tables, and that it would be up to higher level things to further filter down using things like content groups and user partitions. But that doesn't allow the flexibility to re-order things (as some randomization use cases would require).

I also thought that maybe we only represent placeholder Selector nodes in this table, that Selectors would later expand out. But that has the problem that we can no longer always look up a given Component and quickly get its ancestor listing.

That led me to a sort of hybrid thought: We still represent everything in the hierarchy, even things in AB tests. But elements that are dynamic children have NULL for the ordering. They exist for the purposes of ancestor lookup, but they're not really a part of the Unit. It would be the responsibility of something else joining to it (either keying to something off the Unit, or to a placeholder Component-level node in the hierarchy table) to provide the composition information.

[bradenmacdonald]

Dynamic content thoughts, very rough:

Another option is to consider this PublishedContainerPath feature to retrieve the "authored outline" only, with that meaning:

1. It gives you the whole outline of the [course] as seen by authors, but
2. it does not account for permissions, content groups, exams, start dates, A/B tests, or other things that would hide things from the static outline, and
3. wherever randomized content [or other dynamic transformer plugins] occur in the outline, there is just a single placeholder (DynamicContent). This is necessary because the randomizer is specified at the component level and there is no lower level to put the potential children.

A completely separate set of entries in the table could describe the potential hierarchy of each dynamic area - for example if you had Randomization, there could be a separate set of rows with the various Components at level_0_entity and DynamicContentRoot as the root at level_1_entity. So it's like an isolated hierarchy from a mini-course, but it has a DynamicContentRoot as its root instead of OutlineRoot. Or maybe we just re-use OutlineRoot for both uses. As Dave mentions, this would likely be unordered.

When learners want the outline, we first load the authored outline, joining all the dynamic content data (1 query), then do a post-processing step to join in additional relationships needed and load it (1 query), then apply the transforms (permissions, randomization, etc.) and produce the final learner outline.

[kdmccormick]

Thoughts from the meeting:

• Why not make level_0 a component?
  • in the future, things like files and uploads might be at level_0
  • keep the model focused on paths, not on course stuff
• Why not make level_1-5 containers?
  • xblock state is associated with PEs, not Containers
  • but Containers would be better for correctness
• Why not make level_6 a nullable outlineroot?
  • let's do this

[bradenmacdonald]

@ormsbee Why do you think that files & uploads should be part of the hierarchy?