The OFFSET should be optimized in H2

[pittlu]

There is a table named vssq_user contains 1,000,000 records,the following SQL query takes more than 20 seconds:

SELECT * FROM VSSQ_USER  LIMIT 10 OFFSET 600000

The DDL of the table is:

CREATE TABLE

    VSSQ_USER

    (

        ID_ CHAR(32) NOT NULL,

        COMPANY_ CHAR(32) NOT NULL,

        EMAIL_ VARCHAR(256) NOT NULL,

        PASSWORD_ VARCHAR(256) NOT NULL,

        SALT_ VARCHAR(64),

        NAME_ VARCHAR(1024) NOT NULL,

        OTHER_NAME_ VARCHAR(1024),

        GENDER_ CHAR(1) NOT NULL,

        TEL_ VARCHAR(16),

        IM_ VARCHAR(16),

        ADDRESS_ VARCHAR(1024),

        BIRTHDAY_ DATE,

        REMARK_ CLOB,

        VALID_STATUS_ CHAR(1) DEFAULT '1' NOT NULL,

        MODIFIED_TIME_ TIMESTAMP NOT NULL,

        CREATED_TIME_ TIMESTAMP NOT NULL,

        VERSION_ INTEGER NOT NULL,

        PRIMARY KEY (ID_),

        CONSTRAINT FK_USER_COMPANY FOREIGN KEY (COMPANY_) REFERENCES VSSQ_COMPANY (ID_) ON

    DELETE

        RESTRICT

    );

Is there anyway to optimize performance?

[Noel Grandin]

You could try using an index like this:
SELECT * FROM VSSQ_USER LIMIT 10 OFFSET 600000 ORDER BY ID__

But even that is not going to be particularly fast because it will still
have to iterate through the whole index to find the right position.

The correct answer is "don't do that".
Why on earth on would you be trying to do that anyhow?

[pittlu]

Just for write a database performance report and mysql faster than h2 when use similar function.Anyway thanks very much for your advice.

在 2013年7月11日星期四UTC+8下午5时30分56秒，Noel Grandin写道：

[Noel Grandin]

If you have a real use-case, then we could look at making it faster, but
I'm not going to spend time on a purely artificial test-case.

[Thomas Mueller]

Hi,

It is possible to optimize this, but it is not so easy. I wonder how MySQL is doing it internally.

The best way I know to optimize it is using a "counted b-tree". This is possible with the MVStore (the future storage engine for H2). However support for transactions makes it more complicated, so I'm not sure if it really makes sense to optimize it.

Regards,

Thomas 

--
You received this message because you are subscribed to the Google Groups "H2 Database" group.
To unsubscribe from this group and stop receiving emails from it, send an email to h2-database...@googlegroups.com.
To post to this group, send email to h2-da...@googlegroups.com.
Visit this group at http://groups.google.com/group/h2-database.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[pittlu]

Hi,

I want to give you a suggestion, maybe you can temporarily stop the implementation of new features, focusing on optimizing performance, even at 1 billion row table, 500 concurrent work very well, improve usability.

I tested one billion row table 500 concurrent, insert spend time more than 6 seconds, query spend more ugly than mysql (12G memory, 8-core CPU, jrockit JDK 6, Ubuntu 64bit OS)

在 2013年7月12日星期五UTC+8上午12时26分31秒，Thomas Mueller写道：

[Lukas Eder]

In exceptional cases, OFFSET clauses can be most efficiently implemented by counting and skipping the largest possible logical data sets in either a TABLE or INDEX structure, according to the specified SELECT query. With only one physical table in the table source and no predicates / group by expressions, etc, there are three cases:

1. SELECT * FROM t LIMIT x OFFSET y

2. SELECT * FROM t ORDER BY id LIMIT x OFFSET y

3. SELECT * FROM t ORDER BY abc LIMIT x OFFSET y

The OP is asking about case 1) where OFFSET can be implemented prior to loading physical blocks from the table. In fact, the engine could just skip loading entire blocks until reaching the OFFSET y, as it knows the block size. In this example, I'd expect 1) to perform best

Case 2) might perform in a similar way as 1), as the loading of table data can be skipped until the OFFSET y has been reached from the index structure, skipping index leaf blocks whose size is probably also known to the engine.

Case 3) is where the current slow implementation will probably be the only reasonable implementation, as the actual data has to be traversed. Case 3) is also applicable when using more complex table sources, or predicates.

Looking at H2's engine code (in particular, Select.queryFlat()), I'm not sure if such optimisations should be a priority, as I don't think that the current "execution plan" is flexible enough for such transformations. The risk of introducing bugs may be higher than the overall benefit, as the above queries are rather exceptional cases.

