You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
the complexity of querying a list of snapshots is M*log(N) where M is the number of observations queried and N is the total number of observations for a pool
if both M and N is large, this can be quite expensive. to make it more efficient, we can find the indices of the minimum and maximum queried observation time in that period, then use that to narrow the binary search so that it's 2*log(N) + M*log(U) where U is the number of observations in the period
if say you have an observation every 30 seconds, one day contains 2880 observations, one month contains 86400 observations, one year contains ~1M observations, in which case log(N) is about 20
so if you are querying prices every minute for an hour (~120 observations at 30 seconds per block), this will reduce the cost by about 2.5x, which will greatly speed up querying price charts from the app
we should probably have a method in the oracle contract that simply returns all the observations in a time period, which would make price chart querying better in that you can more easily compute low/high in addition to open/close
The text was updated successfully, but these errors were encountered:
moodysalem
changed the title
make it more efficient to query a list of ticks
make it more efficient to query price chajrts
Nov 17, 2024
moodysalem
changed the title
make it more efficient to query price chajrts
make it more efficient to query price charts
Nov 17, 2024
the complexity of querying a list of snapshots is
M*log(N)
whereM
is the number of observations queried andN
is the total number of observations for a poolif both
M
andN
is large, this can be quite expensive. to make it more efficient, we can find the indices of the minimum and maximum queried observation time in that period, then use that to narrow the binary search so that it's2*log(N) + M*log(U)
whereU
is the number of observations in the periodif say you have an observation every 30 seconds, one day contains 2880 observations, one month contains 86400 observations, one year contains ~1M observations, in which case log(N) is about 20
so if you are querying prices every minute for an hour (~120 observations at 30 seconds per block), this will reduce the cost by about 2.5x, which will greatly speed up querying price charts from the app
we should probably have a method in the oracle contract that simply returns all the observations in a time period, which would make price chart querying better in that you can more easily compute low/high in addition to open/close
The text was updated successfully, but these errors were encountered: