Subquery improvement for select_osc_chunk

[ggunson]

In the line https://github.com/github/gh-ost/blob/master/go/sql/builder.go#L270 there's a sql statement to get an id value, which I guess based on the function name is for the range of ids to copy. This produces a query like:

     select /* gh-ost `schemaname`.`tablename` iteration:12345 */ `id`
				from (
					select
							`id`
						from
							`schemaname`.`tablename`
						where ((`id` > 123456789)) and ((`id` < "987654321") or ((`id` = "987654321")))
						order by
							`id` asc
						limit 100
				) select_osc_chunk
			order by
				`id` desc
			limit 1

I was wondering if this could be rewritten to:

select id 
from schemaname.tablename
where ((`id` > 123456789)) and ((`id` < "987654321") or ((`id` = "987654321")))
order by id asc
limit 1 offset 99

The reason is that the query as-is creates a temporary table and does a filesort on it:

+----+-------------+-------------+-------+---------------+---------+---------+------+---------+--------------------------+
| id | select_type | table       | type  | possible_keys | key     | key_len | ref  | rows    | Extra                    |
+----+-------------+-------------+-------+---------------+---------+---------+------+---------+--------------------------+
|  1 | PRIMARY     | <derived2>  | ALL   | NULL          | NULL    | NULL    | NULL |     100 | Using filesort           |
|  2 | DERIVED     | tablename   | range | PRIMARY       | PRIMARY | 4       | NULL | 8425424 | Using where; Using index |
+----+-------------+-------------+-------+---------------+---------+---------+------+---------+--------------------------+

mysql> show session status like 'handler%';
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| Handler_commit             | 1     |
| Handler_delete             | 0     |
| Handler_discover           | 0     |
| Handler_external_lock      | 2     |
| Handler_mrr_init           | 0     |
| Handler_prepare            | 0     |
| Handler_read_first         | 0     |
| Handler_read_key           | 1     |
| Handler_read_last          | 0     |
| Handler_read_next          | 99    |
| Handler_read_prev          | 0     |
| Handler_read_rnd           | 1     |
| Handler_read_rnd_next      | 101   |
| Handler_rollback           | 0     |
| Handler_savepoint          | 0     |
| Handler_savepoint_rollback | 0     |
| Handler_update             | 0     |
| Handler_write              | 100   |
+----------------------------+-------+
18 rows in set (0.00 sec)

While my suggestion just does an index range scan:

+----+-------------+-------------+-------+---------------+---------+---------+------+---------+--------------------------+
| id | select_type | table       | type  | possible_keys | key     | key_len | ref  | rows    | Extra                    |
+----+-------------+-------------+-------+---------------+---------+---------+------+---------+--------------------------+
|  1 | SIMPLE      | tablename   | range | PRIMARY       | PRIMARY | 4       | NULL | 8425428 | Using where; Using index |
+----+-------------+-------------+-------+---------------+---------+---------+------+---------+--------------------------+

mysql> show session status like 'handler%';
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| Handler_commit             | 1     |
| Handler_delete             | 0     |
| Handler_discover           | 0     |
| Handler_external_lock      | 2     |
| Handler_mrr_init           | 0     |
| Handler_prepare            | 0     |
| Handler_read_first         | 0     |
| Handler_read_key           | 1     |
| Handler_read_last          | 0     |
| Handler_read_next          | 99    |
| Handler_read_prev          | 0     |
| Handler_read_rnd           | 0     |
| Handler_read_rnd_next      | 0     |
| Handler_rollback           | 0     |
| Handler_savepoint          | 0     |
| Handler_savepoint_rollback | 0     |
| Handler_update             | 0     |
| Handler_write              | 0     |
+----------------------------+-------+
18 rows in set (0.00 sec)

My suggestion was also faster in my testing for chunks larger than 100 but I would appreciate other testing. I don't like the use of OFFSET normally, but this isn't pagination, and the query gets run millions of times for a large table so that's a lot of created temporary tables.