[Noel Grandin]

On 2013-07-12 09:03, Lukas Eder wrote:
> In exceptional cases, OFFSET clauses can be most efficiently
> implemented by counting and skipping the largest possible logical data
> sets in either a TABLE or INDEX structure, according to the specified
> SELECT query.
>

It should be possible to pass this information down to our Index classes
and have them perform the skipping.
The downside is that this optimisation is only applicable to top-level,
single-table queries.
Anything else would have to fall back to the current implementation.

Given that the OP was asking about a synthetic benchmark, not a
real-world use-case, I agree that it is not worth the extra complexity.

[Lukas Eder]

2013/7/12 Noel Grandin <noelg...@gmail.com>

It is a real-world use-case, in my opinion. :-)

Any database visualisation tool that has a paging feature will produce precisely those queries... This may include something as simple as a website. It's just very probable that predicates will be added to the query.

I'm actually wondering if the code in Select.queryFlat() is correct, with respect to the FOR UPDATE clause. It seems that LIMIT 3 OFFSET 2 will lock 5 rows, instead of 3. So maybe, the performance improvement would really be to push offset handling into queryFlat() and skip the evaluation of the projection and the locking for skipped rows. Of course, I'm not sure about potential side-effects of such a change...

[Noel Grandin]

On 2013-07-12 10:07, Lukas Eder wrote:
>
> It is a real-world use-case, in my opinion. :-)

Go back and re-read the original email.

> Any database visualisation tool that has a paging feature will produce
> precisely those queries... This may include something as simple as a
> website. It's just very probable that predicates will be added to the
> query.
>

In which case we can't use the optimisation.
The moment you do anything more complex than a select without any where
clauses and only one table in the from clause you can't use the
optimisation.

[Lukas Eder]

2013/7/12 Noel Grandin <noelg...@gmail.com>

On 2013-07-12 10:07, Lukas Eder wrote:

It is a real-world use-case, in my opinion. :-)

Go back and re-read the original email.

OK, OK ;-)

Let's go back and re-read the original email. Citing the OP:

    "Just for write a database performance report and mysql faster than h2 when use similar function"

In this case, the OP did have a real-world use-case that you, as an H2 developer, should be concerned about in my opinion. They were making a rather generic performance benchmark to compare H2 with MySQL. Now, whether this benchmark was done well or thoroughly might be questionable, but I'd be careful with immediately jumping to the conclusion that

    "The correct answer is 'don't do that'. "

Why not? Why not challenge an Open Source database with a silly stress test?

Now, once such a benchmark surfaces blogs, indicating that H2 might be poorly optimised, it is hard to get rid of such feelings again. Besides, if you don't take such requests seriously, you risk facing FUD, eventually. So, please, Noel, let me kindly ask you to be a bit more open-minded towards such support requests. In the long run, I think they can add value to H2, which is a great database. Even if the actual implementation may not be a high priority just yet :-)

Any database visualisation tool that has a paging feature will produce precisely those queries... This may include something as simple as a website. It's just very probable that predicates will be added to the query.

In which case we can't use the optimisation.
The moment you do anything more complex than a select without any where clauses and only one table in the from clause you can't use the optimisation.

The Oracle database does 100's of silly optimisations, such as a constant predicate stop check. An Oracle query or an Oracle subselect will not be fully executed if - by query transformation - it can be proven that a part won't return any results. An example:

    SELECT * FROM t WHERE 1 = 0

Or also

    SELECT * FROM t t1

    INNER JOIN (

        SELECT * FROM t t2 WHERE 1 = 0

    ) ON t1.id = t2.id

Or if there's a CHECK constraint on t.a, such as CHECK(t.a in (1, 2))

    SELECT * FROM t WHERE t.a = 3

These sure aren't mission-critical optimisations, but they do add some value, even if the above statements are overly silly. But with a sophisticated CBO, every little optimisation eventually adds up towards Oracle (or also SQL Server) being awesome databases. Tom Kyte's "Metadata Matters" is an excellent presentation about the topic:

http://blog.jooq.org/2011/11/25/how-schema-meta-data-impacts-oracle-query-transformations

Now, if adding OFFSET optimisations to complex queries might be out of scope, adding simple ones to simple queries might help those users who know that H2 has these optimisations and who can explicitly leverage those in their queries.

Apart from this OFFSET story, what's your take about my findings related to bad locking of records that are not within the LIMIT .. OFFSET window? I think there is a significant bug in Select.queryFlat(). Besides, there's a low hanging optimisation fruit for all OFFSET handling (with or without predicates), if the projection is never evaluated for those rows that are excluded by the OFFSET clause. What do you think?

Cheers

Lukas

[Noel Grandin]

