metabase / metabase/macaw

Consider replacing "map-key mapping" with trie structure

Open
#47 3 comments 0 reactions 0 assignees View on GitHub
optimization
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.