Consider replacing "map-key mapping" with trie structure
- Dominant language
- Clojure
- Stars
- 23
- Forks
- 4
- PR merge metrics
- No merged PRs in 30d
Description
Currently Macaw makes use of various maps whose keys are qualified entities that are themselves represented by maps.
For example, the parameters passed to `replace-names`:
```clojure
{:columns {{:table "orders" :column "total"} "subtotal"}
:tables {{:table "orders"} "purchases"}}
```
Ignoring what we want the library API to look like, there are some practical downsides to using this representation internally:
1. The relaxed look-up (`find-relaxed`) method requires a linear scan over they keys of a persistent map - slow!
2. Since the ordering of the keys is non-deterministic and we return the first match we find, this may also be non-deterministic!
3. We may want to do something different when there are multiple matches - e.g. return all of them, throw an error, etc.
We could still support this with an exhaustive scan that accumulates all the results, but that's even more expensive.
An idea for something better would be to build a trie-like structure which us traversed from the "outside in", i.e. right-to-left as identifiers are written. For example:
```clojure
{"total" {"orders" {"schema_1" "primary_orders_total"
"schema_2" "secondary_order_total"}
"payments" {"schema_1" "total_payments"}}}
```
In the simple case of a fully-qualified identifier, we'd now need to do 3 look-ups instead of a single one, so there's no free lunch. On the other hand, we do save hashing the whole map - and clojure does not cache map hashes.
The advantage for partially qualified identifiers is that we can replace a linear seek which needs to check equality with modified keys with a sequence of look-ups. When we reach the end of our crumbs we can then easily enumerate all the children nodes. In the case where there is no match, we can also fail on a look-up step instead of doing a full seek.
They're also not great for pretty printing, given their density. That said, a trie will probably be even worse - so we'd probably want a utility method for printing them nicely when debugging too.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reading the find-relaxed method and the map-based inputs to replace-names described in the issue. Evaluate a trie-like replacement for qualified-entity maps, including partially qualified lookups, deterministic handling of multiple matches, and debugging output; done means the representation and lookup behavior are agreed and implemented.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- clojure
- Domain
- backend, databases
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100