ApiQueryExtLinksUsage::run query has crazy limit
Open, NormalPublic

Description

Next steps:

  • Merge the schema change patch: https://gerrit.wikimedia.org/r/#/q/If5c137f6
  • Deploy the schema change to all wikis: T153182
  • Merge the "populate field" patch: https://gerrit.wikimedia.org/r/#/q/I971edf01
  • Wait for the "populate field" patch to be deployed to all wikis.
  • (optional) Schema change to drop the default on the el_index_60 column: (task not filed yet)
  • Run maintenance/populateExternallinksIndex60.php: (task not filed yet)
  • Merge the "start using field" patch: https://gerrit.wikimedia.org/r/#/q/I84d224ef
  • Announce in tech news that Special:LinkSearch results might be incomplete in between when the above patch is deployed to the wiki and the maintenance script below is run on the wiki.
  • Run maintenance/refreshExternallinksIndex.php: (task not filed yet)

Crazy limit offsets like this are showing up in slow query logs for enwiki:

SELECT /* ApiQueryExtLinksUsage::run  */
  page_id,page_namespace,page_title,el_to
  FROM `page`,`externallinks`
  WHERE (page_id=el_from)
  AND (el_index  LIKE 'http://gov.nih.nlm.ncbi.%' )
  LIMIT 768500,501;

By itself it's not too bad, < 10 seconds, but they're appearing in spikes presumably from something automated and causing concurrency issues.

Suggest disallowing such page offsets or redesigning the pagination method.

Details

Reference
bz57176
bzimport raised the priority of this task from to High.
bzimport set Reference to bz57176.
bzimport added a subscriber: Unknown Object (MLST).

Can you count how often the LIKE will match?
SELECT COUNT(*)

FROM externallinks

WHERE el_index LIKE 'http://gov.nih.nlm.ncbi.%'

When the result is a number over the offset, it is okay, when someone is getting all external link usages for this url.

A primiary key was added to externallinks table with gerrit 51675 which allows changing the pagination method of the api and [[Special:LinkSearch]] (bug 45237). Maybe it can allow descending order on that table (bug 32386, bug 32401)

enwiki> SELECT COUNT(*)

->   FROM externallinks
->  WHERE el_index LIKE 'http://gov.nih.nlm.ncbi.%';

+----------+

COUNT(*)

+----------+

951774

+----------+
1 row in set (3 min 57.90 sec)

The externallinks PK is partly added but some larger wikis (including en) are yet to be done.

For the time being, spikes of these queries may get killed if slaves get overloaded.

aaron added a comment.EditedFeb 11 2014, 11:06 PM

el_id would help when the el_index query prefix is the full el_index key length (60 chars) or more. Even if all results are all actually < 60 chars, all rows would have to be scanned to know that. In any case, if the query prefix is < 60 chars, then you no longer have the property of easily getting a range of index records having an equal first part and are ordered by the second part. Ordering by el_id in that case could be slower than the OFFSET query used now since MySQL would have to quicksort for all matches just to return the top X.

Option A:
Maybe we could have two more or more el_index indexes, accept they'd be on smaller prefixes (e.g. a 30 and 15). The index with the largest prefix that is smaller than the query prefix could be used. Non-matching rows (were only the prefix in the index matched, not the whole el_index field) would just be eliminated via scanning.

Option B:
It could help to have a new field:

-- Bucket to page on for large prefix queries
el_bucket UNSIGNED INTEGER DEFAULT MOD(el_id,1024)

...and a new index:

el_bucket_index ON externallinks (el_bucket,el_index (60))

When a LIKE query is estimated to match many rows (100000+), the API query could page through el_bucket from 0 to 1023, doing the LIKE query for each bucket.

Option A means using FORCE INDEX I guess. Since multiple indexes would increase the overall footprint it would need testing to see if there is a net improvement. My guess would be probably not much.

Option B sounds like application-side hash partitioning. Anything that breaks up queries would help, though that may not speed up the api-user experience. Along the same lines we could investigate server-side partitioning now that S1 api traffic is sent to specific slaves.

aaron added a comment.Feb 26 2014, 6:10 AM

With B, the API would would get the requested number of rows within a shard (moving to the next one as needed to respect the limit). The API continue parameter would include the shard and next link. The shards just give a stable ordering to page on, rather than having to keep doing more and more work for each subsequent query of the same result size. It should be much faster for the api-user.

