Skip to content

Cursor should be a tree for fast traversal of intermediate paths when paginating #43

@theronic

Description

@theronic

During intermediate path traversal, we currently re-read some Relationship indices from 0, when we could be continuing from the previous traversal.

E.g. in can?:

(->> (rels-range-resource->subject-type db resource-type resource-eid via-relation intermediate-type 0) ; cursor 0. we would like to pass cursor her.
  (some (fn [intermediate-eid]
  (can? db subject target-permission
  (spice-object intermediate-type intermediate-eid)))))

And a few places in traverse-permission-path, e.g.:

:relation
;; Direct relation - forward traversal
(when (= subject-type (:subject-type path))
  (->> (rels-range-subject->resource db subject-type subject-eid (:name path) resource-type 0) ; we'd like to pass cursor here, but need better cursors.
 ...))

and

(let [target-relation (:target-relation path)
        intermediate-eids (rels-range-subject->resource db subject-type subject-eid target-relation intermediate-type 0)] ...) ; note the zero.

This is because the cursor we return to the caller is the last resource-eid emitted by the merged lazy seq containing sorted & deduplicated resources from terminal indices (of the resource types the caller wants). However, this resource-eid has no relation to the intermediate resources we had to traverse to yield those indices, so we have to start over for all intermediate lookups, which is slow.

As long as intermediate resources are sparse, this is not a big problem, but it becomes a problem when intermediate resources outnumber terminal resources.

A solution would be to replace cursor with a tree of cursors indexed on path, so that each intermediate traversal can continue from where it left off. The shape of cursors would mirror the expected result from expand-permission-path, but with a cursor to continue from along that path.

This requires building up a path to pass into traverse-permission-path, so it can look up the right cursor, and means each traversal has to return [cursor resource-seq] to its caller.

Implementing better cursors for intermediate path continuation should be a major performance improvement. Without this, subsequent pages are slower than they need to be, because we have to read all intermediate resources / subjects all over again on the Nth page, to calculate the terminal index ranges.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions