FWD » Core Development » Database

Prefetching records into cache can significantly improve performance, especially when access patterns are predictable. One common pattern we've observed in production environments is sequential data access. In many cases, when a user retrieves a record, nearby records are likely to be accessed soon after.
The core challenge is determining what to prefetch. This requires a heuristic that can effectively predict "neighboring" records. Several possible approaches come to mind:
1. Use the recid: Fetch the next recid + 1 ... recid + N records, assuming sequential IDs reflect logical proximity.
2. Follow the sorting index: If records are sorted by an index (e.g., by date or ID), fetch the next N records in that order.
3. Analyze the WHERE clause: Attempt to detect patterns in incrementing fields (e.g., a date or numeric value being filtered) and prefetch based on that inferred direction.

Additionally, we could consider inspiration from ProgressiveResults and implement a form of progressive prefetching, or use them as is with the addition of caching the results in the FF cache.
This technique would be perfectly complemented by #10169 (prefetch in another thread).

While this approach may have limited benefit when the server is already warm and the FF cache isn't fully populated, it could be highly beneficial during initial query executions or in high-load scenarios where cache evictions are frequent. In production, these conditions occur often, making intelligent prefetching a potentially high-impact optimization.

In RandomAccessQuery:
1. Detect sequential increment of a subset of substitution value for the fql. * Add a small LRU cache that would hold the previous subst values for a query. * As key use the existing Key implementation from FF cache, but ignore the subst values. * As cache values, use the current subst values. * Check if a subset of values is being incremented.
2. Compute a single range of values for the incremented fields, next 10 for example.
3. Emit e single query that caches multiple records. * Currently FFcache is active only for a RAQ, will need to add caching for multiple records too.

do i = 0 to 100:
    find tt1 where tt1.f1 = i and tt1.f2 = "field" no-error.
end.

for each tt1 where tt1.f1 between i and i+10 and tt1.f2 = "field" 

Worst case, we cache some unnecessary records that would be removed from the cache anyway due to the LRU alhgoritm.
This needs to be configurable from the directory, I expect that this approach will bring an improvement only for some customers.

Further optimizations:
1. Track if the prefetch records are being read, if true, prefetch again a larger number of records, similar to how ProgressiveResults work.
2. Execute the prefetching queries in a separate thread using a different connection. * There may be a gap at first where the RAQ are being executed, but the prefetching query did not complete yet, so the records are not cached yet, but this needs testing.

Detect Sequential Data Access and Prefetch Records from the Database

Arthur, can you provide a 4GL code that would be detected by such tool? Do you refer to patterns like the one in #10436-3 where you have a nested find? FYI, AdaptiveFind exists in the sense of "prefetching" data for FIND, but this is generated at conversion time where the pattern is clear. Maybe AdaptiveFind can be used in broader patters ... I can't tell. That is why I request a more specific pattern to assess. Some pseudo-code eventually can help.

Alexandru Lungu wrote:

Do you refer to patterns like the one in #10436-3 where you have a nested find?

Yes.

AdaptiveFind exists in the sense of "prefetching" data for FIND

Can it be used to cache records in advance?

I mainly was thinking to detect the sequential nature of the queries at runtime, this could cover a broader specter of cases where multiple queries are emitted with a single parameter changed between them. Anyway, the important part is that instead of large number of queries, only a few is executed and the results are cached in the FF cache so that the first 'future' find fill retrieve the results from the cache and not the DB.

Can it be used to cache records in advance?

This is exactly the point. But AdaptiveFind is used when there is exactly the same WHERE clause and you use FIND NEXT. It basically presumes that it is like a "manual FOR EACH block" if that makes sense. You pattern is different in terms that the FIND is not NEXT and you have different WHERE.

The core challenge is determining what to prefetch. This requires a heuristic that can effectively predict "neighboring" records. Several possible approaches come to mind:

I think this should be analyzed and a viable solution to be prototyped. From my POV, this is a hard challenge. Even if fixing it might be a wonderful performance boost, we need to understand if it is a realistic expectation.
My suggestion is to shrink the scope of it instead of thinking of a general fix that may not be possible to design. In other words, assessing #9802 would be an easier to start with.

Prototype

From #9802 I understand that the i is not evidently scoped, so you are more within the following case:

repeat <clause>:
   find tt1 where tt1.f1 = i and tt1.f2 = "field" no-error.
   ...
end.

which requires a run-time approach.
From the FIND alone, we can understand that we have a conjunction of equalities for indexed properties (in other words we want specific (f1, f2) pairs within a (f1, f2) index).

We do not prefetch eagerly, but we rather start prefetching if we detect that the pattern actually exists.
So we still need to identify whether the find tt1 where tt1.f1 = i - 1 and tt1.f2 = "field" was executed already.

• We either consult FFC for that, but I am afraid that the structures there are cross-session and not even bound to the exactly same FIND statement (aka another session could have run the i - 1 query from a completely other side of the converted code).
• We can wait for #9078 that reuses the same FindQuery instance for the same FIND in the converted code. I would prefer this technique as it can basically log what queries did it execute and use that in our advantage to prefetch.