If the B method of paging works for the users, great. Let's see what Anomie thinks.

Anomie added a comment.EditedFeb 26 2014, 5:26 PM

I thought I had posted an analysis of these API modules somewhere, but now I can't find it.

As noted already, the query for ApiQueryExtLinksUsage looks something like this:

SELECT page_id,page_namespace,page_title,el_to FROM `page`,`externallinks`
 WHERE (page_id=el_from) AND (el_index LIKE 'http://gov.nih.nlm.ncbi.%' ) LIMIT $OFFSET,501;

ApiQueryExternalLinks has the same issue, BTW. Its queries look something like this:

SELECT el_from, el_to FROM externallinks
 WHERE (el_from IN (1,2,3,4,5,6,7,...,5000)) AND (el_index LIKE 'http://gov.nih.nlm.ncbi.%') ORDER BY el_from LIMIT $OFFSET,501;

Option B is to change the first to making queries like this for $NUM from 0 to 1023?

SELECT page_id,page_namespace,page_title,el_to FROM `page`,`externallinks`
 WHERE (page_id=el_from) AND (el_index LIKE 'http://gov.nih.nlm.ncbi.%' ) AND el_bucket = $NUM LIMIT $OFFSET,501;

It'd be doable, although we still have the offset in there so it's still ugly IMO. We'd also need another index to handle ApiQueryExternalLinks in a similar way: either (el_bucket, el_from, el_index(60)) or (el_from, el_bucket, el_index(60)) would work, I think.

I note that the API doesn't really have any clue as to whether the like is likely to match many rows, so we'd either have to do some sort of pre-query to test it (e.g. SELECT COUNT(*) FROM (SELECT 1 FROM externallinks WHERE el_index LIKE $FOO LIMIT 5001) AS tmp) or else always do the bucket method.

Also, to avoid making clients do excessive numbers of queries to get back few rows from each, I'd prefer ApiQueryExtLinksUsage to do as many of the 1024 bucket queries it needs to fill up the requested limit. For example, if the 1000000 matching links were evenly spread across the buckets, ApiQueryExtLinksUsage called by someone with apihighlimits and eulimit=5000 would wind up making 6 queries: bucket 0 with limit 5001 getting about 977 rows, bucket 1 with limit 4024 getting another 977, bucket 2 with limit 3047, bucket 3 with limit 2070, bucket 4 with limit 1093, and bucket 5 with limit 116. And if the 1000000 matching links were all in bucket 999 (major hashing failure!), it'd do 1000 queries.

I like Option A better, since it would let us get rid of that offset entirely and also to stop trusting the database to not arbitrarily change the row ordering when no ORDER BY is actually given. But couldn't we just use one long index field and do a range match if the query is shorter, much like Block::getRangeCond()?

-- This is el_index truncated to 60 bytes
el_index_60 VARBINARY(60) NOT NULL

CREATE INDEX /*i*/el_index_60 ON /*_*/externallinks (el_index_60, el_id);
CREATE INDEX /*i*/el_from_index_60 ON /*_*/externallinks (el_from, el_index_60, el_id);

Then the queries would look something like this:

-- Note '/' is '.' + 1
SELECT page_id,page_namespace,page_title,el_to,el_index_60,el_id FROM `page`,`externallinks`
 WHERE (page_id=el_from)
  AND (el_index_60 >= 'http://gov.nih.nlm.ncbi.' AND el_index_60 < 'http://gov.nih.nlm.ncbi/' AND el_index LIKE 'http://gov.nih.nlm.ncbi.%')
  AND (el_index_60 > 'http://gov.nih.nlm.ncbi.XXXX' OR (el_index_60 = 'http://gov.nih.nlm.ncbi.XXXX' AND el_id >= $ID))
 ORDER BY el_index_60, el_id LIMIT 501;

SELECT el_from,el_to,el_index_60,el_id FROM externallinks
 WHERE (el_from IN (1,2,3,4,5,6,7,...,5000))
  AND (el_index_60 >= 'http://gov.nih.nlm.ncbi.' AND el_index_60 < 'http://gov.nih.nlm.ncbi/' AND el_index LIKE 'http://gov.nih.nlm.ncbi.%')
  AND (el_from > $FROM OR (el_from = $FROM AND (el_index_60 > 'http://gov.nih.nlm.ncbi.XXXX' OR (el_index_60 = 'http://gov.nih.nlm.ncbi.XXXX' AND el_id >= $ID))))
 ORDER BY el_from, el_index_60, el_id LIMIT 501;

