Nested Categories

[riqwan]

Abstract

Providing a way for store managers to organise products into different categories that make it easier for users to browse through and find products that they are interested in.

Note: This RFC focuses purely on Categories and its nested capabilities. Adding products to a category will come in as a follow up RFC.

Motivation

Nested Categories are a way of organising products into a hierarchy of categories, with each level representing a more specific subcategory within the larger category. This makes it easier for customers to find the products they're looking for, as they can navigate through the categories to find the specific products they're interested in.

Collections, on the other hand, are groups of products that are being sold together for a limited time, such as a spring collection. While categories are mainly used for organising products, collections are more focused on grouping products for sales or marketing purposes.

Goals

• Add category to a store
• Add a sub-category under a category

Non Goals

• Add product to single/multiple categories
• Filter products based on categories
• Category ranking

Proposal

From the list of tree depictions possible in relational databases (nested set, materialised paths, closure tables), I’m proposing the fairly simple and straightforward “Parent-Child” structure for the following reasons:

• Easy pattern to understand, thereby easy to code, extend and customize
• Simple API calls and responses
• The drawbacks of this approach can be circumvented easily
  • Caching
  • Nested depths limitation
• Performing actions on category record doesn’t cause side-effects (ex: regenerating tree paths)

This is a simple visual of how the category parent-children relationship look like:

Each category node, contains the ID of its parent category node.

Limiting the tree depth

To build out the entire tree, we do have to recursively call each child until the last node or vice versa for the parent node. This can very quickly cause O(N²) performance issues when we have a very deep tree structure. To contain this, we should have a limit on the nested depth. By default we could recommend a limit of 4, but this can be configurable if customers are willing to make the performance tradeoff. Lets refer to this as MAX_CATEGORY_DEPTH from here onwards.

I've taken a look at some large ecommerce sites and can see that they don't go beyond 4 category levels.

Taking a deeper dive into this diagram, lets split our operations that we can perform on a category.

Adding a new Category

1. To create a top level Category
   1. Create a category with parent_id as null
2. To create a sub-Category
   1. If category depth > MAX_CATEGORY_DEPTH
      1. Fails hard with error “Category tree depth reached”
   2. Fetch existing category ⇒ parentCategory
   3. Create a category with parent_id as parentCategory.id

Moving a category

1. To move to a top level Category
   1. Update category with parent_id as null
2. To move to another parent
   1. Fetch new category ⇒ newParentCategory
   2. Update category parent_id from “catg_02” to newParentCategory.id (”catg_03”)

Note: The caveat here is that the subtree of this category will tag along the journey as well

Deleting a category

Note: This will have implications on product categories, but we are not going to focus on that aspect here. This will come in as a separate RFC.

1. Deleting a category without children
   1. Delete OK
2. Deleting a category with children
   1. Here we have 4 options:
      1. Preferred: Delete fails hard with error “Category with children cannot be deleted”
      2. Delete fails hard with error “Category with children cannot be deleted”
         1. Add a configurable flag to delete irregardless
         2. This would have to purge all products in children category as well
      3. Delete fails with error “Category with children cannot be deleted without an target category to move the children”
      4. Deleting a category, deletes all of its children

Fetching collection of categories

Every category fetch in a collection, makes 2 additional DB queries and returns this in the response:

• Fetch parent
• Fetch immediate children

You can fetch categories with a few filters:

1. Default - Returns all categories
2. Filter by ID
3. Filter by parentID

With this, the number of API calls to build an entire tree path will be MAX_CATEGORY_DEPTH - 1

Fetching a category

Every category fetch (GET /categories/:id), makes a few additional DB queries and returns this in the response:

• Category find
• Recursive fetch until all parents are fetched
• Recursive fetch until all children are fetched

Note: These can be optimized to use a single query using recursive search

Caching

Categories API call will be a dominant API call used by almost all customer that enters the store front. The cost of querying even with the limitations we’ve applied for it is still fairly high. Luckily, categories are something that don’t change too often. We can heavily rely on caching to take care of the bulk of the work and purge cache whenever operations on categories are performed.

We can introduce a service level cache to prevent queries from hitting the db as much.

Model Layer

models/category.ts

export class Cateogry extends SoftDeletableEntity {
  @Column()
  title: string

  @Column()
  is_active: Boolean

  @Column()
  is_internal: Boolean

  @Index({ unique: true, where: "deleted_at IS NULL" })
  @Column({ nullable: false })
  handle: string

  @Index()
  @Column({ nullable: true })
  parent_id: string

  @OneToOne(() => Category)
  @JoinColumn({ name: "parent_id" })
  categories: Category
}

[srindom]

Would it make sense to add a ancestor_path field to the Category entity? It would be a string with ids of ancestors split by a .. The benefit is that we move the heavy recursive behavior to write time instead of read time. We can always know the top-level category for a given sub-category without traversing the tree.

Creating a new sub-category would be pretty simple:

ancestor_path = [parentCatg.ancestor_path, parentCatg.id].join(".")

There would be some more work when moving a category as that would require:

movedCatg.ancestor_path = [newParentCatg.ancestor_path, newParentCatg.id].join(".")

for (const childCatg of movedCatg.children) {
  // recursively update child catg
}

[riqwan]

I've moved my position to using materialized paths, that should handle this scenario of queries on ancestors and descendants on reads as you've mentioned here.

[magnusdr]

I know this would complicate things a bit, but I can see quite common use cases for categories with multiple parents:

