[OAK-5592] Write Skew in the Property Index

• Type: Bug
• Status: Open
• Priority: Minor
• Resolution: Unresolved
• Component/s: documentmk, property-index
• Assignee: Unassigned
• Reporter: Kevin Wellenzohn
• Created: 06/Feb/17 13:09
• Updated: 27/Mar/17 05:13

Description

Under certain circumstances the property index (using the ContentMirrorStoreStrategy) may not prune all nodes that could be pruned.

Assume two nodes child1 and child2 having property foo set to bar exist under a common parent node. Moreover, a property index on foo exists. The tree would look like this:

  - parent
    - child1[foo=bar]
    - child2[foo=bar]
  - oak:index
    - foo
      - :index
        - bar
          - parent
            - child1[match=true]
            - child2[match=true]

Assume two concurrent transactions T1 and T2 remove property foo from child1 and child2, respectively. Since the transactions do not see the effects of one another, they do not prune node /oak:index/foo/:index/bar/parent. The reason is that even after pruning their respective child node, there is still a second child node left. Therefore, after T1 and T2 execute, the tree looks like this

  - parent
    - child1
    - child2
  - oak:index
    - foo
      - :index
        - bar
          - parent

In a serializable exeuction of T1 and T2, the tree should look like this:

  - parent
    - child1
    - child2
  - oak:index
    - foo
      - :index

This "bug" does not affect query correctness, but it might impact query performance if it happens frequently, since nodes are traversed that not need be traversed otherwise. I'm not even sure if this is a bug; I see this as an instantiation of the Write Skew problem [1,2] inherent to MVCC and as such it is probably "expected behavior".

[1] http://jackrabbit.apache.org/oak/docs/architecture/transactional-model.html
[2] https://issues.apache.org/jira/browse/OAK-26

Issue Links

• relates to: OAK-3380 Property index pruning should happen asynchronously