-- In these, the query is over 60 characters so el_index_60 is constant
SELECT page_id,page_namespace,page_title,el_to,el_id FROM `page`,`externallinks`
 WHERE (page_id=el_from)
  AND (el_index_60 = 'http://gov.nih.nlm.ncbi./foo/bar/xxxxxxxxxxxxxxxxxxxxxxxx/ba' AND el_index LIKE 'http://gov.nih.nlm.ncbi./foo/bar/xxxxxxxxxxxxxxxxxxxxxxxx/baz/%')
  AND (el_id >= $ID)
 ORDER BY el_id LIMIT 501;

SELECT el_from,el_to,el_id FROM externallinks
 WHERE (el_from IN (1,2,3,4,5,6,7,...,5000))
  AND (el_index_60 = 'http://gov.nih.nlm.ncbi./foo/bar/xxxxxxxxxxxxxxxxxxxxxxxx/ba' AND el_index LIKE 'http://gov.nih.nlm.ncbi./foo/bar/xxxxxxxxxxxxxxxxxxxxxxxx/baz/%')
  AND (el_from > $FROM OR (el_from = $FROM AND el_id >= $ID))
 ORDER BY el_from, el_id LIMIT 501;
aaron added a comment.Mar 7 2014, 7:40 PM

I'm OK with A too. The above approach looks reasonable. Indeed we will need both extra columns with indexes and not just more prefixes since even FORCE is not enough to get MySQL to be aware of the possible optimization.

Sean, how does my proposal in comment 7 sound to you?

Sean: How does anomie's proposal in comment 7 sound?

Sean: How does anomie's proposal in comment 7 sound?

(In reply to Brad Jorsch from comment #9)

Sean, how does my proposal in comment 7 sound to you?

Looks like we can't make Sean answer here. :(

greg added a comment.Oct 21 2014, 10:36 PM

(suggestion: add it (the question for Sean) to the Scrum of Scrums)

Ah, sorry. Dropped the ball.

Setting up a real test of both options on enwiki.eternallinks now.

Ah, sorry. Dropped the ball.

Setting up a real test of both options on enwiki.eternallinks now.

Did you get a chance to run the test?

Any more new on this?

@Springle: Did you get a chance to run the test?

@Springle: Did you get a chance to run the test?

And is this really "high priority"?

Springle lowered the priority of this task from High to Normal.Jul 6 2015, 4:51 AM
Springle set Security to None.
aaron added a subscriber: jcrespo.Sep 18 2015, 5:21 PM

externalinks may need physical partitioning, exactly in the way that "bucketing" is proposed. As I would be starting analysis from 0, and with my current load, you shouldn't make this a blocker on me and start doing tests independently on a spare slave. In general, all our LIMITs should die with fire, as they are eventually abused.

externalinks may need physical partitioning, exactly in the way that "bucketing" is proposed.

Even if we have to have non-transparent partitioning in there, IMO it would still be good to not have to use LIMIT with an offset.

As I would be starting analysis from 0, and with my current load, you shouldn't make this a blocker on me and start doing tests independently on a spare slave.

I for one don't know how to safely do such tests independently on a spare slave (e.g. without breaking replication or the like), or how to know which slaves might be spare in the first place.

In general, all our LIMITs should die with fire, as they are eventually abused.

I'm not sure what this means.

Qgil removed a subscriber: Qgil.Sep 21 2015, 1:53 PM
jcrespo added a comment.EditedSep 25 2015, 11:21 AM

Even if we have to have non-transparent partitioning in there, IMO it would still be good to not have to use LIMIT with an offset.

+1

As I would be starting analysis from 0, and with my current load, you shouldn't make this a blocker on me and start doing tests independently on a spare slave.

I for one don't know how to safely do such tests independently on a spare slave (e.g. without breaking replication or the like), or how to know which slaves might be spare in the first place.

Let me then either do it or help you do it. There are not really spare slaves, we have to take them out of production :-)

In general, all our LIMITs should die with fire, as they are eventually abused.

I'm not sure what this means.

LIMIT 55 000 000, 501

As we have seen by actual bot requests.

Not an issue if indexes are being used for filtering.

