All we need is an easy explanation of the problem, so here it is.
I have table
currency_pair(c1, c2); values are
(usd,bnb), (cake,bnb), (cake,eth).
I need to find the shortest path that allows me to compare
The result here would be those same values. I can then use the first pair to establish a usd-bnb relationship, which I can then use to calculate a usd-cake relationship, which I can then use to compute usd-eth.
Since order is not determinate, the first step I did was create a materialized view,
currency_pair_map(c1, c2), which is a union of
select c1, c2 union select c2, c1. This would seem to simplify the logic.
If I am thinking about this correctly, what I need to do is use WITH RECURSIVE? I should also have some sort "depth_limit" parameter that ensures that a query fails if it is impossible to establish a pair.
Thinking about this out loud, we should always begin with:
SELECT * FROM currency_pair WHERE c1 = 'usd' AND c2 = 'eth'
If there is a result, we should end there.
If there is not, then we need to find all
usd-* pairs and continue search until we find one that ends with
Using this logic, so far I have:
WITH RECURSIVE pair_route AS ( SELECT 1 depth, cp1.id, cp1.c1, cp1.c2 FROM currency_pair cp1 WHERE cp1.c1 = 'usd' UNION SELECT pr1.depth + 1, cp2.id, cp2.c1, cp2.c2 FROM pair_route pr1 INNER JOIN currency_pair cp2 ON cp2.c1 = pr1.c2 WHERE pr1.depth < 4 ) SELECT * FROM pair_route;
I think this is correct. Now I just need to track path (IDs) and identify the shortest paths.
How to solve :
I know you bored from this bug, So we are here to help you! Take a deep breath and look at the explanation of your problem. We have many solutions to this problem, But we recommend you to use the first method because it is tested & true method that will 100% work for you.
You could use this recursive query:
WITH RECURSIVE c AS ( SELECT c1, c2 FROM currency_pair UNION SELECT c2, c1 FROM currency_pair ), curr_path AS ( SELECT ARRAY[c1, c2] AS path FROM c WHERE c2 = 'usd' UNION ALL SELECT c.c1 || p.path FROM c JOIN curr_path AS p ON c.c2 = (p.path) WHERE c.c1 <> ALL (p.path) ) SELECT path FROM curr_path WHERE path = 'eth' ORDER BY cardinality(path) LIMIT 1;
First, I calculate the symmetric closure.
Then I construct arrays of "conversion paths" by starting with the pairs we have, then prepending new currencies to arrays that can be converted to the first array element and do not yet appear in the array.
Once I have got all conversion chains that end up in
'usd', I pick the shortest chain that starts with
While Laurenz answer is great, it is not the most efficient.
I found that the best way to do this in production is:
- start with trying to find the direct pair
- then try to find pair by looking up the first leg, the last leg, and all connections
- then fallback to Laurenz solution
The query mentioned in #2 would look something like this:
WITH pair_symmetric_closure AS ( SELECT cp1.c1, cp1.c2 FROM currency_pair cp1 UNION SELECT cp1.c2, cp1.c1 FROM currency_pair cp1 ) SELECT * FROM pair_symmetric_closure psc1 INNER JOIN pair_symmetric_closure pcp2 ON pcp2.c1 = psc1.c2 INNER JOIN pair_symmetric_closure pcp3 ON pcp3.c1 = pcp2.c2 WHERE psc1.c1 = 'usd' AND pcp3.c2 = 'eth';
Note: Use and implement method 1 because this method fully tested our system.
Thank you 🙂