Optimize entities

Open
#227 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
25/100
Issue type
Refactor
Clarity
Needs clarification
Activity status
Stale
Tech stack
clojure
Domain
databases, performance

Research direction

Start by reading the current entity attribute lookup, the eavt and btset indexes, and the Iter implementation; also review the bounded-count work in #226. Compare caching all entity datoms with retaining an Iter and define a fallback for large reference sets. Done means lookups are faster without problematic memory use for entities with many references.

Written by the indexing model from the issue text.

Description

Also partially dicussed on Slack:

Currently an attribute lookup on an entity does a search into the btset and then caches the result. This is inefficient since the all the attribute values are right next to each other in the eavt index.
Getting them all at once and storing them in a cache makes sense, but has huge problem:

  1. What if the entity has a many ref with many many references?
  2. What if the entity has MANY attributes

I think 2) is unlikely a use-case and can be ignored. However 1) is an issue.

Ideas:

  • Save an Iter instance that represents (Datom. eid nil nil nil nil), ie, all Datoms belonging to an entity. This is fast to get.
  • Enhance Iter to allow fast searching within an Iter. This would mean we can avoid the cache of an entity and just lookup in the Iter.
  • For avoiding performance problems with 1) we could add a heuristic to fall back to the current implementation when the count of an Iter is "too large" (> 20??). For this implement bounded-count for Iter. See #226
Dominant language
Clojure
Stars
5.8k
Forks
318
No merged PRs in 30d

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from tonsky/datascript

All issues in tonsky/datascript

Similar issues

More Clojure issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.