I for one don't know how to safely do such tests independently on a spare slave (e.g. without breaking replication or the like), or how to know which slaves might be spare in the first place.

Let me then either do it or help you do it. There are not really spare slaves, we have to take them out of production :-)

If you've got time to walk me through it (or to write up comprehensive instructions) I'm willing to give it a try.

LIMIT 55 000 000, 501

As we have seen by actual bot requests.

Limits with offsets, yes, kill them.

Status: Proposal in T59176#603751, looking for DBA approval of the plan before writing up the schema change and such.


In an attempt to make some sort of progress here, I loaded the eowiki[1][2] page and externallinks sql dumps into a local MySQL instance, made the changes proposed in T59176#603751, and executed some test queries. In the dump used, externallinks had 795030 rows and page had 512465.

First, before and after for adding the column and the two indexes:

-rw-rw---- 1 mysql mysql      3017 Nov 17 22:07 externallinks.frm
-rw-rw---- 1 mysql mysql 562036736 Nov 17 22:10 externallinks.ibd
...
-rw-rw---- 1 mysql mysql      4085 Nov 17 22:13 externallinks.frm
-rw-rw---- 1 mysql mysql 696254464 Nov 17 22:14 externallinks.ibd

It added about 169 bytes per row for this data set. Average length of the el_index_60 column is 52.5692, versus 81.1349 for the el_index column. 56.65% of the el_index values were truncated to fit el_index_60.

Query plans look good to me, they're all using the expected indexes:

MariaDB [test]> explain SELECT page_id,page_namespace,page_title,el_to,el_index_60,el_id FROM `page`,`externallinks` WHERE (page_id=el_from) AND (el_index_60 >= 'http://com.google.www.' AND el_index_60 < 'http://com.google.www/' AND el_index LIKE 'http://com.google.www.%') AND (el_index_60 > 'http://com.google.www./search?q=85.71.0.46' OR (el_index_60 = 'http://com.google.www./search?q=85.71.0.46' AND el_id >= 86891)) ORDER BY el_index_60, el_id LIMIT 501;
+------+-------------+---------------+--------+-------------------------------------------------------+-------------+---------+----------------------------+------+------------------------------------+
| id   | select_type | table         | type   | possible_keys                                         | key         | key_len | ref                        | rows | Extra                              |
+------+-------------+---------------+--------+-------------------------------------------------------+-------------+---------+----------------------------+------+------------------------------------+
|    1 | SIMPLE      | externallinks | range  | PRIMARY,el_from,el_index,el_index_60,el_from_index_60 | el_index_60 | 66      | NULL                       |   96 | Using index condition; Using where |
|    1 | SIMPLE      | page          | eq_ref | PRIMARY                                               | PRIMARY     | 4       | test.externallinks.el_from |    1 |                                    |
+------+-------------+---------------+--------+-------------------------------------------------------+-------------+---------+----------------------------+------+------------------------------------+

MariaDB [test]> explain SELECT el_from,el_to,el_index_60,el_id FROM externallinks WHERE (el_from IN (16754,17560,1370,360856,394832,394818,395719,395705,403133,16532,395871,342632,559952,233818,42825,427708,427710,440412,564913,377355,257114,344194,397441,978,977,492539,333274,235760,4349,217624,562943,493589,431176,567974,393840,272548,28526,497954,359671,514142,2042,508425,281106,486778,40122,329054,427905,416945,414900,95611,49707,314527,1041,230990,301800,102091,570772,532990,21540,462934,334228,2709,216352,345484,527735,527992,524995,541987,534382,537803,530252,428850,525424,511554,529746,538713,524939,535882,525433,525284,357918,296763,14973,329735,329737,376028,348580,538873,471979,33350,33681,33694,33683,129951,223186,194424,549537,51470,21898,129893,14279,272908,404837,224778,4057,3300,18522,49165,2655,48380,140212,2792,3923,29758,1606,69696,58906,59364,36906,294178,130209,372990,452232,421576,11965,40256,34650,34688,34775,28770,43685,34691,4591,34047,32564,374364,25618,401821,25806,1155,131444,10403,342630,418677,106800,57883,60977,407926,294799,224897,219857,225992,222368,224436,241831,243411,2680)) AND (el_index_60 >= 'http://com.google.www.' AND el_index_60 < 'http://com.google.www/' AND el_index LIKE 'http://com.google.www.%') AND (el_from > 33683 OR (el_from = 33683 AND (el_index_60 > 'http://com.google.www./search?&q=%22Banska_Bystrica%22' OR (el_index_60 = 'http://com.google.www./search?&q=%22Banska_Bystrica%22' AND el_id >= 9714)))) ORDER BY el_from, el_index_60, el_id LIMIT 101;
+------+-------------+---------------+-------+-------------------------------------------------------+------------------+---------+------+------+------------------------------------+
| id   | select_type | table         | type  | possible_keys                                         | key              | key_len | ref  | rows | Extra                              |
+------+-------------+---------------+-------+-------------------------------------------------------+------------------+---------+------+------+------------------------------------+
|    1 | SIMPLE      | externallinks | range | PRIMARY,el_from,el_index,el_index_60,el_from_index_60 | el_from_index_60 | 70      | NULL |  188 | Using index condition; Using where |
+------+-------------+---------------+-------+-------------------------------------------------------+------------------+---------+------+------+------------------------------------+

