FWD » Core Development » Database

This is deferred work from #8495 and refers to the replacement of expr1 begins expr2 with expr1 >= low_bound and expr1 < lowbound + 1 (pseudo-code used). There are some conditions that should be accounted for like expr1 should be indexed or stuff like that. In #8495, this optimization proved to drastically improve time, because it didn't use the slow begins UDF anymore. The customer applied the change manually to their legacy code, but the goal of this task is to improve FqlPreprocessor in FWD to automatically apply this optimization, when possible.

The conversion of a simple find first tt where tt.f1 begins tst yields:

 new FindQuery(tt, "upper(tt.f1) like ?", null, "tt.f1 asc", new Object[]
         {
            toUpperCase(convertToSQLBegins(tst))
         }, LockType.NONE).silentFirst();

The actual SQL has (upper(tt_1_1__im0_.f1) like ?) clause. At plan time, PG doesn't know this is a "prefix" and most probably it will plan it as a seq-scan. The parameter is indeed like "abc%", but PG finds out that too late. I wonder if we should rather inline the parameter if used for begins. I think it is always sub-optimal to favor parsing and planning time with a prepared statement at the cost of not knowing this is a "prefix" search.

• if the pattern is tt.f1 like ?, then we should inline
• if the pattern is tt.f1 line <expr> then better solutions are needed (maybe the one from #8495).

Alexandru Lungu wrote:

The conversion of a simple find first tt where tt.f1 begins tst yields:
[...]

The actual SQL has (upper(tt_1_1__im0_.f1) like ?) clause. At plan time, PG doesn't know this is a "prefix" and most probably it will plan it as a seq-scan. [...]

Don't we need this to be (upper(rtrim(tt_1_1__im0_.f1)) in order to give the database a chance to match an index? At least, for dialects which compose indices using upper(rtrim(...)).

I was a bit puzzled why isn't BEGIN implemented as an UDF?
I mean that was my first reaction, to see how udf.begins(a text, b text) (for PSQL) is implemented and whether it can be improved.
I am thinking also of constructs like

find first tt where tt.f1 begins tt.f2

find first tt where tst begins tt.f2

So I assume the UDF performance has already been explored. Right?

Don't we need this to be (upper(rtrim(tt_1_1__im0_.f1)) in order to give the database a chance to match an index? At least, for dialects which compose indices using upper(rtrim(...)).

You are right. However, I tested now some SQLs in PgAdmin4 and both upper(f1) like 'ABC%' and upper(rtrim(f1)) like 'ABC%' use the scan index. upper(rtrim(f1)) like 'ABC' uses the scan index and upper(f1) like 'ABC' doesn't. I agree however that this is a conversion bug.

Interestingly is also that find first tt where tt.f1 = 'ABC' converts to new FindQuery(pt, "upper(pt.f1) = 'ABC'", null, "pt.f1 asc").first(); without rtrim. Something is not right .... Is the rtrim added at run-time?

So I assume the UDF performance has already been explored. Right?

Not yet, but I doubt the planner will resolve the UDF to an index scan. I think the UDF are quite opaque to the planner and if it simply plans where udf.begins(tt.f1, "abc"), then it will most probably say that this is a seq scan as it doesn't know the range properties of begins in regard to the b-tree. It seems it doesn't even know to resolve "like 'abc%'" for that matter :)

Alexandru Lungu wrote:

Don't we need this to be (upper(rtrim(tt_1_1__im0_.f1)) in order to give the database a chance to match an index? At least, for dialects which compose indices using upper(rtrim(...)).

You are right. However, I tested now some SQLs in PgAdmin4 and both upper(f1) like 'ABC%' and upper(rtrim(f1)) like 'ABC%' use the scan index. upper(rtrim(f1)) like 'ABC' uses the scan index and upper(f1) like 'ABC' doesn't. I agree however that this is a conversion bug.

I assume from these mixed results that you are testing this on an analyzed table with a lot of data. The PostgreSQL query planner will sometimes decide a table scan is faster for a table with few rows, or if it decides the table statistics call for that plan. It also considers the various cost settings, which can be configured in postgresql.conf, though I've never changed these from the defaults myself. That being said, I don't know the details of this algorithm.

I don't know how other database implementations come up with their query plans, but I expect there are similar considerations in their algorithms.

All this is to say that we have to test with a typical (I know that's vague) data set to be able to safely draw conclusions about the query planner's decisions. By "typical", I suppose that means a lot of rows with a good distribution of values for the columns we are using.

Interestingly is also that find first tt where tt.f1 = 'ABC' converts to new FindQuery(pt, "upper(pt.f1) = 'ABC'", null, "pt.f1 asc").first(); without rtrim. Something is not right .... Is the rtrim added at run-time?

Yes, it is injected by FQLPreprocessor if needed.

BTW, I've considered the idea of doing the same with upper, instead of emitting it during conversion, depending on whether the target field is case-insensitive or not. But, we would have to be consistent and do the same with the opposite operand, which often is a substitution parameter, but can be a more complex expression. In the end, it would have meant doing a lot of the same work at runtime we currently do during conversion. What prevented me from going down this path was a combination of inertia and a concern for hurting runtime performance.

So I assume the UDF performance has already been explored. Right?

Not yet, but I doubt the planner will resolve the UDF to an index scan. I think the UDF are quite opaque to the planner and if it simply plans where udf.begins(tt.f1, "abc"), then it will most probably say that this is a seq scan as it doesn't know the range properties of begins in regard to the b-tree. It seems it doesn't even know to resolve "like 'abc%'" for that matter :)

Whether or not the UDF would be opaque I believe depends on the language used and the complexity of the UDF implementation.

A simple UDF implemented with pure SQL (as opposed to a procedure language) has better odds of being properly analyzed by a query planner, but it depends on a database's query planner implementation.

