Memoizing Hierarchial Selectors

[ronag]

I'm a bit stuck on how one would go about memorising the following selector using this library:

export function selectItem(items, id) {
  const item = items[id]
  return {
    id,
    ...item && {
      children: item.children.map((id) => selectItem(items, id))
    }
  }
}

Currently if any item in the items state is modified all of the selections need to be rebuilt.

Any suggestions on how to go about with these kind of scenarios?

A more complete example: https://gist.github.com/ronag/bc8b9a33da172520e123

[ellbee]

Hey @ronag, I don't fully understand the example.

Currently if any item in the items state is modified all of the selections need to be rebuilt.

What does a 'selection' refer to here?

[ronag]

@ellbee: If I use that in redux for mapStateToProps it will create a new object for every item every time a single item is updated and also cause a react re-render... which is not very optimal. It would be nice to somehow memoize it. But I don't think it is possible with reselect as is... correct me if I'm wrong,

[ellbee]

I'm sure there will be a way to get this to work without re-rendering everything. Other than the fact that it is a nested tree, I'm still a bit fuzzy on what exactly this example is doing. Can you add an example of what the state object looks like? I don't get the difference between state.nodes and state.tree. Also, what is the purpose of selectEvent?

[ronag]

selectEvent should be selectItem and state.tree is not relevant, not sure why I added it. I've fixed the sample.

[ellbee]

function selectNode(nodes, id) {
  const node = nodes[id]
  return {
    id,
    title: 'Loading...',
    ...node && {
      title: node.title,
      children: node.children.map((id) => selectNode(nodes, id))
    }
  }
}

Oh, you are recursively building the tree in the selector. Would it be easier to keep the tree in the store state and use shouldComponentUpdate in TreeViewNode to only re-render the parts of the tree that have actually changed?

[ronag]

Sure I could build a second structure in the reducer which I need to keep in sync. But that kind of negates the purpose and nice functional aspect of selectors... in this specific scenario.

[ellbee]

I was suggesting that it might be an easier solution than Reselect style selectors in this scenario. Keeping the structures in sync shouldn't be a problem if they are both updated by the same action.

Having realised selectNode is recursive, I can't see a nice way to memoize it in the way that you want. You can't memoize on nodes because of the recursive calls. Every single one is going recompute as nodes + id is going to be unique for any change to nodes. And you can't memoize on an individual node, because although a nodes data might not have changed the data of one of its children might have. This will lead to subtrees not getting recomputed.

@speedskater Do you have any wisdom for us here?

[ronag]