MariaDB [test]> explain SELECT page_id,page_namespace,page_title,el_to,el_id FROM `page`,`externallinks` WHERE (page_id=el_from) AND (el_index_60 = 'https://de.bayern.statistikdaten.www./genesis/online?sequenz' AND el_index LIKE 'https://de.bayern.statistikdaten.www./genesis/online?sequenz=%') AND (el_id >= 820607) ORDER BY el_id LIMIT 501;
+------+-------------+---------------+--------+-------------------------------------------------------+-------------+---------+----------------------------+------+------------------------------------+
| id   | select_type | table         | type   | possible_keys                                         | key         | key_len | ref                        | rows | Extra                              |
+------+-------------+---------------+--------+-------------------------------------------------------+-------------+---------+----------------------------+------+------------------------------------+
|    1 | SIMPLE      | externallinks | range  | PRIMARY,el_from,el_index,el_index_60,el_from_index_60 | el_index_60 | 66      | NULL                       | 1540 | Using index condition; Using where |
|    1 | SIMPLE      | page          | eq_ref | PRIMARY                                               | PRIMARY     | 4       | test.externallinks.el_from |    1 |                                    |
+------+-------------+---------------+--------+-------------------------------------------------------+-------------+---------+----------------------------+------+------------------------------------+

MariaDB [test]> explain SELECT el_from,el_to,el_index_60,el_id FROM externallinks WHERE (el_from IN (82241,168116,170059,168396,175374,168104,174451,168028,168153,168332,175381,168527,168673,174976,168165,175553,168542,175543,168601,168347,168530,175873,175639,169581,168587,177049,170054,175718,176664,176167,169252,170121,169605,177229,169661,175737,177279,177388,169813,177221,175907,176230,174629,174689,175129,175376,177556,178297,177506,178747,182273,182574,175847,178375,177524,175386,178510,178230,176975,182901,178580,183365,175491,175763,176390,182969,182543,177745,182646,183130,184522,177596,184392,184206,178237,178560,182364,183678,184460,184244,182895,183922,185055,182350,178162,185539,182936,178311,182672,182355,182680,186423,183927,185823,183873,186477,183154,184073,186215,185815,187907,183903,183390,187584,187459,185596,184756,184718,184081,185696,184823,186447,185287,185954,186221,186385,186371,186817,186356,186455,185933,187846,186965,185438,186370,186460,188091,188159,183174,185136,502712,182771,182924,502744,186641,186218,184561,502852,175823,169759,176951,177980,177699,176894,186200,168358,168)) AND (el_index_60 = 'https://de.bayern.statistikdaten.www./genesis/online?sequenz' AND el_index LIKE 'https://de.bayern.statistikdaten.www./genesis/online?sequenz=%') AND (el_from > '184081' OR (el_from = '184081' AND el_id >= '794204')) ORDER BY el_from, el_id LIMIT 101;
+------+-------------+---------------+-------+-------------------------------------------------------+------------------+---------+------+------+------------------------------------+
| id   | select_type | table         | type  | possible_keys                                         | key              | key_len | ref  | rows | Extra                              |
+------+-------------+---------------+-------+-------------------------------------------------------+------------------+---------+------+------+------------------------------------+
|    1 | SIMPLE      | externallinks | range | PRIMARY,el_from,el_index,el_index_60,el_from_index_60 | el_from_index_60 | 70      | NULL |   46 | Using index condition; Using where |
+------+-------------+---------------+-------+-------------------------------------------------------+------------------+---------+------+------+------------------------------------+