I agree that the odds of a good query plan generally are better if the query can be expressed with simple operands and operators, instead of a UDF. If we do use a UDF, this will require a lot more testing across dialects to ensure we are getting good query plans. If we can avoid a UDF and get the correct functional behavior with native operators, I think that is the way to go.

I assume from these mixed results that you are testing this on an analyzed table with a lot of data. The PostgreSQL query planner will sometimes decide a table scan is faster for a table with few rows, or if it decides the table statistics call for that plan. It also considers the various cost settings, which can be configured in postgresql.conf, though I've never changed these from the defaults myself. That being said, I don't know the details of this algorithm.

I was running on #9690 analyzed table with 3.5k rows. I can't say this is "a lot of data", but enough to separate a table scan from an index scan.
I can agree that planning can be different according to index selectivity and other statistics analyzed.

Yes, it is injected by FQLPreprocessor if needed.

Huh, dodged a bullet here. I really though we messed up with this. Just checked today morning and indeed, SQL queries end up having rtrim injected.

After a super-fast internet search, it seems like text datatype we choose for character legacy fields uses a default operator class that is limited in terms of planning with LIKE.

According to https://www.postgresql.org/docs/current/indexes-opclass.html

• text_pattern_ops is an operator class that can be set per-field in index and so it organizes the data to satisfy LIKE queries faster. I did such attempt and indeed, LIKE 'A%' is using that index with text_pattern_ops field.

However, there is the following note:

The difference from the default operator classes is that the values are compared strictly character by character rather than according to the locale-specific collation rules.

But at the same time:

If you do use the C locale, you do not need the xxx_pattern_ops operator classes, because an index with the default operator class is usable for pattern-matching queries in the C locale.

Finally, inside https://www.postgresql.org/docs/current/locale.html

The locale settings influence the following SQL features: 
*   [...]
*   The ability to use indexes with LIKE clauses
The drawback of using locales other than C or POSIX in PostgreSQL is its performance impact. It slows character handling and prevents ordinary indexes from being used by LIKE. For this reason use locales only if you actually need them.

This is getting messy. The database I was testing with used a custom fwd_basic locale flavor (installed using the FWD guide). With such, pattern-matching queries aren't using the indexes with default operator class.
I also just tested with an UTF-8 database and guess what: the default operator indeed supports pattern-matching queries!

So I would say that begins constructs that end up as field LIKE 'A%' are going to work fast by default on databases that have C locales (like UTF-8). The workaround exists as documented:

As a workaround to allow PostgreSQL to use indexes with LIKE clauses under a non-C locale, several custom operator classes exist. These allow the creation of an index that performs a strict character-by-character comparison, ignoring locale comparison rules. Refer to Section 11.10 for more information. Another approach is to create indexes using the C collation, as discussed in Section 23.2.

But it has the obvious limitations: the comparison will not be locale sensitive and extra indexes are required (as text_pattern_ops ones do not support =, <, <=, >, >=).

Therefore, I think this task #9305 still stands, but it should be toggled so that customers with DB that use C locale can use the native support for pattern matching.

From #10165:
For temp-table (H2 database), LIKE 'prefix%' does not use an index at the moment. I suspect it is because the BEGINS is turned into something like (upper(tt_1_1__im0_.word) like 'PREFIX%') and H2 does not know how to handle upper(...) in an index.

In H2 the condition is (UPPER(TT_1_1__IM0_.WORD) LIKE CAST('PREFIX%' AS VARCHAR_IGNORECASE))

This case will be fully fixed if we remove the upper(...) call and send only (tt_1_1__im0_.word like 'PREFIX%') as it is already a VARCHAR_IGNORECASE. This way the H2 planner will use this:

    /* PUBLIC.IDX__TT1_IDX_WORD__1: _MULTIPLEX = ?1
        AND WORD >= 'PREFIX'
        AND WORD < 'PREFIY'
     */

Alexandru,
You told yesterday and in #9305-10 that the default database configuration, with en_us.UTF8 collation, the LIKE operator should work. I think the actual configuration that you tested was actually a C or pg_c_utf8 collation, which LIKE operator works by default with B-TREE indexes.
The thing is that there is a configuration on a customer, with en_us.UTF8 and the LIKE operator is slow. en_US.UTF8 is a libc collation, which the LIKE operator will use the sequential scan.

There is pg_unicode_fast, which was introduced in PSQL 18, where the range and LIKE operator will use the index.

Teodor Gorghe wrote:

You told yesterday and in #9305-10 that the default database configuration, with en_us.UTF8 collation, the LIKE operator should work. I think the actual configuration that you tested was actually a C or pg_c_utf8 collation, which LIKE operator works by default with B-TREE indexes.
The thing is that there is a configuration on a customer, with en_us.UTF8 and the LIKE operator is slow. en_US.UTF8 is a libc collation, which the LIKE operator will use the sequential scan.

Indeed with en_us.UTF8 locale on LIKE does not use index scan. I also created a separate index with text_pattern_ops operator class, and this actually helped index usage. Since the duplicating number of indices is not a viable solution, I guess we are left with the #9305-1.

The range check follows the field collation or is byte-by-byte?
If it is after collation, there are some cases like foo-a, which goes before foo. Replacing LIKE with range check will skip foo-a. This is a specific en_US.UTF8 rule, but there are lots of rules in other languages in which the prefix is NOT an interval boundary.

Please do the tests requested in #9305-25 in 4GL and PG with LIKE / < and > / with BETWEEN. We need to take a decision that is functionally sound.

This is one difference between BEGINS and range check, on BASIC collation:

DEFINE TEMP-TABLE tt1 NO-UNDO
    FIELD f1 AS CHARACTER
    INDEX idx1 IS PRIMARY f1.