On 2013-07-12 14:27, Lukas Eder wrote:

Why not? Why not challenge an Open Source database with a silly stress test?

Because the nice part about being an Open Source database is that we can make the choice to ignore stupid test cases that don't make real world sense.
I take as my inspiration Linus Torvald's frequent rants against exactly the behaviour of optimising for non-useful benchmarks.

But hey, if you want to produce patches to optimise such use cases, I won't stand in the way of getting them into the code.

Apart from this OFFSET story,

I tend to ignore tack-on questions that try to hijack a discussion, otherwise it gets painful to remember where I am in which part of the discussion.

 I'd rather you started a new thread with a different subject line.

[Lukas Eder]

Hi Noel,

OK, I'm going to be a bit sarcastic in this mail. I hope you're not offended.

2013/7/12 Noel Grandin <noelg...@gmail.com>

On 2013-07-12 14:27, Lukas Eder wrote:

Why not? Why not challenge an Open Source database with a silly stress test?

Because the nice part about being an Open Source database is that we can make the choice to ignore stupid test cases that don't make real world sense.
I take as my inspiration Linus Torvald's frequent rants against exactly the behaviour of optimising for non-useful benchmarks.

Yes, the great inspiration to all benevolent dictators! I know the feeling.

 

But hey, if you want to produce patches to optimise such use cases, I won't stand in the way of getting them into the code.

I used to want that. But Linus's rants never motivated me too much :-)

Apart from this OFFSET story,

I tend to ignore tack-on questions that try to hijack a discussion, otherwise it gets painful to remember where I am in which part of the discussion.

OK, one more time, before I give up.

These were neither tack-on questions nor a hijacked discussion unless you have a very different understanding when it comes to hijacking. 

I was actually trying to give some input about various ways how OFFSET can be optimised. Let's re-read the OP's mail subject:

    "The OFFSET should be optimized in H2"

So, not hijacked. :-)

After giving my input about execution plans, I found an actual bug related to OFFSET handling, unless I misunderstood the code.

Now, if I specify OFFSET 600000 and H2 will evaluate the projection for all the 599999 records that are not of interest, then OFFSET might be a bit slow, right? Consider this code from Select.queryFlat(). 600000x the following piece of code

    Value[] row = new Value[columnCount];

    for (int i = 0; i < columnCount; i++) {

        Expression expr = expressions.get(i);

        row[i] = expr.getValue(session);

    }

That's 600000 arrays put into the result arraylist, each with the length of the number of columns in the queried table. I don't know if this accounts for 10% or 90% of the OP's reported 20 seconds. But 600000 arrays with 17 columns (from the OP's table) is a lot of wasted memory when skipping to OFFSET 600000.

And this happens for non-silly queries, too. In fact, this happens for every OFFSET clause unless I made a mistake? OFFSET 1000 is a more real-world use-case, agreed. And as a side-effect of this issue, there was also the wrong (or unexpected) FOR UPDATE behaviour.

 

 I'd rather you started a new thread with a different subject line.

Maybe later, Linus. :-)

BTW: I'm sorry if my comments are perceived off-topic or rude. I'm trying to take 1-2 things with a bit of humour. It wasn't meant personal. I was just trying to help.

[Noel Grandin]

On 2013-07-12 15:53, Lukas Eder wrote:
>
> OK, I'm going to be a bit sarcastic in this mail. I hope you're not
> offended.
>

Not at all.

> Now, if I specify OFFSET 600000 and H2 will evaluate the projection
> for all the 599999 records that are not of interest, then OFFSET might
> be a bit slow, right? Consider this code from Select.queryFlat().
> 600000x the following piece of code
>

You are correct, that it is how we currently perform that query.