[1]: https://dumps.wikimedia.org/eowiki/latest/
[2]: I tried to pick one that wouldn't overload my laptop.

Anomie moved this task from Unsorted to Blocked on the MediaWiki-API board.Nov 18 2016, 5:10 AM

Anomie you say "a local MySQL instance", but we do not use mysql on production. Can you test it on the latest 10.0 MariaDB version. This uses IN and we know mariadb lags behind MySQL on that respect.

Apologies for speaking inexactly, my local "MySQL" instance actually is MariaDB. More specifically, it's from Debian's mariadb-server package in unstable as of whenever I last had apt install updates.

MariaDB [test]> select @@version;
+-------------------+
| @@version         |
+-------------------+
| 10.0.28-MariaDB-1 |
+-------------------+

I still think of it as MySQL because all the command line commands are still "mysql", even though "MariaDB" is right there in the default prompt. :/

Oh, no, that is great- then I have no further comments, let's go with it. the problem with externallinks.ibd size is not the indexes, but the format. This is similar in spirit to the change done for pagelinks/templatelinks/imagelinks, right? And that has already given lots of improvements.

Anomie moved this task from Blocked to In Dev on the MediaWiki-API board.Nov 18 2016, 4:37 PM
Anomie claimed this task.
Anomie moved this task from In Dev to Needs Review on the MediaWiki-API board.Nov 21 2016, 8:19 PM

Change 322727 had a related patch set uploaded (by Anomie):
Add externallinks.el_index_60 column and indexes

https://gerrit.wikimedia.org/r/322727

Change 322728 had a related patch set uploaded (by Anomie):
Populate externallinks.el_index_60 and drop default

https://gerrit.wikimedia.org/r/322728

Change 322729 had a related patch set uploaded (by Anomie):
Use new externallinks.el_index_60 field

https://gerrit.wikimedia.org/r/322729

Anomie updated the task description. (Show Details)Nov 21 2016, 8:20 PM

Change 322727 merged by jenkins-bot:
Add externallinks.el_index_60 column and indexes

https://gerrit.wikimedia.org/r/322727

jcrespo updated the task description. (Show Details)Dec 14 2016, 10:05 AM
Anomie updated the task description. (Show Details)Dec 14 2016, 2:13 PM
Krinkle updated the task description. (Show Details)Dec 15 2016, 5:55 AM
Krinkle removed a subscriber: wikibugs-l-list.
Reedy moved this task from Unsorted to Change on the Schema-change board.Apr 26 2017, 3:32 PM

Why can't you just sort by el_index? Then you could use el_index values for continuation.

We can't use only by el_index since it's not unique. While MariaDB will probably return the rows in the same order every time, that's not guaranteed to it's possible rows could be repeated and/or skipped across a continuation. Even if we ignore that possibility as being unlikely to happen in practice, trying to continue only on el_index will break in much the same way as was reported in T26782.

So we'd have to order by something like el_index, el_id for proper behavior. The resulting query would look something like

SELECT page_id,page_namespace,page_title,el_to,el_index,el_id FROM `page`,`externallinks` WHERE (page_id=el_from) AND (el_index  LIKE 'http://gov.nih.nlm.ncbi.%' ) ORDER BY el_index, el_id LIMIT 501;

The EXPLAIN output for that doesn't look too good:

mysql:wikiadmin@db2069 [enwiki]> explain SELECT page_id,page_namespace,page_title,el_to,el_index,el_id FROM `page`,`externallinks` WHERE (page_id=el_from) AND (el_index  LIKE 'http://gov.nih.nlm.ncbi.%' ) ORDER BY el_index, el_id LIMIT 501;
+------+-------------+---------------+--------+------------------+----------+---------+------------------------------+---------+-----------------------------+
| id   | select_type | table         | type   | possible_keys    | key      | key_len | ref                          | rows    | Extra                       |
+------+-------------+---------------+--------+------------------+----------+---------+------------------------------+---------+-----------------------------+
|    1 | SIMPLE      | externallinks | range  | el_from,el_index | el_index | 62      | NULL                         | 2153646 | Using where; Using filesort |
|    1 | SIMPLE      | page          | eq_ref | PRIMARY          | PRIMARY  | 4       | enwiki.externallinks.el_from |       1 |                             |
+------+-------------+---------------+--------+------------------+----------+---------+------------------------------+---------+-----------------------------+