CREATE tt1. tt1.f1 = "ORD".
CREATE tt1. tt1.f1 = "ORD-123".

FOR EACH tt1 WHERE tt1.f1 BEGINS "ORD ":
    DISPLAY tt1.f1 "BEGINS".
END.

FOR EACH tt1 WHERE tt1.f1 >= "ORD " AND tt1.f1 < "ORE":
    DISPLAY tt1.f1 "RANGE CHECK".
END.

4GL output:

ORD      BEGINS
ORD      RANGE CHECK
ORD-123  RANGE CHECK

FWD output:

ORD      BEGINS
ORD-123  BEGINS
ORD      RANGE CHECK
ORD-123  RANGE CHECK

Something might be wrong at conversion, BEGINS is converted into upper(tt1.f1) like 'ORD%'.
Also, it seems that when using BEGINS, 4GL takes the shorter operand in length and then it appends with spaces to match the length with the other operand. This is why the "ORD" is matched with BEGINS "ORD ".
I will find some other cases where BEGINS and range check is different.

This is another example of RANGE CHECK vs BEGINS, using UTF-8 collation on 4GL:

DEFINE TEMP-TABLE tt1 NO-UNDO
    FIELD f1 AS CHARACTER
    INDEX idx1 IS PRIMARY f1.

CREATE tt1. tt1.f1 = "luna".
CREATE tt1. tt1.f1 = CHR(322, "UTF-8", "UTF-32") + "una".
CREATE tt1. tt1.f1 = "macaw".

DISPLAY 
    "Session Collation: " SESSION:CPCOLL FORMAT "x(20)" SKIP(1)
    WITH FRAME fTop NO-BOX NO-LABELS WIDTH 60.

DISPLAY "--- WHERE f1 >= 'l' AND f1 < 'm' ---" FORMAT "x(40)" 
    WITH FRAME fRange NO-BOX NO-LABELS.

FOR EACH tt1 WHERE f1 >= "l" AND f1 < "m":
    DISPLAY tt1.f1 FORMAT "x(15)" WITH FRAME fBody1 DOWN NO-LABELS.
END.

DISPLAY "--- WHERE f1 BEGINS 'l' ---" FORMAT "x(40)" 
    WITH FRAME fBegins NO-BOX NO-LABELS.

FOR EACH tt1 WHERE f1 BEGINS "l":
    DISPLAY tt1.f1 FORMAT "x(15)" WITH FRAME fBody2 DOWN NO-LABELS.
END.

With UTF-8 basic collation:

RANGE CHECK: luna
BEGINS: luna

With UTF-8 ICU collation:

RANGE CHECK: luna, łuna
BEGINS: luna

Notes:
- if you want to execute this test on 4GL, you need to use the prowin. If you try it from Developer Studio, it will corrupt the łuna string.

I have also noticed that for Western characters, there is no difference between BASIC and ICU-UCA on RANGE CHECK/BEGINS.

I think this is due to the fact that long ago, there were no ICU-UCA implementation. Since some of Progress 4GL users are from Western Europe, they have implemented some sort of support for western characters like ß in the BASIC collation.

I have also tested the difference between LIKE and RANGE CHECK on PSQL.

When the libc collation provider is being used, there is no difference between LIKE and RANGE CHECK.

When the collation provider ICU is used, there are some differences, but it depends on the ICU rules.
I have tested with Polish rules and I see that the LIKE operator displays luna, but the range check displays both luna and łuna.
The surprise for me is that the English United States ICU rules displays the same results as when using the Polish ones.

PS: Of course, this would be a PG only fix.

Using starts_with instead of like operator might improve the performance, but please mind that we need to fully support BEGINS operator in the future, which pinpoints directly to #9305-22. In short terms, 4GL extends each character field to the according format and then uses BEGINS operator.

I added Stefanel as assignee to relate with #5219 work and whether there are certain things we can do in PG to improve this BEGINS saga. We need to fully understand what 4GL does behind the scenes for BEGINS (collation-wise, formatting, case-insensitive, etc.) and try to match that in PG within the most performant solution. The urgency of this rises as this occurred already at 2 in-production customers and potentially in #11686. It is common to have a "search fill-in" that does a BEGINS to search for records that begin with the input.

However, please also consider that most customers ported their single-byte databases to UTF-8 collation databases and accepted mismatches that could occur functionally along the way (e.g. sorting of data). Thus, we also need to hunt a solution that makes "most sense" for UTF-8 migrated customers (is fast and it works). Greg/Eric, please correct me on this point otherwise.

In short terms, 4GL extends each character field to the according format and then uses BEGINS operator.

The range check / interval based conditional was an work-around. The more I think about it, the less confident I am that it is a good solution. I really can't belive that we can't make PG (at least) be fast with a BEGINS counter-part. I understand that LIKE "probe%" is not indexed under certain collations, but how does a modern application manages to implement such functionality fast. I can't take "it can't" as an answer. If it is about special indexes, then lets have special indexes emitted (e.g. detect at conversion time BEGINS clauses in reports, use schema hints, use run-time statistics to identify tables that are target to BEGINS, etc.). But if there is a quick win like starts_with or ^@ operator, then lets go for the quick win.

I have a doubt that starts_with works for simple collations like C, but it may not work for libc collations.

#11686 is confirmed to be related to this BEGINS task.

However, please also consider that most customers ported their single-byte databases to UTF-8 collation databases

Some have but not more than half. When running with UTF-8, our objective is to be compatible with OE running UTF-8. I don't want us to add special cases or quick fixes that break full compatibility.

The customer expectation is that if they run on both OE and FWD with UTF-8, that it will work the same way.

Let's focus on testcases. These need to be designed to test the results across multiple encodings.

