FWD » Core Development » Database

Problem¶

A pattern was detected in a customer application that uses a browsed query, which is automatically scrolling. There is a functionality to insert records in the queried table, and as the query is not preselect, the new record should be visibile in the query. To satisfy this, FWD generated an AdaptiveQuery that gets invalidated into an RandomAcessQuery which retrieves records one-by-one. The query can get revalidated if the sort band condition is satisfied: the current first indexed field value is strictly greater than reference record's first indexed field value. The scenario repositions the query to the newly created record; if the record is very far according to the index order, the query should basically go through almost all records.

In the customer application, the index has 2 columns A and B, but the first one (i.e. A) is not segregating the records very much: there may be 25k records for one single value of A. This means that the revalidation won't occur for ~25k next() calls, especially when the created record is at the very end.

Due to recent changes in RandomAccessQuery.next() that functionality impact invalidated AdaptiveQuery, the SQL query:

• properly considers range query like user.name > "test", which now is null safe.
• uses coalesce to properly consider null values on next():
  

  (coalesce(upper(rtrim(user.name)) = upper('test'), not (upper(rtrim(user.name)) = upper(rtrim(user.name))), coalesce('test') is null))

• appends a trailing user.recid asc condition in the ORDER BY even for unique indexes to properly consider records that have null on indexed columns

The combination of these changes and sometimes even only one of them is severly downgrading the performance:

• the coalesce construct is very opaque to the planner and causes table scans to be used. I attempted to replace it with OR and got better results, but not impressively faster.
  • even with OR, the small LIMIT seems to spoil the planner as it optimistically goes for a table scan to find the very first record matching the filter. Removing the LIMIT (or using LIMIT 100) is triggering a Bitmap OR plan that runs in <1ms.
• the trailing recid is rulling out the ORDER BY + LIMIT optimization as the ORDER BY fields are not completely satisfied by an index anymore.

One RAQ.next may now take >10ms instead of <1ms. Because this RAQ is used to satisfy the goal of an AdaptiveQuery, its next may be executed 25k times, leading to >4mins of execution vs a couple of seconds.

I attempted to optimize this or create heuristics, but I must admit that a null-safe RAQ is a real pain to the PostgreSQL planner in any form. The fact that ? in 4GL has slightly different semantics than NULL in SQL causes queries to be bloated with OR or COALESCE constructs to inject IS NULL checks. Lastly, the trailing recid is a must to be functionally accurate.

Solution¶

I designed a general solution for invalidated AdaptiveQuery that is a bit more optimistic than RAQ. I call it LookAheadQuery and will be an internal FWD query used only by the invalidated AdaptiveQuery. Thus, the DynamicResults of the adaptive query will delegate the dynamic work to LookAheadQuery instead of RandomAccessQuery.

Design¶

The core principle that drives the implementation is the combination of FQLBundle with ProgressiveResults. The idea of FQLBundle is to generate several FQL queries that can satisfy the next operation in regard to a referenceRecord. Executed in the right order, they will provide the "next" record: either with all indexed field equal, but greater recid or with a prefix of the indexed fields that are equal, but the next is greater, etc. For the customer scenario that has an index (A, B), the bundle contains:

• A = ? and B = ? and recid > ? (executed 25k times in the customer scenario)
  • >10ms in the customer scenario due to table scan / each execution
• A = ? and B > ? (executed 25k times in the customer scenario)
  • >10ms in the customer scenario due to table scan / each execution
• A > ? (executed once in the customer scenario)
  Note that ? are the query parameters filled with the indexed fields of the referenceRecord, relative to which the NEXT is fired. Also, for brevity, I omitted the null-safe checks.

Combining these queries with a ProgressiveResults will end up calling each bundled query only a logarithmic number of times. In trunk, the statements are executed one-by-one as the dynamic mode is pessimistic. An optimistic approach will gather results in incrementally larger buckets.

• A = ? and B = ? and recid > ? (to be executed once in LookAheadQuery)
  • expected: >10ms similar customer scenario due to table scan / each execution
• A = ? and B > ? (to be executed ~6 times in LookAheadQuery)
  • expected for first bucket is >10ms similar customer scenario due to table scan / each execution
  • if OR is used instead of COALESCE, then the expected for other buckets: <1ms according to testing due to Bitmap OR plan; otherwise, it will be >10ms as well
