Unification searches with many results are slow
Since the type tree update, queries that return many results are slow, most notably
:: a. This is because keys to a
Map are stored, so we require O(r • log(n)) rather than O(n) where r is the number of results and n the size of the database.
This can be fixed by using a different type for the map, ideally an array, but that is complicated.
Another option is to store a list of records annotated with a boolean indicating whether it should be returned. This is what is being done with
FilteredStore in the ngrams branch (see #143 (closed)). Then search queries can be seen as refining those booleans, and to produce the final results is linear again. However, a refining function is easy to derive from a search in the type tree.
Ideally, this is made more general s.t. you can annotate the records with any data. If we annotate records with a type distance measure, we don't need to recompute that for equal types if it is connected to the type tree.