Indexed FinFunctions and hash joins
#355
Merged
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
The codomain defaults to `TypeSet(T)` for the appropriate `T`.
Also, add function `is_indexed`.
Don't export the underlying concrete types. Also, add pretty-printing for indexed functions.
Multiway hash joins are not yet supported.
Mainly for the sake of accurate comparison with other join algorithms.
This departs from the convention used in C-set indices but the sorting is irrelevant in hash joins, the main application of these indices.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This PR:
FinFunctions andFinDomFunctions with indices, so that preimages can be efficiently computedAs expected by their asymptotic complexity, both the sort-merge join and hash join are way faster than the naive algorithm, the nested loop join. At least in these benchmarks, the hash join is generally a bit faster than the sort-merge join. Note that this includes the time for computing the indices; when used with the pre-indexed functions coming from C-sets, the performance of hash joins should be even better.