Thanks for these informations.

(In reply to comment #0)
> While testing with a simple embedded database and AOO, I noticed the CHECKPOINT
> statement is being sent to the embedded database after each SELECT statement
> (these are issued internally while browsing table contents). This should not
> happen. A CHECKPOINT uses significant resources and rewrites the .script and
> .backup files even if the data has not changed at all.

I filed this as bug 53473.

Changed status to "NEW"

I spent more time testing LO and AOO base with HSQLDB. Here are the testing methods that can be used with HSQLDB 1.8 and 2.3.0 (pre-release).

In addition to the default embedded HSQLDB implementation, an external HSQLDB server can be used for testing. LO/AOO execute common built-in queries for displaying the list of tables and viewing table contents. The embedded mode performs some additional SQL statements as well.

Performance issues caused by the common built-in queries can be checked with the external HSQLDB Server.

A database can be extracted from the .odb archive file and tested with external HSQLDB Server. When the server is started with the server.silent=false option, it has these advantages:

1. It shows all the queries executed by LO/AOO on the console.
2. It allows simultaneous access to server by a database browser. This allows query execution to be repeated and measured.
3. Query execution plans can be checked with EXPLAIN PLAN FOR SELECT ...
3. Version 2.3.0 supports logging parametric query execution with the parameter values. Use SET DATABASE EVENT LOG SQL LEVEL 3 to log all query executions in the .app.log level created alongside the server database files.

In recent tests I checked Bug 51976 as this relates to a difference between LO 3.6.4.3 and AOO 3.4. The query below is executed only by LO while the rows from a large table are being displayed. The table definition is:

CREATE TABLE "TEST" ("ID" INT PRIMARY KEY, "VAL" VARCHAR(100))

SELECT * FROM "PUBLIC"."PUBLIC"."TEST" WHERE ( 1 = ? AND "PUBLIC"."PUBLIC"."TEST"."ID" = ? OR 1 = ? AND "PUBLIC"."PUBLIC"."TEST"."ID" IS NULL )
 
As mentioned in Bug 51976 this query can cause a severe slowdown in embedded HSQLDB (and HSQLDB server 1.8). Each execution of the query causes all the rows of the table to be examine. Therefore performance degrades exponentially with large tables. The query is executed with parameters such as (1,99,0), with the first and last parameter being constant.

The query is optimised by HSQLDB 2.3.0 and executes in no time.

It seems this query is not needed if the table has a primary key columns, or at least can be reduced to WHERE "PUBLIC"."PUBLIC"."TEST"."ID" = ? which is also fast with embedded HSQLDB 1.8.

Latest patch in Bug 51976 issues different simple queries and avoids the table scan for not-null values. With HSQLDB 1.8, the query with IS NULL would still do a table scan as it is not optimised. Both queries would still run slowly with HSQLDB 2.3.0 or other databases if there is no primary key or other index on the column used.

(In reply to comment #3)

> The query below is executed only by LO while the
> rows from a large table are being displayed.

> SELECT * FROM "PUBLIC"."PUBLIC"."TEST" WHERE ( 1 = ? AND
> "PUBLIC"."PUBLIC"."TEST"."ID" = ? OR 1 = ? AND "PUBLIC"."PUBLIC"."TEST"."ID"
> IS NULL )

> As mentioned in Bug 51976 this query can cause a severe slowdown in embedded
> HSQLDB (and HSQLDB server 1.8). Each execution of the query causes all the
> rows of the table to be examine.

> The query is executed with parameters such
> as (1,99,0), with the first and last parameter being constant.

With the third parameter being 0, the right hand-side of the OR is:
 1 = 0 AND PUBLIC"."PUBLIC"."TEST"."ID" IS NULL
that is
 FALSE AND PUBLIC"."PUBLIC"."TEST"."ID" IS NULL
that is
 FALSE
without needing to evaluate
 PUBLIC"."PUBLIC"."TEST"."ID" IS NULL

I was hoping that "all decent" database engines query optimisation would do that. I was wrong...

> Therefore performance degrades
> exponentially with large tables.

Exponentially? Good lord, that's bad. When you said "full table scan for every row" I understood "reading the whole table is quadratic instead of linear" (times the complexity of getting one row; this could be something like O(log(n)))! What hidden Schlemiel the Painter algorithm in HSQLDB1.8 brings that to *exponential*?

> It seems this query is not needed if the table has a primary key columns, or
> at least can be reduced to WHERE "PUBLIC"."PUBLIC"."TEST"."ID" = ? which is
> also fast with embedded HSQLDB 1.8.

In the case of a single table, yes, obviously.

Now, we introduce joins and cartesian products.

How to get a single row from
 "public" AS p1, "public" AS p2
? It is only natural to do:

 SELECT * FROM "public" AS p1, "public" AS p2
 WHERE p1.ID=? AND p2.ID=?

filling in the parameters with the appropriate values.

Neither
 SELECT * FROM "public" AS p1, "public" AS p2
 WHERE p1.ID=?
nor
 SELECT * FROM "public" AS p1, "public" AS p2
 WHERE p2.ID=?

will do, since this will return multiple rows;
we need to specify the primary key of *ALL* tables
in the WHERE clause.

Now consider an outer join. Either p1.ID or p2.ID is allowed to be NULL... That's the whole point of an outer join. So when we want to retrieve the row where p1.ID is 52 and p.ID is NULL?

In this case, the above query does not work anymore. In full ISO SQL, we could do:

 SELECT * FROM "public" AS p1, "public" AS p2
 WHERE p1.ID IS NOT DISTINCT FROM ? AND p2.ID IS NOT DISTINCT FROM ?

But "IS NOT DISTINCT FROM" is not supported by embedded HSQLDB (1.8), not supported by MySQL, not supported by SQLite (yes, quite some users want to use that...)

In SQLite, one can do:

 SELECT * FROM "public" AS p1, "public" AS p2
 WHERE p1.ID IS ? AND p2.ID IS ?

(Snatching defeat from the jaws of victory... Support the feature but not the common syntax to get to it!)

but no such go in HSQLDB, PostgreSQL nor MySQL: they keep to the ISO SQL that the "?" can only be NULL in this case, not a value.


So, I got to the idea of

( 1 = ? AND tableName."ID" = ? OR 1 = ? AND tableName."ID" IS NULL )

And set either of first/third parameter to 1 and the other to 0 to inactivate the part that does not apply in this particular case. This looked portable... Do you have a better suggestion?


(In reply to comment #4)
> Latest patch in Bug 51976 issues different simple queries and avoids the
> table scan for not-null values.

And punishes engines that have a better query optimiser by having them run
the parser and query planner more often :-(

FYI, I also observed a 20-30% speedup in the absence of any NULL values.

> Both queries would stillrun slowly with HSQLDB 2.3.0 or other databases
> if there is no primary key or other index on the column used.

These queries are *only* on primary index columns
(plus the bits of the WHERE clause in the SELECT we currently show;
 none when showing an entire table).

My comments are for sharing information to make it easier for others to do testing.

I read the original bug report that led to this query, which AFAIR was for an OUTER joint. But in this case, I was viewing the table by double clicking on it. Clearly it is known in advance that LO is using a "SELECT * FROM ATABLE" that is constructed by itself.

I saw the need for the query had something to do with the result set not showing a usable, correct state. I'm not going into that as I don't know much about it. It may be possible to fix it at that level though.

1. If instead of "go to last row" you use the scroll bar, the query is executed multiple times. If it is executed over 100 times, then this is at least approaching exponential. For each execution, HSQLDB 1.8 does one single table scan. It is the repeat execution by LO that makes it take so long.

2. In this case (table view), when it is known the table has a PK, it follows the column is NOT NULL. I don't know a database that works otherwise.

3. NULL matching on PK is unnecessary for cartesian products, any form of INNER JOIN, or any form of OUTER joins! In the case of non-OUTER joins, you should have one equality condition for each joined table, as you show in your example. When you have TABLE A OUTER JOIN TABLE B, for each row of TABLE A that has no match in table B, there is only a single row in the result with NULLs for the given row. Therefore if the required value for TABLE B is NULL, you simply omit the relevant equality condition from the query. The remaining equality condition on TABLE A will suffice to return a single row. You can apply the same principle to RIGHT and FULL OUTER joins.

4. You are right about IS NOT DISTINCT FROM being desirable. I do appreciate your preference for Standard SQL and high-quality query optimisation. But as you can see in the case of missing SQL Standard features from MySQL, despite the fact they had several expert developers for a number of years, database engine development is a very difficult task. Therefore it is obvious that the old HSQLDB 1.8.0 may not optimise some queries well. But version 2.x.x is probably better than most open-source engines in this area.

5. In general, it would be better to focus on not punishing the average user, rather than gaining a small speed advantage with databases that have better optimisation.

6. To sum up, if it is absolutely necessary to execute this query, then LO should distinguish between table viewing and query result viewing. The query should be constructed with equality conditions only relevant to the specific column values. There can be prepared queries when there is no OUTER JOIN.

7. In future, let's check the issue with result sets together and see if there is an alternative solution.

(In reply to comment #3)


Hi Fred,

> In addition to the default embedded HSQLDB implementation, an external
> HSQLDB server can be used for testing. LO/AOO execute common built-in
> queries for displaying the list of tables and viewing table contents. The
> embedded mode performs some additional SQL statements as well.


You should be aware that there is currently the following bug open with regard to multiple different versions of hsqldb.jar (also in latest master builds) :

fdo#34411

Alex

(In reply to comment #7)


> You should be aware that there is currently the following bug open with
> regard to multiple different versions of hsqldb.jar (also in latest master
> builds) :
> 
> fdo#34411
> 
> Alex

Which naturally makes testing and comparison a bit difficult...

Alex

(In reply to comment #8)

Yes, I am aware of that issue. For development work, you can work with either the bundled hsqldb.jar or the newer version 2.x. Not both at the same time.

BTW, if I simply write bug 34411 here, Bugzilla should convert it to a link.

Created attachment 73451 [details]
HSQLDB server output for a test with LO

I include the server console output for a short test. This test can be repeated with any database containing a table with a PK and a few hundred rows.

I have added comment to indicate issues with the queries generated by LO. This includes resources that are not closed and could cause memory leaks.

(In reply to comment #11)
> I include the server console output for a short test.

Thank you for the log and explanatory comments.

> I have added comment to indicate issues with the queries generated by LO.
> This includes resources that are not closed and could cause memory leaks.

It says:

  SQLEXECUTE 6 (single row select ) is performed (...) and the result sets are not closed (not released)

I'm confused. http://docs.oracle.com/javase/6/docs/api/java/sql/ResultSet.html says:

  A ResultSet object is automatically closed when the Statement object that generated it is closed, re-executed, or used to retrieve the next result from a sequence of multiple results.

Clearly in the log you give, the same Statement object (number 6) is reexecuted many times, and then closed, so the documented "automatic close" should happen?



It says:

   SQLEXECUTE 6 (single row select ) is performed nearly 300 times

You just viewed the table, and did not click on "goto last record"? Then things should be better in this respect with 4.0.0 (part of my batch of commits from around 5 December 2012). A release candidate of it can be downloaded from http://www.libreoffice.org/download/pre-releases/
Ping me if things are not better.



It says:

   last SQLPREPARE has statement id 4 which is never used and never closed

It would be useful to get a backtrace of LibreOffice's state when creating that statement.


It says:

   [Server@1e51060]: 0:HQLCLI:CLOSE_RESULT:RESULT_ID 138
   ---------------- the result for SQLEXECUTE 5 (the main select) is closed

How do you match up this one with "SQLEXECUTE 5"? The ID 138 does not appear elsewhere in your log.

(In reply to comment #6)

> I read the original bug report that led to this query, which AFAIR was for
> an OUTER join. But in this case, I was viewing the table by double clicking
> on it. Clearly it is known in advance that LO is using a "SELECT * FROM
> ATABLE" that is constructed by itself.

> 2. In this case (table view), when it is known the table has a PK, it
> follows the column is NOT NULL. I don't know a database that works otherwise.

Yes, but that query is then handed off to a generic layer that handles any query. It would theoretically be possible to use a specialised layer of the generic one when we know that for the particular query at hand primary keys cannot be NULL, but frankly multiplying the code paths is IMHO a trap for bugs and higher maintenance costs.

> I saw the need for the query had something to do with the result set not
> showing a usable, correct state. I'm not going into that as I don't know
> much about it.

When LibreOffice was refetching the data for row
  pKey1: 5
  pKey2: NULL
it was doing it through:
 SELECT * FROM tbl_expression WHERE pKey1=5 AND pKey2=NULL

which obviously failed to actually select the row, so LibreOffice assumed the row has been deleted behind its back (by another thread, or another user connected to the same server or ...). This then led to refetching of the next row, which would also fail, and to a cascade of trying to refetch all rows (with the same problem leading to "row deleted"), and thus LibreOffice suddenly thought the query result was empty, or nearly so.


> 1. If instead of "go to last row" you use the scroll bar, the query is
> executed multiple times. If it is executed over 100 times, then this is at
> least approaching exponential. For each execution, HSQLDB 1.8 does one
> single table scan.

Let $n$ be the size of the table. For simplification, let's assume bounded row size, so that $O(size of table in bytes) = O(number of rows in table)$.

Doing a table scan should take something like $O(n)$. Does it take more? Then, I'm curious why.

Doing that for *each* row (worst case of LibreOffice fetching the whole table when the user slowly uses the scrollbar to go from begin to end), that is $O(n)$ times, leads to a total complexity of $O(n^2)$

For the end result to be $O(c^n)$ for some constant $c$  (that is "exponential")

Anyway... This argument is academic, since quadratic is "too much" anyway. I agree that forcing quadratic behaviour is bad.

> It is the repeat execution by LO that makes it take so
> long.

Which is compounded by the slowness of calling Java code from C++ code :(
(That's "just" a constant factor, but it does not help.)

> 3. NULL matching on PK is unnecessary (...)!
> When you have TABLE A OUTER JOIN TABLE B, for each row of
> TABLE A that has no match in table B, there is only a single row in the
> result with NULLs for the given row. Therefore if the required value for
> TABLE B is NULL, you simply omit the relevant equality condition from the
> query. The remaining equality condition on TABLE A will suffice to return a
> single row. You can apply the same principle to RIGHT and FULL OUTER joins.

Hmmm.... That makes sense; so each time I try to (re)fetch a row that has some NULL in some primary key column, I can just inactivate this condition! For 4.0.1 (too late for 4.0.0), I'll make the "refetch one row query":

SELECT * FROM tblExpression WHERE (pKey1=? OR 1=?) AND (pKey2=? OR 1=?) 

When retrieving the row:
  pKey1: 5
  pKey2: NULL

I'll set the parameters as (5, 0, NULL, 1).

This should work for any tblExpression, right?

Ah, but this will not help HSQLDB 1.8, it will still do a full table scan.

Hmm... If I set the parameters as  (5, 0, DUMMY, 1), where DUMMY is a value of the right type, it should work... But coming up with a value for an arbitrary type (including user-defined) is not that trivial... Any life-saving idea there?

> 4. (...) it is obvious that
> the old HSQLDB 1.8.0 may not optimise some queries well. But version 2.x.x
> is probably better than most open-source engines in this area.

Well, let's cross our fingers for bug 44854, then.

> 7. In future, let's check the issue with result sets together and see if
> there is an alternative solution.

I'm not sure what issue you are referring to; you mean bug 44813?

(In reply to comment #12)
> Clearly in the log you give, the same Statement object (number 6) is
> reexecuted many times, and then closed, so the documented "automatic close"
> should happen?

AFAIR 1.8.0 did not force this, while 2.x.x does. This shouldn't matter too much.
 
>    [Server@1e51060]: 0:HQLCLI:CLOSE_RESULT:RESULT_ID 138
>    ---------------- the result for SQLEXECUTE 5 (the main select) is closed
> 
> How do you match up this one with "SQLEXECUTE 5"? The ID 138 does not appear
> elsewhere in your log.

The log doesn't show this but I run the server in debug and intercepted the close() call.

> but frankly multiplying the code paths is IMHO a trap for
> bugs and higher maintenance costs.

I agree so long as the queries or any other action performed does not degrade the more common simple cases.

> > I saw the need for the query had something to do with the result set not
> > showing a usable, correct state. I'm not going into that as I don't know
> > much about it.
> 
> When LibreOffice was refetching the data for row
>   pKey1: 5
>   pKey2: NULL
> it was doing it through:
>  SELECT * FROM tbl_expression WHERE pKey1=5 AND pKey2=NULL

OK, a correct query can prevent this.

> For the end result to be $O(c^n)$ for some constant $c$  (that is
> "exponential")

Thanks, that corrects my comment.

> Hmmm.... That makes sense; so each time I try to (re)fetch a row that has
> some NULL in some primary key column, I can just inactivate this condition!

Yes, that's the idea.

> For 4.0.1 (too late for 4.0.0), I'll make the "refetch one row query":
> 
> SELECT * FROM tblExpression WHERE (pKey1=? OR 1=?) AND (pKey2=? OR 1=?) 
> 
> When retrieving the row:
>   pKey1: 5
>   pKey2: NULL
> 
> I'll set the parameters as (5, 0, NULL, 1).

Well, this one won't be optimised by HSQLDB 2.x.x. Some database engine may recompile the query on each set of execution parameters. HSQLDB does not recompile. The query planner must create an execution plan that is valid for all possible parameter values. This one would be more complex than the old one therefore the "simple" table scan execution plan is chosen.
 
> This should work for any tblExpression, right?

No, it won't work if you use this method for a query submitted by the user and the query has any GROUP BY, ORDER BY, LIMIT and OFFSET, UNION, or the query is a CALL to a routine that returns a table.

> Ah, but this will not help HSQLDB 1.8, it will still do a full table scan.
> 
> Hmm... If I set the parameters as  (5, 0, DUMMY, 1), where DUMMY is a value
> of the right type, it should work... But coming up with a value for an
> arbitrary type (including user-defined) is not that trivial... Any
> life-saving idea there?

For queries that are generated by LO, find the PK columns and prepare a simple query with equality for each column. Reuse this prepared statement when there is no null. When there is a null, prepare a new query with nulls and reuse this, and so on. You will have at most a handful of prepared queries for multiple OUTER JOIN use. Finally close all the prepared statements. 

For queries that are submitted by the user cache the full result set and display parts of it as the user scrolls over the query result view.

> > 4. (...) it is obvious that
> > the old HSQLDB 1.8.0 may not optimise some queries well. But version 2.x.x
> > is probably better than most open-source engines in this area.
> 
> Well, let's cross our fingers for bug 44854, then.

Certainly. We can work toward it.

> I'm not sure what issue you are referring to; you mean bug 44813?

It was the same issue I mentioned at the beginning and you clarified. So we are covering it right now.

Correction:

When there is a null, prepare a new query with the not-nulls and reuse this, and so on.

Update on HSQLDB

Update: The latest HSQLDB SVN code seems to work fine in-process with LO 3.6.4 :)

For in-process tests, one line of code should be modified as described in the first comment, and the jar compiled.

Tested with the Timbabase.odb database (attached to bug 51976), the table can be modified and saved. Navigation is still slow as discussed before.

Current plan of action on HSQLDB side is:

1. Provide a special version of HSQLDB 2.3.0 that can coexist with the default HSQLDB 1.8.0 for use with external databases (see bug 34411).

2. Work toward bug 44854 with LO developers, providing a backward compatible upgrade path without too much extra effort within LO.

(In reply to comment #18)
> Update: The latest HSQLDB SVN code seems to work fine in-process with LO
> 3.6.4 :)
> 
> ... snip ...
>

Hi, could you please update news with current 4.1.1 LibO release?
has perfomance got any better meanwhile?

(In reply to comment #19)
> (In reply to comment #18)
> > Update: The latest HSQLDB SVN code seems to work fine in-process with LO
> > 3.6.4 :)
> > 
> > ... snip ...
> >
> 
> Hi, could you please update news with current 4.1.1 LibO release?
> has perfomance got any better meanwhile?

It is the responsibility of LO developers to test this further and report any issues that may need changes to the HSQLDB code.

Xisco, this one is old, please see the status.