Versions Compared

Old Version 65

changes.mady.by.user Daniel Hanrahan

Saved on

compared with

New Version 66

changes.mady.by.user Daniel Hanrahan

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

Here is a visualization of both algorithms, executing a query for /bookstore/categories[@code='1']/books[@title='Matilda']:

Existing solutionProposed solution

Because the existing solution uses a regex, all nodes in anchor 3 need to be examined to see if they match the regex.

Because the proposed solution uses sub-queries to look up each path component, only relevant nodes are examined.

  • Green and yellow nodes have been checked against the regex.
  • Yellow nodes matched the regex, and thus have JSON attributes examined.

  • Green nodes have been looked up using an index-only lookup.
  • Yellow nodes have had JSON attributes examined.

If the number of nodes is doubled, the number of xpaths checked against the regex is also doubled (linear complexity).

If the number of nodes is doubled, the same number of nodes is still scanned in this case (constant complexity).

...