As I found out in #5219 also, in an indexed field an accented character is considered equal to the normal one.
The below report is aggregated with AI assistance, but I took time to upgrade my posgresql to a newer version and to make sure the results are as accurate as possible, but still may contain wrong information.

OpenEdge does not agree with itself. The same BEGINS answers differently depending on whether an index serves it — on 17 of 34 patterns. There are two baselines, and a form can only imitate one.

The indexed route is a window opened over the index and handed back unfiltered: always a superset of the operator, never smaller. The extras are whatever the collation ties to the pattern — äbc and Äbc for BEGINS "abc", ssx for BEGINS "ß", the empty value for a blank pattern.

Output fidelity¶

What is being compared¶

41 values and 34 patterns, chosen so every rule BEGINS obeys has a value only that rule explains — case pairs, accents against their base letter, sharp-s against ss, blanks and the empty value, % and _ as ordinary data, a tab, a tilde. The forty-first value is unknown and no pattern reaches it on either engine.

OpenEdge answers each pattern twice, indexed and unindexed. Those 68 answers are the ground truth, re-measured on OpenEdge 12.8 (cpcoll=Basic, cpinternal=ISO8859-1) for this report and reproducing the stored baselines 68 of 68.

PostgreSQL gets the operand FWD would give it, built in Java before any SQL exists — toUpperCase(convertToSQLBegins(rightTrim(pat))) — so what separates the forms is the form and the collation, nothing else.

Measured on PostgreSQL 14.24 and again on 17.11. All 1 020 cells — six collations, five forms, 34 patterns — are identical. Nothing in this chapter depends on the server version.

The scores, under the collation FWD deploys¶

Out of 34 patterns, on en_US@iso88591_fwd_basic. Latin-1 and UTF-8 score identically.

Every form that keeps the LIKE returns the same row ids FWD returns today, on all 34 patterns. A range changes the plan, not the answer — the LIKE stays in the predicate and re-checks whatever the bracket collected. PostgreSQL always re-checks, which is also why no form here can reproduce OpenEdge's unfiltered bracket. Confirmed at scale on the million-row table: every one- and two-character prefix present in the data, 702 of them against 20 001 distinct keys, zero disagreements.

The last row is the shape a careless range rewrite would take. Two bounds close the window:

The code-point bound sweeps in the accented rows — closer to OpenEdge's index bracket, hence 21 against it rather than 16, but wrong on eight patterns more than the LIKE is. Pairing it with the LIKE removes the extras and returns it to 29.

Where FWD is wrong today¶

Five patterns, none of them about indexes, ranges or collations. Every form above fails them identically.

Two bugs. The pattern is right-trimmed and the value is not, so blanks stop being comparable. And the pattern is uppercased by Java while the column is uppercased by PostgreSQL, which disagree wherever a character has no one-to-one uppercase. Both are independent of the index question.

Collation¶

The collation changes results, not only speed. Same 34 patterns, scored against the OpenEdge operator, on the UTF-8 databases.

C is not output-neutral. Its LC_CTYPE leaves accents alone, so upper('äbc') comes back unchanged while the pattern is already 'Äbc'. Four more patterns break than under FWD's collation (ä, Ä, ç, é), taking LIKE from 29 to 25. Switching to C so the existing index can serve LIKE buys the index with silently wrong results on accented data.

Standard en_US admits no exact range bound. Its accents tie with the base letter, so the next distinct weight after A is b — a window from A runs all the way to b and takes every a-led value with it. Hence 9 of 34 for a bare range. Paired with the LIKE it is correct again at 30 of 34; what it loses is selectivity, not correctness.