>
> That's 600000 arrays put into the result arraylist, each with the
> length of the number of columns in the queried table. I don't know if
> this accounts for 10% or 90% of the OP's reported 20 seconds. But
> 600000 arrays with 17 columns (from the OP's table) is a lot of wasted
> memory when skipping to OFFSET 600000.

You say waste, I say nice simple code.
Now, I'm not saying you're wrong, and maybe we can improve that.
But I'd like to see a real-world case first, and I'd also like to see
some profiling that points to that code as a problem.
Because at the moment our performance is pretty darn good, and a large
chunk of that is precisely because we don't go chasing benchmarks and
fixing problems that are only theoretical.

>
> And this happens for non-silly queries, too. In fact, this happens for
> every OFFSET clause unless I made a mistake? OFFSET 1000 is a more
> real-world use-case, agreed. And as a side-effect of this issue, there
> was also the wrong (or unexpected) FOR UPDATE behaviour.

Yeah, the side effect is that we lock a few more rows than we should.
But that's not a correctness issue, it's just a performance issue.

And this is my last word on this topic for today, further queries will
be > /dev/null

[Thomas Mueller]

Hi,

I think optimising OFFSET is possible, but to really optimise it more significantly, we would need to avoid doing unnecessary I/O. Just avoiding the in-memory transformation wouldn't really help that much in my view, and possibly would make the code more complex. But to avoid doing the I/O with the current data structures is quite hard. And I don't think MySQL uses significantly different data structures (I don't think they use a counted b-tree as in the MVStore), so I'm a bit surprised that MySQL is faster. But maybe MySQL isn't actually all that much faster - possibly it's just because MySQL has more cache by default: the cache size of H2 is usually 16 MB, and for MySQL it's a lot more I believe. In any case, before we do optimise anything, we would need a good benchmark, and we would need to understand why MySQL is faster.

Another question of course is: is it a high priority to optimise OFFSET? With high priority I mean, does it make sense to delay other work and concentrate on this. This I don't know, but I believe it's not such a high priority. Of course others might feel different :-) If so, please speak up!

Regards,

Thomas

--
You received this message because you are subscribed to the Google Groups "H2 Database" group.

To unsubscribe from this group and stop receiving emails from it, send an email to h2-database+unsubscribe@googlegroups.com.

[Brett Ryan]

I have a real world use for needing to optimise either paginated or full select queries.

I'm presently using H2 as a transport database. What I'm doing is exporting data from database to an h2 database, copying the exported data to another machine then using that database to load the data back in on that machine. This method has been found to be very effective for smaller tables, though I'm presently facing a problem with a table that's just shy of 40 million rows. I've got the db built fine, though doing a select without a where clause just borks, as does any paginating with limit/offset.

40 milion is actually conservative as I've only taken a sample size, if I were to process everything this would end up being several billion rows.

If you're wondering what the data is it's retail barcode scans.

[Silvio]

Don't use OFFSET for that. Use an ordering on an indexed column (pk will do fine) in combination with LIMIT.

In fact, NEVER use OFFSET, it is a non-feature.

[Brett Ryan]

Doesn't `select * from table' order on the primary key by default?

If I do `select * from table order by id' where id is the primary key, it never starts streaming the resultset. I tried leaving this running for 12 hours before killing it.

Using offset, at least it starts but then slows down the further it gets.

Pattern being used involves JdbcTemplate where srcJT and destJT are instances of JdbcTemplate src being the h2, dest being a SQL Server instance.

List<Object[]> args = new ArrayList<>();
LOG.debug("Inserting batched mode...");
srcJT.query(select, rs -> {
args.add(argsProducer.apply(rs));
if (args.size() == batchSize) {
LOG.debug("Committing batch {} -> {}", counts[1], counts[0]);
destJT.batchUpdate(insert, args);
counts[0] += args.size();
counts[1]++;
args.clear();
}
});
if (args.size() > 0) {
LOG.debug("Committing batch {} -> {}", counts[1], counts[0]);
destJT.batchUpdate(insert, args);
counts[0] += args.size();
counts[1]++;
args.clear();
}

argsProducer is a function that takes a ResultSet and produces an array of arguments used for the batched insert.

The pattern works very well, and; the exact code is used to create the h2 database in the first place from an OpenEdge database which does start streaming immediately from the select *.

[Noel Grandin]

On 2016/05/25 6:15 AM, Brett Ryan wrote:
> If I do `select * from table order by id' where id is the primary key, it never starts streaming the resultset. I tried leaving this running for 12 hours before killing it.

Yeah, if you do that it's going to try to generate an enormous temporary table.
For large tables, you ALWAYS want to be using LIMIT.

The problem with OFFSET is that the further you get into the results, the more unnecessary work the engine has to do.

What I used to do, (back when I needed pagination), was to store the PK of the last row in the current "page" of results
and add that PK as part of the WHERE clause for the next "page".
That avoids the unnecessary work.

[Silvio]

Which is why I said you should use LIMIT.

[Thomas Mueller Graf]

Hi,

I will document this. Existing documentation: "OFFSET specified how many rows to skip.". I will add "Please note using high offset values should be avoided because it can cause performance problems."

Regards,

Thomas

On Thursday, May 26, 2016, Silvio <sbie...@jambo-software.com> wrote:

Which is why I said you should use LIMIT.

--
You received this message because you are subscribed to the Google Groups "H2 Database" group.

To unsubscribe from this group and stop receiving emails from it, send an email to h2-database...@googlegroups.com.

To post to this group, send email to h2-da...@googlegroups.com.

Visit this group at https://groups.google.com/group/h2-database.
For more options, visit https://groups.google.com/d/optout.