[shlomi-noach]

One problem I see with limit 1 offset 99 is what happens is there are less than 100 rows left. Say 30 (because it's the last chunk or because the table is small in the first place).

limit 1 offset 99 will not find the last row: it will return the empty set; whereas the existing solution will find the last row.

[ggunson]

Can we add a check that if the result is an empty set, run another query to get the max(id)? Is that extra empty set check more expensive than the created temporary table and sorting on a master per query?

This is an expensive query that's run on the master. Vividcortex listed it under queries "Missing indexes", and for the table I saw this in, it was run 488,000 times for a table with 17,000,000 rows (once per 35 rows when chunk size = 100).

Why is this running on the master (in GitHub's case where there's a replica being used for the binlog parsing)?

[shlomi-noach]

Can we add a check that if the result is an empty set, run another query to get the max(id)? Is that extra empty set check more expensive than the created temporary table and sorting on a master per query?

we can certainly do that. This should be fairly straightforward.

How expensive is it though? Create a temporary table with 100 integer values?

Why is this running on the master

Let me look into that.

[ggunson]

How expensive is it though? Create a temporary table with 100 integer values?

It's creating a temporary table of 100 integers, then quicksorting it (because it has no index, being just a basic implicit temp table). For every 35 rows of the migrated table(?).

[shlomi-noach]

This is perhaps digging a bit where we have an alternative solution in the form of the offset query, but, can we quantify how expensive this query is? e.g. how much time does it spend as compared to actually copying the chunk of rows?

Anyhow, since there's an offered solution, we can just pursue that. I don't mean to suggest we should invest time in quantifying the current query.

[shlomi-noach]

• and -- thank you! :)

[ggunson]

but, can we quantify how expensive this query is? e.g. how much time does it spend as compared to actually copying the chunk of rows?

Yes, using vividcortex (yay for monitoring). Using today's example:

SELECT:

INSERT IGNORE:

So the selects take about 1/10 the time of the inserts in this case. I'll see if we have other examples.

[shlomi-noach]

Very cool 😄

[ggunson]

I'd actually like to try the PR myself, if that's okay (at least for the query change).

I have 2 lingering questions:

1. Why is it running on the master,
2. Why is it run 3 times per chunk?

