FWD » Core Development » Database

I recall spending some time in #6196 to identify a clean and short way to encode the 4GL FIRST/LAST semantics using SQL, but there was no straight-forward way of doing so. At that time I was mainly troubled by outer-joins.

Right now, strictly talking about inner joins, FIRST and LAST are supported using the following SQL syntax:

SELECT [...]
FROM first_table tt
CROSS JOIN second_table tt2
WHERE [...] and tt2.recid = (
   SELECT tt22.recid
   FROM second_table tt22
   WHERE [...] and tt2.fk = tt.pk
   ORDER BY tt2.fk LIMIT 1
)
ORDER BY tt.pk

This is semantically equivalent, but brings in planning complexity. In H2, the query is rarely optimized as it is highly dependent upon the ORDER BY clause and other WHERE clauses. Worst-case scenario, the tables are actually cross-joined and each combination is eliminated if it doesn't match the sub-select result. The good part is that the database engines (including H2) evaluates the sub-select only once per tt selected.

I can't recall the details of how H2 is doing the planning here, so we should start by extracting some H2 generated plans to better understand how such query is executed.

An alternative to this technique would be to introduce a FIRST JOIN or LAST JOIN into the H2 syntax. This would simply break the joining process if a record was found matching the WHERE clause (exactly like in 4GL). There are several considerations here:

• The ORDER BY of the joined table should be explicitly stated. This can be either fixed using other kind of custom syntax/clauses or by introducing a USE-INDEX syntax which was formerly supported by H2.
• The table order shouldn't change. H2 has such conditional implemented, but usually cutting down table permutation planning leads to performance decrease.
• Planning changes. FIRST/LAST join should be scored differently comparing to a CROSS JOIN when considering plans.

Alexandru Lungu wrote:

An alternative to this technique would be to introduce a FIRST JOIN or LAST JOIN into the H2 syntax. This would simply break the joining process if a record was found matching the WHERE clause (exactly like in 4GL). There are several considerations here:

• The ORDER BY of the joined table should be explicitly stated. This can be either fixed using other kind of custom syntax/clauses or by introducing a USE-INDEX syntax which was formerly supported by H2.

When converting FIND/FIRST LAST, whether as a joined query component (i.e., RandomAccessQuery) or as a standalone FindQuery, we select an index and generate a corresponding ORDER BY clause in FQL syntax. At runtime, this clause is resolved back to an index, and AFAIK resolves to an SQL ORDER BY clause.

There is code in RAQ.initialize which uses the primary index in the event the FQL ORDER BY clause can't be resolved back to an index. I don't recall ATM under which conditions this can occur.

AFAIR in the CompoundQuery case, if we optimize, the sub-select created for that FIRST/LAST component retains the ORDER BY created by the conversion.

Either way, the point is that I think we always ultimately emit an ORDER BY clause in the SQL.

• The table order shouldn't change. H2 has such conditional implemented, but usually cutting down table permutation planning leads to performance decrease.

What do you mean by the "table order" in this context?

• Planning changes. FIRST/LAST join should be scored differently comparing to a CROSS JOIN when considering plans.

Makes sense.

Right now, strictly talking about inner joins...

Could this proposed syntax be used for OUTER JOIN as well?

Eric Faulhaber wrote:

When converting FIND/FIRST LAST, whether as a joined query component (i.e., RandomAccessQuery) or as a standalone FindQuery, we select an index and generate a corresponding ORDER BY clause in FQL syntax. At runtime, this clause is resolved back to an index, and AFAIK resolves to an SQL ORDER BY clause.
Either way, the point is that I think we always ultimately emit an ORDER BY clause in the SQL.

Right. However, in a FIRST/LAST join case, H2 can't detect what we mean by FIRST/LAST simply using the ORDER BY clause:

• SELECT * FROM tt FIRST JOIN tt2 ORDER BY tt.f1 asc, tt2.f2 asc is a case in which H2 can't trivially understand the order of tt2 to resolve FIRST. We can state that FIRST means the one with the lowest f2, because this is the sorting of the second component. Even if this is somehow encoded in the ORDER BY clause, it is not an invariant.
• SELECT * FROM tt FIRST JOIN tt2 USE-INDEX idxf2 ORDER BY tt.f1 asc, tt2.f2 asc is a good solution, because we clarify what FIRST actually means. Most probably, this is actually easy to implement as we simply force a plan in which tt2 is traversed using an index.
• SELECT * FROM tt FIRST JOIN tt2 BY tt2.f2 ORDER BY tt.f1 asc, tt2.f2 asc is a more general solution, covering the cases where we have something like FIRST tt2 BY f2 in 4GL. It is H2's duty to plan that FIRST JOIN to resolve the FIRST tt2. However, this "H2 duty" becomes our duty, so we need to implement a plan for such case
  • in some cases, the BY clause can be implicitly resolved by an index, but which one?
  • on other cases, we can preselect and sort tt before joining

What do you mean by the "table order" in this context?

I think "table permutation" would be a better statement. When doing joins, the database planners may prefer to join the tables in a different order than the one provided by the SQL. In H2 at least, it tries all the possible permutations if there are at most 7 tables. I had some converted testcases in which H2 preferred to permute the tables before the join. Usually, this provides a better performance.
If we are to introduce FIRST/LAST join, we should rethink this optimization.

• SELECT * FROM tt CROSS JOIN tt2 FIRST JOIN tt3 may be permuted to SELECT * FROM tt2 CROSS JOIN tt FIRST JOIN tt3, but can't be permuted to SELECT * FROM tt FIRST JOIN tt3 CROSS JOIN tt2 (also considering WHERE clauses)
• Basically, we can only permute any continuous segment of cross joins. At this point I am concerned that our current SQLs (using subselect to handle FIRST/LAST) using table permutation may be faster than a native FIRST/LAST join without table permutation.
• In FWD, we don't currently mind this optimization as long as the records are returned in the right order. However, once FIRST/LAST joins are implemented, we need to mind the order of the joins to ensure FIRST and LAST are correctly resolved.

Could this proposed syntax be used for OUTER JOIN as well?

The changes for OUTER JOIN should start somewhere sooner. AFAIK, we don't even emit OUTER JOIN queries. All of these are converted to CompoundQuery and solved one-by-one. There is already some work in #6196 (#6196-15 for classic SQL) for PreselectQuery. I can't find a reason why we can't integrate this syntax for H2. However, if we are to support outer-join:

• we need first to get #6196 (OUTER-JOIN with FIRST/LAST) done to allow outer-join in all dialects
• afterwards, optimize the H2 use-cases to directly use the FIRST/LAST join.