• A > ? (to be executed once in LookAheadQuery)

The rough approximation of the timing with the LookAheadQuery is between 30ms (if using OR) and 100ms (if using COALESCE), instead of 4mins with current trunk.

Multiple invalidations¶

Evidently, the idea arose from the initial quite specific problem. The solution is for general cases. However, there is a case that makes LookAheadQuery a bit vulnerable: multiple invalidations.

If the scenario is invalidating the query again, then the ProgressiveResults extracted becomes stale, which means that the query is no longer able to satisfy its duty. In this case, the LookAheadQuery should invalidate. This shouldn't be a complex operation; the existing LookAheadQuery can simply drop its results, set its new referenceRecord and restart from the most specific FQL from the bundle. The "looked-ahead" results would have been brought to the session without reason, so this was a time price payed for nothing.

Dirty-share¶

The only query that honors the cross-/intra- session dirty share functionality is the RAQ. If there is an operation of the dirty database, then the AdaptiveQuery is invalidated to use RandomAccessQuery. Even before any operation is attempted on the query, earlyInvalidate can decide whether the query should always stay in dynamic-mode to honor the dirty-share.

I need to check how to integrate this into LookAheadQuery. I am thinking that an invalidation caused by dirty-share should always force a RAQ delegate, so that LookAheadQuery will be a "clean" implementation that awaits for #8388 (intra-) or is simply unusable with cross-session dirty share functionality.

Revalidation¶

There is no point in "revalidating" if a LookAheadQuery delegate for dynamic-mode is used. Technically, if the sort band is bypassed, then LookAheadQuery won't honor the fql bundle anymore and will basically continue to operate exactly like a revalidated AdaptiveQuery. Once an AdaptiveQuery is invalidated, it will stay like that with an LookAheadQuery as its results delegate.

Currently, we also have a maximum number of revalidations per query to avoid "thrashing". I don't think this is relevant with LookAheadQuery as the number of revalidations will be technically 0.

Can it be worse than trunk's RAQ?¶

Technically, if the LookAheadQuery is invalidated after each extracted record, then the query would behave exactly like a RAQ. The ProgressiveResults starts with bucket 0 (LIMIT 1), so it emits the same SQL as the RAQ. If the invalidation occurs, then the ProgressiveResults will be recreated, so the query restarts from bucket 0 (LIMIT 1) - very similar to RAQ.

If the records get invalidated in a strategical manner (one every two records), then LookAheadQuery timing is quite interesting to analyze.

• two records to be fetched means two buckets to be retrieved, which means roughtly 11 records (first brought by LIMIT 1 and the others brought by a LIMIT 10 OFFSET 1 query). RAQ would get only 2 records with two queries, so it is faster as it won't uselessly bring other 9 records from the DB.
• however, after testing, LIMIT 7 seems to be a breakpoint from which PG prefers to use Bitmap OR instead of Table Scan (if OR is used instead of COALESCE). So the second bucket which has LIMIT 10 will actually work way faster (< 1ms) than the second RAQ.next execution, which takes >10ms.
• if we still stick to COALESCE, then this stategically picked scenario may be less performant than RAQ's one-by-one retrieval. But from my POV, the whole goal of ProgressiveResults is to minimize such drawbacks and lose time as less as possible for weird scenarios.

I may agree that LIMIT 7 looks like a total random construct and most probably is generated by ANALYZE metrics, but there is certainly a disposition to use the more efficient Bitmap OR on larger result sets, which can be stimulated by ProgressiveResults. If it is not for the second bracket, than the third/forth/etc. brackets will benefit from this beneficial plan switch.

Please review the idea and design; I will attempt to prototype LookAheadQuery in the mean-time

Alexandru Lungu wrote:

...
There is no point in "revalidating" if a LookAheadQuery delegate for dynamic-mode is used.
...
if the LookAheadQuery is invalidated after each extracted record, then the query would behave exactly like a RAQ
...

The whole point is to avoid revalidating, I don't think the problem mentioned will be the only scenario where the LookAheadResults can be used, but I am intrigued by your PG findings and I remembered that I have stumbled across a "fake" infinite loop in another customer application that uses MariaDB (but keep in mind that it is a totally different problem) that might benefit from this. I agree with your idea and design as mentioned in #9755-1 and the simplification from #9755-4.