A filesort is usually a bad sign, it probably means the database is going to fetch all the millions of rows that match the WHERE condition, sort them, and then return the first 501, throwing away the rest.

Trying that query to verify it with SHOW STATUS took way too long, I eventually killed it. But that in itself is an indication that it really is fetching all those millions of rows.

Fortunately I still have the eowiki externallinks and page tables loaded from a dump into my local database from T59176#2804914. So let's try it out there, the EXPLAIN is the same. The most-linked domain in that dump was http://tools.wmflabs.org, so we'll query for that.

MariaDB [test]> SELECT @@version;
+------------------+
| @@version        |
+------------------+
| 10.1.22-MariaDB- |
+------------------+
1 row in set (0.00 sec)

MariaDB [test]> SELECT COUNT(*) FROM externallinks WHERE el_index  LIKE 'http://org.wmflabs.tools.%';
+----------+
| COUNT(*) |
+----------+
|    92313 |
+----------+
1 row in set (9.87 sec)

MariaDB [test]> FLUSH STATUS; pager cat > /dev/null; SELECT page_id,page_namespace,page_title,el_to,el_index,el_id FROM `page`,`externallinks` WHERE (page_id=el_from) AND (el_index  LIKE 'http://org.wmflabs.tools.%' ) ORDER BY el_index, el_id LIMIT 501; pager; SHOW STATUS LIKE '%Hand%';
Query OK, 0 rows affected (0.00 sec)

PAGER set to 'cat > /dev/null'
501 rows in set (3.83 sec)

Default pager wasn't set, using stdout.
+---------------------------------------+-------+
| Variable_name                         | Value |
+---------------------------------------+-------+
| Handler_commit                        | 1     |
| Handler_delete                        | 0     |
| Handler_discover                      | 0     |
| Handler_external_lock                 | 0     |
| Handler_icp_attempts                  | 0     |
| Handler_icp_match                     | 0     |
| Handler_mrr_init                      | 0     |
| Handler_mrr_key_refills               | 0     |
| Handler_mrr_rowid_refills             | 0     |
| Handler_prepare                       | 0     |
| Handler_read_first                    | 0     |
| Handler_read_key                      | 492   |
| Handler_read_last                     | 0     |
| Handler_read_next                     | 92313 |
| Handler_read_prev                     | 0     |
| Handler_read_retry                    | 0     |
| Handler_read_rnd                      | 501   |
| Handler_read_rnd_deleted              | 0     |
| Handler_read_rnd_next                 | 0     |
| Handler_rollback                      | 0     |
| Handler_savepoint                     | 0     |
| Handler_savepoint_rollback            | 0     |
| Handler_tmp_update                    | 0     |
| Handler_tmp_write                     | 0     |
| Handler_update                        | 0     |
| Handler_write                         | 0     |
| Performance_schema_file_handles_lost  | 0     |
| Performance_schema_table_handles_lost | 0     |
+---------------------------------------+-------+

Yeah, that Handler_read_next value shows it really did fetch all the rows then sort them. At least it seems to have not fetched the page rows until after the sorting. The results are largely the same when I run them on db2056 against the current eowiki, although of course the time taken differs.

My changed queries look a lot better:

MariaDB [test]> explain SELECT page_id,page_namespace,page_title,el_to,el_index_60,el_id FROM `page`,`externallinks` WHERE (page_id=el_from) AND (el_index_60 >= 'http://org.wmflabs.tools.' AND el_index_60 < 'http://org.wmflabs.tools/' AND el_index LIKE 'http://org.wmflabs.tools.%') ORDER BY el_index_60, el_id LIMIT 501;
+------+-------------+---------------+--------+-----------------------------------------------+-------------+---------+----------------------------+--------+-------------+
| id   | select_type | table         | type   | possible_keys                                 | key         | key_len | ref                        | rows   | Extra       |
+------+-------------+---------------+--------+-----------------------------------------------+-------------+---------+----------------------------+--------+-------------+
|    1 | SIMPLE      | externallinks | range  | el_from,el_index_60,el_from_index_60,el_index | el_index_60 | 62      | NULL                       | 281360 | Using where |
|    1 | SIMPLE      | page          | eq_ref | PRIMARY                                       | PRIMARY     | 4       | test.externallinks.el_from |      1 |             |
+------+-------------+---------------+--------+-----------------------------------------------+-------------+---------+----------------------------+--------+-------------+
2 rows in set (0.01 sec)

