Stream: terminology
Topic: ValueSet/$expand Paging - Offset vs State param
Colby Seyferth (Feb 22 2019 at 19:31):
Terminology folks, this thread in the implementers stream led to us debating the usefulness of the offset param when paging results of a ValueSet.$expand operation.
Because the codes in a ValueSet aren't necessarily ordered, I think it makes more sense to use a kind of pagingID parameter that will let the user save the state from the last $expand instead of the client just passing in the Offset parameter. Grahame suggested I bring the discussion to this stream.
Michael Lawley (Feb 25 2019 at 07:06):
I dispute the claim that they aren't ordered. Happy to accept that the order may not have any special significance, though, but the paging semantics does require the terminology server to maintain some kind of order.
Where I see difficulties is with infinite value sets where there's no obvious or simple natural ordering.
The (very) nice thing about using an offset is that the request is entirely self-contained; no state needs to be preserved server-side to support paging and it's also not tied to a db cursor so is much more cacheable
Colby Seyferth (Feb 25 2019 at 15:01):
Ok, sure, i concede they are technically returned in some type of order, since they are represented by a list or array or something. (even though in math/computing: a "set" is a collection of distinct objects that aren't ordered. but this is not important, just kind of awkward...)
But the point I was making is that the order does not matter, and a client is never going to say "just give me the Nth code through the Kth code" or something without first having gotten codes 1 through N. The param is only used for paging. But instead of letting the client just say "give me the next page", we are making them keep track of the offset/count/total. And the server may not even respect the count they pass in. So we are making it harder for clients to get the list of codes.
In terms of making it better for servers: The offset param assumes the server just stores the valueset in a big table; that is not always the case.
If the server does not have the codes readily indexable, then they'd have to either:
- iterate from the beginning each time until they get to the offset, then return the next codes, or
- cache the whole expansion of codes
Neither of these solutions seem ideal.
Grahame Grieve (Feb 25 2019 at 23:09):
I just wonder how important this is. @Michael Lawley do you have any statistics on how often the client pages past the first page?
Michael Lawley (Feb 25 2019 at 23:18):
I could maybe dig out some stats like that, but they'd be heavily client & context dependent.
Most of the use of $expand with a filter parameter only wants the first N (and the UIs we see don't offer ability to go past that).
For us the default max of a "full" $expand call is 50,000 so it's rare that that many codes are ever generated in an expansion.
Michael Lawley (Feb 25 2019 at 23:30):
Regarding server-side implementation details, we do not "store the valueset in a big table". We compile the $expand request into a query and run it, then give you K codes starting from posn N. Caching happens transparently in the db layer.
Expansion has two parts: matching the set of relevant codes, and ordering the matched codes. The first part can be very fast, so re-running is not a major problem. The second part is only really useful if the filter parameter is supplied and is only costly when the set of matches is large. Fortunately people rarely want lots of codes returned when they provide the filter parameter, and even less frequently want a second page of results.
Michael Lawley (Feb 25 2019 at 23:34):
There's another significant problem created with using a token rather than start and offset for paging. As stated earlier, it creates a stateful interaction between the client and server which means that if you've done any horizontal scaling of your back-end, then you need to ensure that the requests for subsequent pages are routed back to the node that served the original request. This means you need smart routing and smart http caching between the client and server.
It also introduces timeout issues; the paging token will only have a limited lifetime, so all the intermediate layers need to be in alignment to ensure stale results are not served up.
This has been a sore point for the NCTS in the past.
Peter Jordan (Feb 26 2019 at 00:03):
That's also, roughly, how I implement this, in C# middle tier code ... valSet.Expansion.Contains = es.Contains.GetRange(offsetNo, countNo); where valSet is a ValueSet object and es is a ValueSet.ExpansionComponent object. The later is populated by each $expand request which, in turn, results in a DAL call, (T-SQL table-valued function) where query results are automatically cached by the DB Server.
Michael Lawley (Feb 26 2019 at 00:10):
All things considered, it is this last issue, the entanglement of (stateful) paging with HTTP caching and load balancing / scaling that is the real problem.
Grahame Grieve (Feb 26 2019 at 01:42):
I have a single server and store stuff in memory. I drop it when memory becomes scarce. I don't mind either way. But it doesn't seem like too big a deal to do routing on an internally constructed token. It might skew your load balancing, but given that I think that following up for extra pages is a uncommon thing to do, it's not that big a deal?
Jim Steel (Feb 26 2019 at 01:46):
What we currently do is route stateful calls ($closure and resource search, which also has stateful paging) to one specific server in the cluster. The alternatives, of making a given client's searches stick to a given node in the cluster, seems to require client-side participation involving sticky session headers. Its a nuisance for $closure and resource search, but those aren't typically as high-volume or speed-sensitive for the terminology uses we see. $expand, by contrast, is both of those things, hence our reluctance.
Grahame Grieve (Feb 26 2019 at 01:48):
sure $expand is your high-volume call. but is the follow up high volume?
Jim Steel (Feb 26 2019 at 01:48):
As soon as its a possibility, you have to route it back to the same server it came from
Grahame Grieve (Feb 26 2019 at 01:49):
sure. but is that happening high volume?
Jim Steel (Feb 26 2019 at 01:49):
Doesn't matter
Jim Steel (Feb 26 2019 at 01:51):
We also currently prohibit $closure (which is fine because its not only stateful but non-idempotent) and search (which is stateful but idempotent) inside batch requests, because otherwise we'd have to open up POST bodies to determine whether they are stateful or not. We really want to avoid having to do that for $expand requests
Michael Lawley (Feb 26 2019 at 06:05):
define high volume - we might go days or weeks with it not happening, but then someone comes along with a particular use-case or approach to solving their problem and they'll do it all day for a week. [Note, this is based on looking only at our public server's logs. There are many other Ontoserver instances out there with potentially wildly different uysage patterns.]
Michael Lawley (Feb 26 2019 at 06:11):
My position is that, even if getting the next page is a low-volume scenario, changing / adding token-based page routing is has a major impact on implementers running high-volume services. Routing on an internally constructed token is nasty; it is application semantics bleeding into layers where things should be transparent and has all sorts of knock-on consequences.
e.g., you can get the routing right, but if the response is cached at the HTTP layer, then the cached token for "next" may no longer be valid. Only solution for a client that gets a 404 on the "next" link is to make a cache-busting request on the original $expand (which may be several pages back) or for the server to know how to tell the cache to pro-actively expire pages.
Robert McClure (Feb 26 2019 at 22:22):
So given all this, are you all saying that not one implementation would support a paged $expand. Ipso facto, any expand bigger than a terminology server's max can never be expanded. Correct?
Peter Jordan (Feb 26 2019 at 22:42):
Paged expansions are supported by those servers that implement the offset and count parameters - including mine. However, my Server will not still not expand any Value Set larger than 9,999 as it's not designed as a means of downloading large Code Systems in their entirety.
Jim Steel (Feb 27 2019 at 00:11):
Ontoserver also supports paging $expand using count and offset
Michael Lawley (Feb 27 2019 at 00:13):
All servers I know of support paging with the existing mechanism.
Changing the mechanism to be like that for paging Bundles is what I'm pushing back against
Grahame Grieve (Feb 27 2019 at 07:17):
I’m not entirely sure that I’ve folowed you. You can turn your page / offset parameters into a state parameter, and anything else you need, and then it works no differently for you. You don’t have to support anyone else’s state. So I’m not sure why you’re pushing back so hard?
Michael Lawley (Feb 27 2019 at 21:14):
I don't know why you say "works no differently"?
A state parameter couples the client with a specific node in my stack as well as polluting the http cache. This is because only the original node that did the $expand knows the mapping from the state parameter to the associated $expand parameters.
This means:
1) the routing layer needs to to change to be aware of this parameter
2) the HTTP caching layer needs to to change to be aware of this parameter
3) scaling down the number of nodes needs to worry about stale state; if you shut down the original node you lose the mapping
To me, this is all "works differently".
As @Jim Steel said, we also face similar issues with paging of _search and $closure. We have a work-around that "works" but is not good; it adversely affects scaling behaviour. Fortunately these cases are not (currently) core issues. However, $expand is and stateful paging behaviour for $expand would require a major re-work and complexity increase in our deployment models.
Grahame Grieve (Feb 28 2019 at 21:13):
but you can just put all those things in your state parameter, and ignore it's statefulness
Michael Lawley (Feb 28 2019 at 21:43):
What do I do with the ValueSet from the POST?
Grahame Grieve (Mar 01 2019 at 00:57):
oh I hadn't considered the POST usecase
Josh Mandel (Mar 02 2019 at 14:18):
For the POST you could still have a pagination token parameter (opaque to the client) while keeping all other parameters constant across calls, as is done with offset|.
Grahame Grieve (Mar 02 2019 at 19:48):
isn't that what we have now?
Josh Mandel (Mar 04 2019 at 14:06):
No, right now we have an integer with offset semantics ("Offset is number of records (not number of pages)")
Josh Mandel (Mar 04 2019 at 14:07):
Here I was talking about an opaque value with "next page token" semantics
Grahame Grieve (Mar 04 2019 at 19:16):
right but it would be functionally equivalent. I don't know that buys anyone
Michael Lawley (Mar 05 2019 at 23:58):
Leaving aside POST, the main differences are (single) server-calculated tokens vs (multiple) client-calculated "tokens" (_usually_, but not always, only varying the offset value).
When the client is in control, it can also vary the page size allowing "get me the first few, get me the rest" type behaviour. This can be useful for building responsive UIs. When server is in control, then client has no say on varying page size.
Also, if client asks for count=0, what should the page size be in a server-controlled token?
Josh Mandel (Mar 06 2019 at 01:04):
From my perspective if we can get agreement on a set of client controlled parameters and servers don't have any concerns with being able to support these across arbitrary data, then that is a big win.
Josh Mandel (Mar 06 2019 at 01:04):
we made a different call when it comes to search result behavior, and I wonder if there is a structural difference here that explains the difference in assessment.
Grahame Grieve (Mar 06 2019 at 01:41):
I think the differences are around work load and value
Robert McClure (Mar 08 2019 at 16:31):
I'm not following the technical end of this but I am concerned that we are defining a process that will create a situation where some value set expansions can never be expanded. I understand the futility of expanding a giant value set. But choosing some arbitrary size - for Apleon DTS it's 1000! - over which it is impossible to get the additional members, is fatal. We need a standard way that in the rare case, something really big, can be created.
Josh Mandel (Mar 08 2019 at 18:56):
Totally agree there, Rob. I think what we're discussing here is a couple of subtly different ways to accomplish just that.
Michael Lawley (Mar 09 2019 at 03:44):
Well, what we're discussing is one of either changing an existing mechanism that has worked perfectly well until now, or adding an additional mechanism to do something that is already possible.
I am still struggling to understand what the real value of doing this is.
Josh Mandel (Mar 09 2019 at 22:16):
As long as today's mechanism is easily supportable by servers without performance concerns, I don't suppose any value in making a change.
Colby Seyferth (Mar 12 2019 at 19:20):
It works "perfectly well" right now because not many people have implemented it. Have any major EHRs implemented it yet? At the fall connectathon, nobody I was working with had started it yet.
Colby Seyferth (Mar 12 2019 at 19:37):
Our server does not always store the valueset in an indexable structure; we can always iterate over the values though, potentially performing business logic on the values before returning as part of the valueset expansion. There isn't a simple way to say "start at the 1000th code" without either:
- starting at 1 and iterating over the first 999, then starting at 1000. or
- on the first request, iterate over the whole entire code set and cache it somewhere in a format that can be indexed, then page from there.
Both of these approaches are less than ideal.
However, if we just use the paging format that everybody can already support because it is the way that paging works for any other resource that isn't this one, then it makes it very simple. It removes the unique server requirement (the paging solution doesn't dictate the data model). And it makes it easier for the client (they don't have to do math. They just say "next" which is the only reason they would want to page anyway).
Michael Lawley (Mar 13 2019 at 21:13):
If, as you say, the only reason for paging is to start at the beginning and go next, next, next, then how is that different (performance-wise) from your second strategy above? (which, as I understand it, is how you'd be doing _search style paging)
Colby Seyferth (Mar 13 2019 at 22:15):
Storing a cache of all of the codes (and other metadata) from the valueset would typically take up a lot more space (It scales with the size of the valueSet: O(n)) than just caching the info about where we are in the search(just a constant amount of data: O(1)).
In terms of time, it would take the same overall amount of time, but having to load the whole set at once to cache it would cause a delay on the first call. This could be kinda weird, but is probably neither here nor there i guess, if they are going to call through all the pages anyways.
Michael Lawley (Mar 14 2019 at 00:26):
Where you are in the search is an index into something else, is it not?
Colby Seyferth (Mar 14 2019 at 13:57):
Where you are in the search is an index into something else, is it not?
Is this like a lead-up question, or the actual question?
Yes, where you are in the search is an index, naturally. Whether that index has to be an integer or not is what we have been going back and forth about, right?
Grahame Grieve (Mar 14 2019 at 22:14):
no, what we are going back and forth on is whether the value has to come from the server or whether the client drives it. (e.g. can the client skip pages, control page size)
Grahame Grieve (Mar 14 2019 at 22:22):
and also whether the server has to remember state. As it is now, the server does not have to remember state. But also, it cannot remember state - it has to rebuild it each time.
Grahame Grieve (Mar 14 2019 at 22:22):
except that this is not true. I build the state and remember it by a hash value generated on the request.
Michael Lawley (Mar 15 2019 at 05:09):
exactly - currently the server does not have to remember state, but it can IF that's an optimisation.
Colby Seyferth (Mar 15 2019 at 13:55):
I don't really have anything else to add to this thread. If you do not concede that the current parameter does not work for all servers as is, then are we actually discussing anything? I've already stressed the performance concerns. Think outside of your own server and it would be a more useful discussion.
Yunwei Wang (Mar 15 2019 at 15:57):
As a general approach, server trends to be stateless.
Colby Seyferth (Mar 15 2019 at 16:11):
As a general approach, server trends to be stateless.
Can you explain this claim? @Yunwei Wang
Yunwei Wang (Mar 15 2019 at 16:38):
Stateful server is easy to implement at small scale but costly at large scale while trying to maintain all server states. Load balancer adds another layer of complexity of sharing states among servers.
Colby Seyferth (Mar 15 2019 at 16:44):
How does a stateless server support paging in a resource that is not ValueSet?
Colby Seyferth (Mar 15 2019 at 16:45):
with a search interaction *
Yunwei Wang (Mar 15 2019 at 16:57):
the Bundle.link.url contains page parameter. example here:
http://build.fhir.org/http.html#paging
Colby Seyferth (Mar 15 2019 at 17:07):
This example uses a state param -_-
Yunwei Wang (Mar 15 2019 at 18:19):
and page parameter :wink:
Yunwei Wang (Mar 15 2019 at 18:30):
I think server can choose either stateful or stateless. It is server implementer's choice. You can implement a stateful ValueSet.$expand by adding state parameter to your server operation definition.
Colby Seyferth (Mar 15 2019 at 18:34):
Right. The spec does not dictate how the server must implement its solution. The server can use a state param or chose not to. Why would ValueSet be any different?
Yunwei Wang (Mar 15 2019 at 18:42):
Can you clarify "Why would ValueSet be any different". Do you mean all EHR servers (excluding Terminology servers) choose stateful implementation?
Colby Seyferth (Mar 15 2019 at 18:47):
No. The current ValueSet.$expand spec lists the "offset" parameter, but does not list a state parameter option. Why does a server have a choice to use a state param when implementing search for any resource if it does not have the option to implement a state parameter for ValueSet.$expand.
Yunwei Wang (Mar 15 2019 at 19:04):
If I remember correctly, while the paging was added at DSTU2, no terminology server had implemented or would implement paging as stateful. I remembered we argued at that time if offset should page based or index based. But no one at time asked for stateid.
Grahame Grieve (Mar 15 2019 at 19:08):
we covered why search is different to value set $expand much earlier in the process. you can't just add a state parameter, you have to add paging etc
Colby Seyferth (Mar 15 2019 at 19:17):
we covered why search is different to value set $expand much earlier in the process. you can't just add a state parameter, you have to add paging etc
Grahame, I think we all understand the difference between search and $expand. And that you can't add literally just a state parameter and call it good. Obviously, the server would return an extra element that would be used for paging. something something forest for the trees.
Colby Seyferth (Mar 15 2019 at 19:20):
It sounds like a page-based offset was considered initially, and nobody in the room represented a server that would benefit from a state parameter. Is it too late to consider adding a state parameter? I've exhausted my performance arguments.
Yunwei Wang (Mar 15 2019 at 19:23):
@Colby Seyferth I am just wondering , do you view this question as a server implementer or client implementer?
Colby Seyferth (Mar 15 2019 at 19:28):
Colby Seyferth I am just wondering , do you view this question as a server implementer or client implementer?
My perspective is: EHR Server implementing $expand.
Grahame Grieve (Mar 15 2019 at 22:17):
So there's a middle ground here - we could say that a state parameter could be added and supported for non-POST expands.
Michael Lawley (Mar 15 2019 at 22:59):
As long as that doesn't break existing clients
Servers are not obliged to support paging, but if they do, SHALL support both the offset and count parameters.
Grahame Grieve (Mar 16 2019 at 01:10):
of course
Michael Lawley (Feb 04 2020 at 22:59):
Following discussions with @Jenni Syed @Michael Donnelly in Sydney, I've now created an issue for $expand paging J#25786 - @Colby Seyferth
Last updated: Apr 12 2022 at 19:14 UTC