• Dressers could fit inside a "Bedroom", "Hallway", "Living room" category in a furniture store. If you would shop by product category instead of room, you would also find dressers inside "Storage".
• Headsets could fit inside both "Computers -> Accessories" and "Electronics -> Audio & Hifi"
• A headlamp could fit inside both "Electronics -> Battery and lighting" and "Sports -> Outdoors -> Equipment"

If not having multiple parents on categories, another option would be multiple categories per product. Although it would require more work from the user to manually add extra category to many products (could be automated). This option would also result in multiple categories with the same name, making it more difficult to differentiate them without seeing it's parent name.

I do recognize the added complexity though. We would then create a directed acyclic graph instead of a tree structure, which would require some extra validations to make sure the graph stays acyclic (and not circular).

[riqwan]

Thank you @magnusdr, I understand the use-case. I purposely went against the DAG method because of the complexities you've mentioned - relational databases in general don't handle large trees well, let alone DAGs. There is another RFC coming soon, where you will see that a user can add a product to multiple categories.

The problem of "user having to manually add extra categories to products" can be solved either through UX or workflows as you've mentioned. We're also making an assumption here that Dressers as a category is just one category (even though they're named the same). F.ex. You could have a Dresser A product that fits inside the Bedroom category, but not Hallway. Similarly you could have Dresser B product that fits in Hallway and Living Room, but not Bedroom. This would reintroduce the problem of needing to have multiple categories of the same name even under DAG.

[JuanmaDiazRivas]

Hello Riqwan,

Amazing job, just to clarify. Why cant we just remove the idea to add a relationship between categories?

i mean, men and women has shoes, so we have 3 different categories shoes, women and men.

When we apply filters, we can just select category men and shoes!

On my point of view we can have a table of categories with a deep level, for example men and women could be level 1, clothing and accesories level 2, and rings or shoes level 3

With this type is structure we dont have redundant categories!

Also, when we create a product we can choose in a select the categories we want for an item (ex: level 1 category men, level 2 category clothing, level 3 category shoes)

Thank you for read me.

Juanma Díaz.

[saranp]

Hi Riqwan,

I am proposing a System default category.

When the Category or Sub-Category is deleted - the items (or children) in that list can be auto-assigned to a system default category, which will not be visible to users. This will ensure that the data added in the wrong category/sub-category can be easily added again to the right category/sub-category with little effort by editing the items.

There are chances that the category needs to be corrected; in that scenario, deleting the items and adding them again to the right category will take a lot of effort - if we provide a simple means to modify would make life easier for the person who maintains data.

Does it make sense to you?

Thanks,
Saran

[micotodev]

An alternative to this would be if we allow the set to null cascade, then there can be a separate 'Unassigned' area that handles all products not currently assigned (automatically not visible to customers).

If we wanted to handle soft deletes, we could add metadata to the deleted category (something like 'previous_products') which is an array of the products assigned at the time of deletion. 'Restore' functionality would re-assign all products that have not been manually re-assigned since deletion.

[durdenx]

Your talk about product categories in that RFC but what about the ability to add a single product to multiple collections? Like you said collections and product categories have different purposes. For instance, I want to add a product in a featured collection and on the sale collection or the winter collection at the same time.

[vbrzezina]

Hello @riqwan, I ran into an issue - when I try to set the same parent to multiple categories I get this error
Product_category with parent_category_id, rank pcat_01GVXJRDK5EK57EGY871PBBYFX, 0 already exists.

[vbrzezina]

Found the issue.. It's the unique index for parent/rank in v1.7.14 (which is not published from master apparently)..

      CREATE UNIQUE INDEX "UniqProductCategoryParentIdRank"
      ON "product_category" ("parent_category_id", "rank");

Can you explain the intention behind it?

[riqwan]

Thanks for surfacing this @vbrzezina!

• Can you let me know which version of medusa this came up in?
• Also, have you have already created categories in the previous versions?

Rank is a column that we use to sort how you want the categories to be ordered in the API response. We've also scoped this out to be under every tree node "parent_category_id". We don't want 2 categories to have the same rank, so we've added a uniqueness index there.

[flashjames]

@riqwan

I wrote a feature request in this comment #2844 (reply in thread)
"Specify depth of a categories you want to search."

"For example, say we have this category subtree:
perfume/
perfume/children-perfume/

?depth=0&q=perfume , would return [perfume]
?depth=0,1&q=perfume , would return [perfume, children-perfume]
?depth=1&q=perfume , would return [children-perfume]"

And you replied "can you share some use-cases on why you'd want to search for a category under a certain depth? I haven't seen many examples of categories being text-searched on an ecommerce store." and I said I didnt remember.

Now I had to workaround this limitation, so let me tell you what the use-case is.

Use case

I have 500 categories, with a depth of 8.
For the main menu I only need the categories of depth 0-2 (50~ categories).

I.e. with this feature added I don't need to load all 500 categories for main menu.

It would also be useful to be able to get all categories, starting from a category id i.e. get all child categories starting from a category id.
I show a sidebar on left side, with all subcategories from the current category, and with this feature I don't need to load all 500 categories to display this.

[riqwan]

Thanks @flashjames , I've added a ticket to investigate and potentially implement depth into the API - can def see the merit in having this in the API.

Could you elaborate on what It would also be useful to be able to get all categories, starting from a category id i.e. get all child categories starting from a category id. means and check if include_descendants_tree in the list endpoint or the GET /product-categories/:id endpoint suits that need? Since these endpoints return the entire tree with those settings

[riqwan]

@flashjames - take a look at this PR #3880

I've extended the API to include depth.