MariaDB [test]> FLUSH STATUS; pager cat > /dev/null; SELECT page_id,page_namespace,page_title,el_to,el_index_60,el_id FROM `page`,`externallinks` WHERE (page_id=el_from) AND (el_index_60 >= 'http://org.wmflabs.tools.' AND el_index_60 < 'http://org.wmflabs.tools/' AND el_index LIKE 'http://org.wmflabs.tools.%') ORDER BY el_index_60, el_id LIMIT 501; pager; SHOW STATUS LIKE '%Hand%';
Query OK, 0 rows affected (0.00 sec)

PAGER set to 'cat > /dev/null'
501 rows in set (0.05 sec)

Default pager wasn't set, using stdout.
+---------------------------------------+-------+
| Variable_name                         | Value |
+---------------------------------------+-------+
| Handler_commit                        | 1     |
| Handler_delete                        | 0     |
| Handler_discover                      | 0     |
| Handler_external_lock                 | 0     |
| Handler_icp_attempts                  | 0     |
| Handler_icp_match                     | 0     |
| Handler_mrr_init                      | 0     |
| Handler_mrr_key_refills               | 0     |
| Handler_mrr_rowid_refills             | 0     |
| Handler_prepare                       | 0     |
| Handler_read_first                    | 0     |
| Handler_read_key                      | 492   |
| Handler_read_last                     | 0     |
| Handler_read_next                     | 500   |
| Handler_read_prev                     | 0     |
| Handler_read_retry                    | 0     |
| Handler_read_rnd                      | 0     |
| Handler_read_rnd_deleted              | 0     |
| Handler_read_rnd_next                 | 0     |
| Handler_rollback                      | 0     |
| Handler_savepoint                     | 0     |
| Handler_savepoint_rollback            | 0     |
| Handler_tmp_update                    | 0     |
| Handler_tmp_write                     | 0     |
| Handler_update                        | 0     |
| Handler_write                         | 0     |
| Performance_schema_file_handles_lost  | 0     |
| Performance_schema_table_handles_lost | 0     |
+---------------------------------------+-------+

It fetched only the needed number of rows, which is exactly what we want to see. And it finished 100× faster too (I ran these queries multiple times and the timings were stable enough).

We can't use only by el_index since it's not unique. While MariaDB will probably return the rows in the same order every time, that's not guaranteed to it's possible rows could be repeated and/or skipped across a continuation. Even if we ignore that possibility as being unlikely to happen in practice, trying to continue only on el_index will break in much the same way as was reported in T26782.

Out of curiosity, I decided to check whether sorting by only el_index would work on the DB side even if it isn't fit for purpose.

mysql:wikiadmin@db2056 [eowiki]> explain SELECT page_id,page_namespace,page_title,el_to,el_index,el_id FROM `page`,`externallinks` WHERE (page_id=el_from) AND (el_index  LIKE 'http://org.wmflabs.tools.%' ) ORDER BY el_index LIMIT 501;
+------+-------------+---------------+--------+------------------+----------+---------+------------------------------+--------+-----------------------------+
| id   | select_type | table         | type   | possible_keys    | key      | key_len | ref                          | rows   | Extra                       |
+------+-------------+---------------+--------+------------------+----------+---------+------------------------------+--------+-----------------------------+
|    1 | SIMPLE      | externallinks | range  | el_from,el_index | el_index | 62      | NULL                         | 188138 | Using where; Using filesort |
|    1 | SIMPLE      | page          | eq_ref | PRIMARY          | PRIMARY  | 4       | eowiki.externallinks.el_from |      1 |                             |
+------+-------------+---------------+--------+------------------+----------+---------+------------------------------+--------+-----------------------------+

Nope, same bad query plan. And an actual run followed by SHOW STATUS confirms. I suspected as much, since the index on a prefix of el_index can't be used to sort on the full field.

MariaDB will probably return the rows in the same order every time

It definitely does not happen- this has proven in practice because different queries can go to different servers and those will be unsorted.

1978Gage2001 moved this task from Triage to In progress on the DBA board.Dec 11 2017, 9:45 AM
Marostegui moved this task from In progress to Triage on the DBA board.Dec 11 2017, 11:06 AM