Though, this should be a quite common problem, if one follows the idea of normalising the data structure for your stores (i.e. https://github.com/gaearon/normalizr) you end up with the same problem when you need to denormalise your data for rendering your react component graph...

const nodesSelector = createSelector(
  state => state.root.selected,
  state => state.nodes,
  (selected, nodes) =>
    nodes.map((node, id) => node.merge({
      selected: id === selected,
    }))
)

const treeSelector = createSelector(
  state => state.root,
  nodesSelector,
  (root, nodes) =>
    root.merge({
      children: root.children.map((id) => nodes.get(id)),
    })
)

Every time the selection changes one has to re-build the entire tree... this can't be right...

[ellbee]

Possibly, although you are the first to bring it up! Is there a good reason to have flattened the tree in the first place?

[ronag]

Yes, it is much easier to work with the data in the reducer. The flattened structure is much more natural to transform. From my experience that is the general case. The only reason you want it non-flat is to create the react component graph.

This is just a very simplified example.

[ronag]

I think the "selected" state in a treeview or list is a good example, You don't want to have a "selected" property on every node in the tree. Figuring out which item is selected would be O(n) instead of O(1) when working on the data structure. However, when displaying the data you want it as a graph, thus you want a "reselect" view of the data suited for creating the display.

The only alternative right now is to have 2 parallel data states, which gives me shivers, and also makes updates much more expensive both in terms of complexity and performance, or as my example re-build the entire state view every time something changes which is very slow.

I'm surprised no one else has encountered this issue.

[ellbee]

Yes, it is much easier to work with the data in the reducer. The flattened structure is much more natural to transform. From my experience that is the general case.

I do agree with this as a general principle. However, given the arbitrarily deep recursive tree data structure I am not sure that this example is the general case.

The problem as I see it is that you can only see the ids of the immediate children but don't know if any of these children have changed since the last update. Given that, I can't see how to build the tree without starting from the beginning and rebuilding each node every time.

The reason I suggested that a tree might be more suitable is that if you were updating a tree made from Immutable.js maps, for example, changing a node deep in the tree would change the parent nodes up to the root so you would easily be able to see which nodes have a change beneath them.

The only reason you want it non-flat is to create the react component graph.

Seems like a pretty good reason.

I think the "selected" state in a treeview or list is a good example, You don't want to have a "selected" property on every node in the tree. Figuring out which item is selected would be O(n) instead of O(1) when working on the data structure. However, when displaying the data you want it as a graph, thus you want a "reselect" view of the data suited for creating the display.

You could use the redux store to store a reference to the selected node.

The only alternative right now is to have 2 parallel data states, which gives me shivers, and also makes updates much more expensive both in terms of complexity and performance, or as my example re-build the entire state view every time something changes which is very slow.

Instead of 2 parallel data states, you could just model the tree as a tree?

I'm surprised no one else has encountered this issue.

Maybe they modelled their tree as a tree? 😉 Seriously though, if you have any suggestions as to how Reselect could be changed to support this case I would be keen to hear them, as I don't have any ideas.

[ronag]

I do agree with this as a general principle. However, given the arbitrarily deep recursive tree data structure I am not sure that this example is the general case.

Does it matter if it is arbitrarily or e.g. just a single level deep?

Seriously though, if you have any suggestions as to how Reselect could be changed to support this case I would be keen to hear it, as I don't have any ideas.

The only way I can see to solve this in reselect is if the memoized value was passed into the selector so that one can choose to short circuit the building the view and re-use the previous value.

[ellbee]

Does it matter if it is arbitrarily or e.g. just a single level deep?

Actually, I think it is nesting that causes the problem, arbitrary or not. You could make a custom selector that would work with a single level.

The only way I can see to solve this in reselect is if the memoized value was passed into the selector so that one can choose to short circuit the building the view and re-use the previous value.

Even with the previous state I don't think you can avoid walking the entire tree. However, that does give me an idea that won't avoid the tree walk, but will at least return the same object where child data hasn't changed. I'm going to be out for the rest of the day, but I'll give it a go tomorrow.

[ronag]

but will at least return the same object where child data hasn't changed

Exactly! That was what I was thinking about. That's good enough, just so the entire react render tree doesn't need to re-run and you don't have to re-allocate all that memory. Just haven't been able to realise it yet.

[ronag]

Actually, I think the easiest way to accomplish this is to simply do a connect for the TreeNode react component that would be pretty much perfect in terms of performance. I know it's non-pragmatic redux but it is the simplest solution I can think of.

Modelling the data as a tree inside the reducer just makes everything much more complex in my specific case as the tree is just a view for a data structure that is actually a list (with some plainly visual nested groupings) and 80% of the computations are wasted on constantly flattening the structure for logic as opposed to selecting the view data (neither one is good :/ ).

As far as I understand the pragmatic approach is to model data in the reducer simple and also most appropriate for logic and then use selectors to transform the data to a form appropriate for rendering where you would usually end up with a lot more redundant data.

[ellbee]

Here is the idea I was talking about yesterday. It returns the same object, but at the cost of walking the entire tree to build it and every subtree when stringifying, plus the extra memory that getCachedTree will consume.

import { createSelector } from 'reselect';
import assert from 'assert';
import memoize from 'lodash.memoize';

// return a cached tree if it has been seen before
const getCachedTree = memoize(tree => tree, JSON.stringify);

// build the tree
const selectNode = (nodes, id) => {
  return getCachedTree({
    id,
    title: 'Loading...',
    children: nodes[id].children.reduce(
      (acc, id) => Object.assign(acc, {[id]: selectNode(nodes, id)}),
      {}
    )
  })
}

const selector = createSelector(
  state => state.nodes,
  nodes => selectNode(nodes, 1)
);

const state1 = {
  nodes: {
    1: {id: 1, children: [2,3]},
    2: {id: 2, children: [4,5]},
    3: {id: 3, children: [6,7]},
    4: {id: 4, children: []},
    5: {id: 5, children: []},
    6: {id: 6, children: []},
    7: {id: 7, children: []}
  }
};

const state2 = {
  nodes: {
    1: {id: 1, children: [2,3]},
    2: {id: 2, children: [4,5]},
    3: {id: 3, children: [6,7]},
    4: {id: 4, children: []},
    5: {id: 5, children: []},
    6: {id: 6, children: []},
    7: {id: 7, children: []}
  }
};

const tree1 = selector(state1);
const tree2 = selector(state2);
assert(tree1 === tree2);

[ellbee]

Modelling the data as a tree inside the reducer just makes everything much more complex in my specific case as the tree is just a view for a data structure that is actually a list (with some plainly visual nested groupings) and 80% of the computations are wasted on constantly flattening the structure for logic as opposed to selecting the view data (neither one is good :/ ).

Oh, OK. I thought from the example that the data structure was simply a tree that had been flattened.

[ronag]

Oh, OK. I thought from the example that the data structure was simply a tree that had been flattened.

Well, that sometimes happens when one tries to do a simplified example. Didn't realise it was an important point until after your comments.

[ellbee]

Resolved in this Redux issue

[austinmao]

I have read through the related issues and am a bit unclear on the specific solution with the combination of a flat structure (a la normalizr) and memoization via reselect. What is the best way to "denormalize" a flattened hierarchical structure for consumption by components? For example, if I want to render a table of all objects from an API call, I would need to convert the flat object to an array. What is the best way to do this?

[oyeanuj]

@austinmao: I basically have selectors feeding into each other for every level of normalization. It seems to work fine (except for the problem in #66) but its not uncommon for certain components to have multiple levels of selector composition.

To @austinmao's point, I think it would be great to have a section on the docs that deals with normalized data and best practices when memoizing it.

[OliverJAsh]

@oyeanuj Could you provide an example of what you're talking about there?

[oyeanuj]

@OliverJAsh The comment is super old but I think I was referring to something like this where each prop has many levels of selectors feeding into them:

export const getMemberFromRoute = createSelector(
	getMembersState, // <- selector
	getMemberHandle, // <- selector
	( state, handle ) => state && state[handle],
)

export const getMemberNameFromRoute = createSelector(
	getMemberFromRoute,
	member => member && member.name,
)

[natevw]

Updated link to "resolved in" issue: reduxjs/redux#815

In that thread @gaearon said:

[…] I think a sane solution is:

• The component receives its own data via props
• The component uses connect() to retrieve the data needed to render its children

and pointed to https://stackoverflow.com/questions/25701168/at-what-nesting-level-should-components-read-entities-from-stores-in-flux/25701169#25701169 as a (non-redux) example.

The trade-off to the approach was that "[it] starts to mix smart and dumb components in different levels of the component tree".