To prefetch, we emit a range query: select * from tt1 where ? <= tt1.f1 and tt1.f2 = "field" order by tt1.f1 limit ?.

• There is no clear way when/how we increment the LIMIT. Maybe we can just use "batching" like hard-coding it to 10.
• With #9078, we can store the LIMIT at FindQuery level. We can ensure an invalidation policy. If results are not found in the FFC (the ones that we expect to have due to prefetching), it means that it doesn't make sense to use LIMIT anymore as this is not a sequential FIND.

Interpret prefetched results¶

To make use of the prefetched results, we can eventually iterate all. For instance, if we fetch rows (1, "field"), (1, "field"), (2, "field"), we need to check that some results were not unique and skip them (i.e. second row from example). To fix this:

• we apply technique only for unique indexes, but we need to ensure that all other fields are checked for equality with non-null values. If the ranged queried column has nulls, then I think we can invalidate the prefetching because the order might be altered.
• we apply technique for any arbitrary index, but we need to manually drop the rows that are duplicate on the specific ranged queries field.

With these techniques we can also satisfy AMBIGUOUS construct.

Cache prefetched results¶

After we have the raw data, how do we transfer it in the FWD layer? There should be a smart algorithm here to actually cache them on the right FQL

• add them to FFC, so that the next FindQuery will find it directly there. For this, we need to fabricate a new FQL to update the FFC. For example, we fabricate the following and artificially update the FFC
  • (WHERE tt1.f1 = 2 AND tt2.f2 = "field", UNIQUE) will be mapped to (2, "field")
  • (WHERE tt1.f1 = 3 AND tt2.f2 = "field", UNIQUE) will be mapped to (3, "field")
• With #9078, maybe we can have a different cache per-FIND statement. I tend to like this more as it avoid the overhead of FQL fabrication and stress over FFC. We can simply map the integer values to the right results.

Variance on trailing field within index¶

The variance should happen on f2, so that we fetch a contiguous segment from the (f1, f2) index:

repeat <clause>:
   find tt1 where tt1.f1 = 1 and tt1.f2 = i no-error.
   ...
end.

In the example provided, pre-fetching using select * from tt1 where ? <= tt1.f1 and tt1.f2 = "field" order by tt1.f1 limit ? may be slow as the index doesn't properly match the where clause here. Still, it may be faster than actually emitting queries one-by-one - this shall be investigated.

Locking¶

I am not sure if this technique is suitable for SHARE-LOCK or EXCLUSIVE-LOCK. We may prefetch locked records and the stale data retrieved should not be used. We can use this technique for NO-LOCK initially.

Dirty-share¶

Some data from persistent database may be stale and the absolute right data is in fact in memory. Prefetching shall invalidate if there is dirty data on that table. Ideally, #8388 will mitigate this.

Conclusion¶

• the analysis should be run-time and only assess FIND (FIRST, LAST, UNIQUE) with NO-LOCK that have a conjuction of equalities in the WHERE clause over all fields of an index (not necessary UNIQUE)
  • the table in question should not have info in dirty-share
  • I am open to suggestions here: what if WHERE has other clauses for non-indexed fields? what if WHERE has OR? I think too complex WHEREs shall not prefetch.
• there should be a good identification of this sequential pattern:
  • should be pessimistic not to trigger it for any arbitrary FIND, but only for the ones we know that already fetched the record for i - 1
  • I am open to suggestions here: other triggers for prefetching?
• prefetching actually means emitting a similar query with a bigger LIMIT and range query for the dynamic clause applied to the tailing index field
  • This shall be analyzed, because arbitrary range queries on other index components may be slower
• the duplicates in the result-set should be assessed in a way or another
  • For UNIQUE we need to report AMBIGUOUS
  • For FIRST/LAST, I suspect we can results the duplicated easily.
  • I am open to suggestions here: how to deal with NULL
• the results shall be cached
  • added to the FFC under a fabricated FQL
  • at FIND instance level as a custom "lookahead" cache.
  • I am open to suggestions here: better way to cache the results.

I think #9078 is more of less a prerequisite of this task.

Before moving further, I think the prototype here has a narrow scope. Artur, can you check if it still satisfied #9802 requirements? (locking, dirty state, type of FIND - FIRST/LAST/UNIQUE, complexity of WHERE, uniqueness of index, etc.)

I finished a prototype implementation, it detects when a find unique query is being iterated, meaning that the same statement is being executed but with incremental parameters, then prefetches synchronously batches of records that are likely to be fetched in the future, similarly to how progressive results fetch brackets of records.
The testing on test cases and a customer project showed that the overhead of sequential query execution detection and batching is too high for the approach to be viable, I got similar times as trunk (at best). I no longer think that runtime detection is the way to go, maybe we need to explore conversion time detection, the challenge is to detect deeply nested finds and identify when two queries are the same.

We could detect at runtime and record hints based on this. Those hints could then change how we convert.