Do we need to find exactly-100-row id ranges? (I haven't had to look at the throttling mechanics of this, just wondering aloud).

[shlomi-noach]

I'd actually like to try the PR myself, if that's okay (at least for the query change).

Absolutely, please go ahead!

Why is it running on the master?

I believe this should be safe to run on replica (and internally to gh-ost code, this would be the "inspected server"). For the sake of not making two changes at once, I'd suggest first changing the query, and keep running it on master. I don't feel strongly about this.

Why is it run 3 times per chunk?

Sorry, I don't see that it runs 3 times per chunk?

What I see is:

• gh-ost/go/logic/migrator.go

  Line 1051 in d016760

  hasFurtherRange, err := this.applier.CalculateNextIterationRangeEndValues()

  call ->

• gh-ost/go/logic/applier.go

  Line 393 in d016760

  func (this *Applier) CalculateNextIterationRangeEndValues() (hasFurtherRange bool, err error) {

  call ->

• gh-ost/go/sql/builder.go

  Line 234 in d016760

  func BuildUniqueKeyRangeEndPreparedQuery(databaseName, tableName string, uniqueKeyColumns *ColumnList, rangeStartArgs, rangeEndArgs []interface{}, chunkSize int64, includeRangeStartValues bool, hint string) (result string, explodedArgs []interface{}, err error) {

Also as per the graphs from #422 (comment) the select and insert ignore counts seem to align nicely?

Do we need to find exactly-100-row id ranges?

(nitpick: not "id ranges" but "ranges" in general)

using an exact N-row chunk makes most sense, because it makes the migration most predictable and hopefully stable. I think the code is simplest by expecting an exact number.

I'm unsure what would be an inexact number. Remember that the PK may be sparse (whether using an AUTO_INCREMENT or some multi-column non-int combo); getting "the next N rows" is a sensible approach that overcomes gaps in PK.

[leeparayno]

@ggunson @shlomi-noach In my experience, for our application we have a lot of queries that do the pagination using LIMIT, OFFSET to find exactly the rows of data for a given page to be displayed. However in MySQL,

						order by
							`id` asc
						limit 100

The ORDER BY has to be fully materialized to a temp table, and often to a disk for queries over large tables, before the LIMIT and OFFSET are applied.

For some of our CSV export jobs, that use the same mechanism, we can see an increasing latency of the SELECT as it attempts to page further and further into the data set.

What I've suggested to our development teams is to switch to a query like this:

select id 
from schemaname.tablename
where (`id` >= 1 and `id` < 1000)

Then the next iteration would be

select id 
from schemaname.tablename
where (`id` >= 1000 and `id` < 2000)

In order to remove the ORDER BY and LIMIT clauses. This would not solve the "the next N rows" issue as there could be gaps due to deleted data, however this, in the case of indexed columns or primary keys would be able to use the index to resolve the query and not use a filesort or an temp table paged out to disk.

[ggunson]

@leeparayno In my example, the offset would always be 99 (or 1 off of whatever the chunk size is) and the lower range of the ids would be incremented between each call, so it's not as bad as paginating. It's just getting the 100th id from each starting point, each time.

The ORDER BY has to be fully materialized to a temp table, and often to a disk for queries over large tables, before the LIMIT and OFFSET are applied.

Not in the case of my query suggestion; it's doing an order by primary key ascending, so it's just scanning the primary key and not hitting the table at all, nor creating a temporary table. (Details are in the issue description, but I did also check created_tmp%tables status variables in my earlier testing, and they were 0).

That said, I prefer the idea of being less exact in the chunking, using an id BETWEEN range as you're suggesting rather than this order by/limit/offset, but @shlomi-noach 's concern was that by not getting an exactly similar chunk of ids for each copy, the copying is less consistently applied and time remaining estimates aren't as good. My idea was a compromise between getting this "exact" 100th id value for each query while avoiding the temp table and filesorting of the original.

[shlomi-noach]

That said, I prefer the idea of being less exact in the chunking, using an id BETWEEN range as you're suggesting rather than this order by/limit/offset, but @shlomi-noach 's concern was that by not getting an exactly similar chunk of ids for each copy, the copying is less consistently applied and time remaining estimates aren't as good. My idea was a compromise between getting this "exact" 100th id value for each query while avoiding the temp table and filesorting of the original.

To elaborate, this wouldn't just be an exact number of, say, 1000 as compared to some 998. Consider tables (I've seen many such cases) with a auto_increment primary key column, where the values are as follows:

10
11
12
10000000
10000001
10000002

etc. Such ranges can exist when:

• purging old data (but some rows always remain because)
• skipping AUTO_INCREMENT values via ALTER
• other

In such case, we will run thousands and tens of thousands of redundant statements looking for rows in a non-existent range.

Moreover, this could only be done on integer primary keys. What if:

• PK is a text? (e.g. key-value table)
• is a compound index?

In those cases you cannot even guess in advance what would the value look like 1000 rows from "here". You'd need to search for those rows anyhow.

On both these accounts I feel strongly that the range should be based on a search rather than on heuristic.

Not in the case of my query suggestion; it's doing an order by primary key ascending, so it's just scanning the primary key and not hitting the table at all, nor creating a temporary table. (Details are in the issue description, but I did also check created_tmp%tables status variables in my earlier testing, and they were 0).

👍
We can agree the vast majority of migrations will utilize a PRIMARY KEY ; and whether or not this would be an integer, text, timestamp or compound index, the search would be optimal.