A code-point bound is not always above the rows it bounds. Incrementing the last character gives a string larger by code point, which under a linguistic collation need not be larger at all: BEGINS "z" becomes >= 'Z' and < '[', and en_US sorts [ before the letters — empty window, row lost. Likewise BEGINS "a_" (_ to `) and BEGINS "9" (9 to :). Twelve patterns lose rows this way, taking range + LIKE to 18 of 34, and the LIKE cannot rescue them: it removes rows the range collected, it cannot restore rows the range skipped. A bound must be derived from the collation in force.

Encoding matters on exactly one pattern. BEGINS "ÿ" uppercases to Ÿ, which Latin-1 cannot represent — the Latin-1 database rejects the statement, the UTF-8 one quietly returns nothing. Under standard en_US on UTF-8 the pattern works, because glibc uppercases the column's ÿ the same way Java uppercased the pattern; that single cell is the whole 30-versus-29 difference above. On the FWD collation and on C the two encodings score the same.

Performance¶

Retrieval shapes¶

FWD is fast only where the prefix sits at the end of the index it walks from — FIND FIRST on a front prefix, FIND LAST on a back prefix. At the other end it costs 134 ms, walking the index from the wrong end and filtering. The range holds up on every early-exit shape; adding the LIKE gives that back, landing near 0.53 ms alongside text_pattern_ops.

Selectivity¶

Index covering three fields¶

^@ and starts_with()¶

The one place the PostgreSQL version matters. Each cell reads PostgreSQL 14 / 17.

On 14 starts_with has no prosupport entry, so nothing rewrites the call into an index bracket; on 17 it carries text_starts_with_support. ^@ on SP-GiST worked on 14 through the operator family rather than a rewrite. In throughput: 54 queries/sec rising to 19 382. Whether 15 or 16 introduced the support function was not tested — neither is installed here.

Neither operator can use the index FWD builds, on either version. Both need text_pattern_ops or SP-GiST, exactly as LIKE does. PostgreSQL 17 adds spellings, not index options.

One caveat on the timings above: PostgreSQL 17 chooses a parallel scan where 14 chose a plain one, which halves every S cell. With parallelism disabled the two versions are within one percent of each other, and at eight concurrent clients FWD measures 62 queries/sec on both. The upgrade spends more cores on the same work; it does not make BEGINS cheaper.

I read #9305-36. The output seems useful but I found it hard to assess much of what was related. It uses quite a bit of jargon (terms that are undefined in this task), it doesn't map the results to example code in a way that is obvious, there are a lot of references to indexes and forms without really explaining what those are and how they relate to the problem; even the problem being analyzed is not well defined. Please provide much more context for us to allow for better comprehension.

From what I understand, if we want to keep using `LIKE`, or switch to `starts_with`, we still need either a supporting collation or an index using `text_pattern_ops`. So, I guess we could detect any columns/tables that would need such special index, like Alex mentioned.

If it is about special indexes, then lets have special indexes emitted (e.g. detect at conversion time BEGINS clauses in reports, use schema hints, use run-time statistics to identify tables that are target to BEGINS, etc.).

The `range` option would be the quickest win. We could also use a `range` with a wider window and then filter out the remaining outliers with an `and LIKE ` condition, e.g. `(upper(col) >= 'ZZ' AND upper(col) < bound AND upper(col) LIKE 'ZZ%')`.

I read #9305-36. The output seems useful but I found it hard to assess much of what was related. It uses quite a bit of jargon (terms that are undefined in this task), it doesn't map the results to example code in a way that is obvious, there are a lot of references to indexes and forms without really explaining what those are and how they relate to the problem; even the problem being analyzed is not well defined. Please provide much more context for us to allow for better comprehension.

I actually trimmed and rewrote a lot of the information that I felt wasn’t useful. Here’s a more detailed report:

FOR EACH item NO-LOCK WHERE item.itemName BEGINS "abc":

OpenEdge answers it from an index. FWD reads the whole table:

Parallel Seq Scan on item
  Filter: (upper(rtrim(item_name)) ~~ 'ABC%'::text)

999 900 of the million rows are read and discarded to return 100. That is 36.3 ms instead of 0.085 ms, 9 346 disk pages instead of 6, and 62 queries/sec instead of 64 158 at eight clients. The cost tracks how many rows exist, not how many match, so it does not improve as the search narrows.

How that statement becomes SQL — the full chainHow that statement becomes SQL — the full chain

FOR EACH item NO-LOCK WHERE item.itemName BEGINS "abc":

query.initialize(item, "upper(item.itemName) like ?", null, "item.itemName asc",
                 new Object[] { toUpperCase(convertToSQLBegins(rightTrim(pat))) },
                 LockType.NONE);

select ... from item where upper(item_name) like 'ABC%'

Finalize Aggregate
  ->  Gather
        Workers Planned: 2
        ->  Parallel Seq Scan on item (actual rows=33 loops=3)
              Filter: (upper(rtrim((item_name)::text)) ~~ 'ABC%'::text)
              Rows Removed by Filter: 333300

Why the index is not used¶

Conversion emits upper(col) like 'ABC%' against an expression index (upper(rtrim(col)), recid). PostgreSQL can rewrite a prefix LIKE into an index range, but only where that is provably correct: the index collation must be C/POSIX, or the index must use a *_pattern_ops operator class.

Which index this isand why it meets neither condition

ADD INDEX "name" ON "item" 
  INDEX-FIELD "itemName" ASCENDING

CREATE INDEX idx__item_name ON item USING btree (upper(rtrim(item_name)), recid)

The options¶

All four return the same rows. They differ in what the planner can do and what they cost to adopt.

The two operator forms need a second index on the same expression with the text_pattern_ops opclass — the same index a LIKE would need — so they add nothing LIKE could not already have, and before PostgreSQL 17 they are not bracketed at all.

The same query in each formwith the plan each one gets

select count(*) from item where upper(rtrim(item_name)) like 'ABC%'

  ->  Parallel Seq Scan on item (actual rows=33 loops=3)
        Filter: (upper(rtrim((item_name)::text)) ~~ 'ABC%'::text)
        Rows Removed by Filter: 333300

select count(*) from item
 where upper(rtrim(item_name)) >= 'ABC'
   and upper(rtrim(item_name)) <  'ABÇ'

  ->  Bitmap Heap Scan on item (actual rows=100 loops=1)
        Heap Blocks: exact=3
        ->  Bitmap Index Scan on idx__item_name (actual rows=100 loops=1)
              Index Cond: ((upper(rtrim((item_name)::text)) >= 'ABC'::text)
                       AND (upper(rtrim((item_name)::text)) <  'ABÇ'::text))

create index idx__item_name_po on item (upper(rtrim(item_name)) text_pattern_ops, recid);
select count(*) from item where upper(rtrim(item_name)) like 'ABC%'

  ->  Index Scan using idx__item_name_po on item (actual rows=100 loops=1)
        Index Cond: ((upper(rtrim((item_name)::text)) ~>=~ 'ABC'::text)
                 AND (upper(rtrim((item_name)::text)) ~<~ 'ABD'::text))
        Filter: (upper(rtrim((item_name)::text)) ~~ 'ABC%'::text)

select count(*) from item where starts_with(upper(rtrim(item_name)), 'ABC')

  ->  Index Scan using idx__item_name_po on item (actual rows=100 loops=1)
        Index Cond: ((upper(rtrim((item_name)::text)) ~>=~ 'ABC'::text)
                 AND (upper(rtrim((item_name)::text)) ~<~ 'ABD'::text))
        Filter: starts_with(upper(rtrim((item_name)::text)), 'ABC'::text)

Recommendation¶

Emit the range, with the upper bound derived from the collation. It is the only option that works with the index FWD already builds, on the PostgreSQL version already deployed.

The range is also the only form that keeps FIND FIRST and FIND LAST fast, because it is the only one the planner can serve with an ordered index scan that stops at the first row.

Two conditions on it¶

The bound must come from the collation, never from incrementing the last character. BEGINS "z" would become >= 'Z' and < '[', and standard en_US sorts [ before the letters — empty window, row silently lost. That mistake costs 12 of the 34 patterns.

The rewrite is safe under the collation FWD deploys, not under every collation. Under a standard en_US collation the accents tie with the base letter, so a window from A must run all the way to b and a bare range scores 9 of 34.

Reading the two OpenEdge columns in #9305-36¶

/* A: an index serves the predicate */
FOR EACH item NO-LOCK WHERE item.itemName BEGINS "abc":

/* B: index bypassed, so the operator runs per row */
FOR EACH item NO-LOCK USE-INDEX pk:
   IF item.itemName BEGINS "abc" THEN ...

With abc, ABC, Abc, äbc, Äbc in the table, A returns five rows, B returns three. A brackets the index over collation weights — where ä weighs the same as a — and returns that window as its answer; B compares characters and keeps the distinction. They disagree on 17 of the 34 patterns. This is the #5219 observation.

FWD reproduces B — which is also what OpenEdge itself gives whenever no index serves the query.

"28 of 34" in those tables means 28 of the 34 fixed patterns returned exactly OpenEdge's rows. #36 prints 29 for that figure; 28 is the corrected value, because FWD's rightTrim strips a trailing tab as well as trailing blanks and so breaks one pattern more than I had modelled. S marks a plan that read the whole table. Times are milliseconds, best of five warm runs.

Thank you, that is very helpful.

In regard to the "two conditions": if the WHERE clause needs to be rewritten based on the collation, then I think this must be done at runtime since converted code can be used with multiple collations. Is that the idea?

Do any of the 3 solutions deliver a more complete solution? From a functional perspective, are there limitations on the 4GL compatibility of these options?

Considering that the PostgreSQL planner for LIKE with text_pattern_ops already does something similar to a range + LIKE:

Index Cond: ((upper(rtrim((item_name)::text)) ~>=~ 'ABC'::text)
                 AND (upper(rtrim((item_name)::text)) ~<~ 'ABD'::text))
        Filter: (upper(rtrim((item_name)::text)) ~~ 'ABC%'::text)

In task branch 9305a revision 16704 I committed the first stable iteration of begins rewrite to range.
This should not regress trunk, but also fixes some other edgecases.
I'm currently in the process of validating and fixing some points from the AI self-review.
The changes work well for most cases, but some edge cases are still failing, including some issues related to handling patterns with trailing spaces.

This is how it currently works:

Every indexed BEGINS was a sequential scan¶

Trunk emits upper(name) like 'AB%'. The functional index Postgres builds for a case-insensitive character field is on expression upper(rtrim("name"::text)), but Postgres will only satisfy LIKE 'prefix%' from a btree created with text_pattern_ops. I think that using text_pattern_ops has more limitations than the flexibility offered by the range implementation.

9305a brackets the same expression as a range, which the existing index does serve:

trunk:  upper(name) like 'AB%'
9305a:  (upper(rtrim(name)) >= upper('ab') and upper(rtrim(name)) <= udf.upper_bound(upper('ab')))

(upper(rtrim(name)) >= upper('ab') and upper(rtrim(name)) <= udf.upper_bound(upper('ab'))) and upper(name) LIKE upper('ab%')

Case folding in the JVM disagreed with the folding in the database¶

Trunk folds the operand with Java toUpperCase() while the column side folds with SQL upper(). The two are not the same function: Java expands ß to SS, Postgres upper() leaves it alone.

name BEGINS "straße"     trunk:  upper(name) like 'STRASSE%'
                         column: upper('Straße') = 'STRAßE'   → no rows, ever
                         9305a:  upper(name) like upper('straße')

9305a stops folding BEGINS operands in the JVM (expressions.rules, where_clause.rules) and emits upper(...) in SQL instead, so both sides fold with the same function.

A pattern ending in the escape character crashed¶

convertToSQLLike(String, boolean, boolean) and convertToRegEx(String, boolean)+ 1)@ with no bounds check:

name MATCHES "ab~"       trunk: StringIndexOutOfBoundsException
                         9305a: escape discarded → 'AB%'  (Progress behaviour)

The same crash occurred for a trailing \ on non-Windows, where the backslash falls through to the '~' case.

An escaped tilde lost its tilde¶

The inner look-ahead switch consumed only * and ., so both tildes of ~~ were treated as escapes and dropped:

name MATCHES "a~~b"      trunk: 'AB%'    -- tilde vanished
                         9305a: 'A~B%'   -- escaped tilde is a literal tilde

The upper bound of the range used for BEGINS implementation will be computed directly in PSQL while running udfs.sql and is based on the collation order the database uses.

In 9305a rev. 16729 I have rewritten how the query gets converted from begins to a range bound. It's a little bit simpler than the previous revisions.

Thanks for the extensive review. I’ll take some time to go through all the details. The UDF part is one of the areas that changed quite a bit from commit to commit, as I was experimenting with different approaches along the way.

I rebase 9305a to trunk/16735 and fixed some review points in revision 16741.

I need to investigate the other collations next and look into how the UDF can be improved. I also need to revisit the isSimplePrefix() logic. Using this guard to drop the LIKE filter fixed some of my unit tests.

Committed some more changes in rev 16742. Currently I'm working to generate more unit tests to cover more cases. The UDF changes are still experimental.

Is there any chance of having this ready for merge next week?

Please do a final review of 9305a. And let me know if you want me to test anything else.

Doing it now.

Stefanel, I think there are files not committed yet:

> Task :compileJava
/media/al2/kiwi1/claude/9305a/src/com/goldencode/p2j/persist/dialect/H2Helper.java:313: error: cannot find symbol
      BeginsSupport.setCollationOrder(next, greatest.repeat(CEILING_PAD));
      ^
  symbol:   variable BeginsSupport
  location: class H2Helper
/media/al2/kiwi1/claude/9305a/src/com/goldencode/p2j/persist/pl/BuiltIns.java:90: error: cannot find symbol
      BeginsSupport.class,
      ^
  symbol:   class BeginsSupport
  location: class BuiltIns

Sorry I forgot to bzr add that file. Doing it now.

You can update the branch. Committed rev. 16766.

Ștefănel, did you wrote some testcases for BEGINS, on multiple collations?
I need to see how it works and why the augmented expression (range check and then bunch of OR based expression) is needed.

Teodor Gorghe wrote:

Ștefănel, did you wrote some testcases for BEGINS, on multiple collations?
I need to see how it works and why the augmented expression (range check and then bunch of OR based expression) is needed.

Wait, that's my bad, I committed some experimental changes in 9305a, that I uncommitted, please update the branch, for now there is only the range check. I'm experimenting with different options right now. But, I think I will keep only a simple LIKE filter at last. It should be safer.

Wait, that's my bad, I committed some experimental changes in 9305a, that I uncommitted, please update the branch, for now there is only the range check. I'm experimenting with different options right now. But, I think I will keep only a simple LIKE filter at last. It should be safer.

Currently I see outputs as begins udf ("begins(upper(tt1.f2), upper(tt1.f1))") or upper(tt1.f1) like begins_index(upper('l%')) with 9305a/16766. Is this the right revision to Review (2026-09-15 06:41:13)?

Alexandru Lungu wrote:

Wait, that's my bad, I committed some experimental changes in 9305a, that I uncommitted, please update the branch, for now there is only the range check. I'm experimenting with different options right now. But, I think I will keep only a simple LIKE filter at last. It should be safer.

Currently I see outputs as begins udf ("begins(upper(tt1.f2), upper(tt1.f1))") or upper(tt1.f1) like begins_index(upper('l%')) with 9305a/16766. Is this the right revision to Review (2026-09-15 06:41:13)?

upper(tt1.f1) like begins_index(upper('l%')) should be turned into the range check in the final sql. I think the udf part is emitted for a begins without an index, I need to recheck.

Changes from 9305a/r16767 to r16768 is supposed to fix the issue from #9305-60?

I have looked what is new and I see that you have made an optimization (eg. begins ? into IS NULL) and added the (expression_like OR equality_expression).
Why the equality is needed since it will be also matched in the like expression?

Teodor Gorghe wrote:

Changes from 9305a/r16767 to r16768 is supposed to fix the issue from #9305-60?

Both are FQL, before the preprocessor runs, so both are expected.
begins_index(...) is a conversion-time marker, emitted by rules/annotations/where_clause.rules:678,1187 when the left operand is a character field and is_index_field says it's indexed.
begins(upper(tt1.f2), upper(tt1.f1)) is field-BEGINS-field. The marker rule only fires for a string literal or a substitution parameter; a field-to-field BEGINS is emitted as the begins() UDF and never becomes a LIKE, so bracketIndexedBegins() skips it at compare.getType() != LIKE. This is trunk behaviour.

I have looked what is new and I see that you have made an optimization (eg. begins ? into IS NULL) and added the (expression_like OR equality_expression).
Why the equality is needed since it will be also matched in the like expression?

Because the LIKE pattern keeps the prefix's trailing blanks, and the equality is the one case it misses.
BEGINS "abc " converts to x like 'abc %'. In 4GL that is TRUE for the row x = "abc", but 'abc' LIKE 'abc %' is FALSE. The range bound is built from rtrim(prefix) precisely so it still admits that row, but LIKE filters it. If I used the rtrimmed value directly for the LIKE, it will break more testcases.

• Cache compiled LIKE patterns to avoid recompiling per row, skip the LIKE to '=' rewrite under rtrim compare modes (which would change semantics), and reset invalidPattern between calls so a bad pattern doesn't poison later ones.

I understand now the changes, thanks. Does the changes from H2Helper and from UDF are compatible with all 4GL collations, or we limit to some (I don't see such thing in the code).

- PostgreSQL (udf/postgresql/udfs.sql, begins_upper) is correct in general. It does not assume any particular character order; instead, it determines the true maximum character at runtime using actual SQL comparisons (max(chr(i)) / greatest()), which are subject to the database’s active collation.
It then brackets (appends) the prefix with copies of that single global maximum character. The resulting range check looks like this: (field >= 'prefix' and field <= 'prefix' || '<maxchar>')

- H2Helper is a bit more limited, and I think it could be improved.

I know, but I mean, if you use en-US@UTF_8 collation on 4GL, persistent or temporary table, field begins "at", it will find the ața record from database?

This is a testcase:

DEFINE VARIABLE m AS MEMPTR    NO-UNDO.
DEFINE VARIABLE s AS CHARACTER NO-UNDO.

DEFINE TEMP-TABLE tt NO-UNDO FIELD f AS CHARACTER INDEX ix IS PRIMARY f.

SET-SIZE(m) = 5.
PUT-BYTE(m, 1) = 97.
PUT-BYTE(m, 2) = 200.
PUT-BYTE(m, 3) = 155.
PUT-BYTE(m, 4) = 97.
PUT-BYTE(m, 5) = 0.
s = GET-STRING(m, 1).
SET-SIZE(m) = 0.

CREATE tt.
tt.f = s.

FIND FIRST tt WHERE tt.f BEGINS "at" NO-ERROR.

PUT UNFORMATTED "cpcoll=" SESSION:CPCOLL
                " f BEGINS 'at' : " STRING(AVAILABLE tt, "TRUE/false") SKIP.

DISPLAY tt.

Output:

proenv>_progres -b -p 9305.p -cpinternal utf-8 -cpstream utf-8 -cpcoll ICU-en
cpcoll=ICU-en f BEGINS 'at' : TRUE

f
--------------
ața

I am a bit surprised that ICU-ro also matches the ața record:

proenv>_progres -b -p 9305.p -cpinternal utf-8 -cpstream utf-8 -cpcoll ICU-ro
cpcoll=ICU-ro f BEGINS 'at' : TRUE

f
--------------
ața

Changed the code to use the cedilla version (ţ instead of ț), and the results are the ones which I have expected: ICU-en matches while ICU-ro doesn't.

I was doing the same kind of test right now, actually. Both, measured on OE 12.8 with -cpinternal UTF-8, indexed field:

-cpcoll ICU-en_US (= en-US@UTF_8) — finds it, 2 records:
FOR EACH t WHERE t.c BEGINS "at"  ->  ata, ața
index order                       ->  ata, ața, aua, aza
ț shares t's primary weight, so it sorts between ata and aua and falls inside the bracket.

-cpcoll Basic (same UTF-8 code page) — does not find it, 1 record:
FOR EACH t WHERE t.c BEGINS "at"  ->  ata
index order                       ->  ata, aua, aza, ața
Basic on UTF-8 sorts non-ASCII by raw encoded bytes, so ț (0xC89B) lands after z and is outside the bracket entirely.

So, we can’t always match exactly what happens in OE for a BEGINS query on an indexed field. The behavior depends on the collation being used and how the LIKE operator handles it.
At the moment, the results are correct when compared with the equivalent unindexed OE BEGINS behavior. Given this, I think it would be reasonable to treat this as a current limitation and consider matching the behavior of the unindexed BEGINS as sufficient for now.
Trying to reproduce the exact OE behavior in every case could get quite complicated, and I’m not sure the added complexity would be worth it. It feels more reasonable to keep the behavior consistent with the unindexed BEGINS and avoid over-engineering this for what are likely to be edge cases.

Teodor Gorghe wrote:
I agree with what you said, but let's refine things a bit:

I mean that the range check is not the universal solution. Take as for example, character ț, which is represented as 0xC8 0x9B. In Romanian alphabet, ț sits between t and u, but in English, is treated as same as t. (ț maps to t).

• ț (whose UNICODE position (hex code-point) is 021B) is encoded in UTF-8 as 0xC8 0x9B
• from lexical PoV, t and ț are the same letter, they only differ by an accent. Some dialects (like SQL Server) have special collations which take into consideration the accents, or not (Latin1_General_100_CI_AS_SC_UTF8 vs Latin1_General_100_CI_AI_SC_UTF8: AS — Accent-Sensitive, AI — Accent-Inensitive);

I am a bit surprised that ICU-ro also matches the ața record:

• The fact that you got ața instead of ața (Romanian for 'the thread') is most likely the byte order (try PUT-BYTE(m, 3) = 200. PUT-BYTE(m, 2) = 155., or better PUT-STRING('ț', 2));
• when the database compares the strings, it does not compare the bytes directly, but reads one character (that is, one or more bytes, decodes them to Unicode) at a time and compares their code-point, using the collation rules;
• ICU-ro and ICU-en have different rules.

I committed 16769,16770 with some cleanups and simplifications. The code should be simpler now.

I have analyzed the changes on latest 9305a, changes looks great, can be controlled from directory.xml.
I am a little bit concerned about when BEGINS works in case sensitive mode vs case insensitive, but we need a confirmation with some testcases. Is begins udf ("begins(upper(tt1.f2), upper(tt1.f1))") output right?

I'll let Alex to decide the final result of review process.

Teodor Gorghe wrote:

I am a little bit concerned about when BEGINS works in case sensitive mode vs case insensitive, but we need a confirmation with some testcases. Is begins udf ("begins(upper(tt1.f2), upper(tt1.f1))") output right?

Your concern is right, there are some issues for case-sensitive. I will fix them in the next commit.

I'll let Alex to decide the final result of review process.

I will look into it first thing tomorrow morning.

Stefanel Pezamosca wrote:

Your concern is right, there are some issues for case-sensitive. I will fix them in the next commit.

Committed in revision 16771. After I generated some testcases to test conversion/runtime for case sensitivity I fixed more issues with case sensitivity for BEGINS, MATCHES, LOOKUP and INDEX (They were related to each other and had changes in the exact same places).

Ok, the only issue which I currently see in the code are just two large history entries. It would have been nicer if these could be summarized into just 1 line (in rare case, two, if there is so much to say).

I have one question. If you have a case sensitive variable which is the second operand of BEGINS, how it gets into SQL? I am curious to see if in this case, it will use the upper(rtrim(my_table_field)) index.

Teodor Gorghe wrote:

Ok, the only issue which I currently see in the code are just two large history entries. It would have been nicer if these could be summarized into just 1 line (in rare case, two, if there is so much to say).

Alright, I'll see what I can do about this.

I have one question. If you have a case sensitive variable which is the second operand of BEGINS, how it gets into SQL? I am curious to see if in this case, it will use the upper(rtrim(my_table_field)) index.

It will not, at least from what I tested and compared with OE, that index can't be used.

Ok, if you query the INDEX-INFORMATION attribute, that index is not there, correct?

Ok, I was wrong, it will use the index, but it will find rows only if the second operand of BEGINS is uppercased. I have to add more detail to my testcases.

So, for a case-insensitive field it should be like this: upper(rtrim([field])) LIKE [pattern]:CS / upper([pattern]:CI).

Stefanel Pezamosca wrote:

So, for a case-insensitive field it should be like this: upper(rtrim([field])) LIKE [pattern]:CS / upper([pattern]:CI).

Fixed this case in revision 16772 together with some History entry cleanups.