MySQL seek-method / keyset pagination

MySQL

I am trying to change the pagination from OFFSET, LIMIT to keyset pagination. My problem is, the resultset consists of several groups (plz) ordered by uid. I added a fiddle, see http://sqlfiddle.com/#!9/62a380/10.

Query to get the results

SELECT  
  uid, nick, u.plz, geodb_locations.name 
FROM
  user as u 
LEFT JOIN 
  geodb_locations ON u.plz = geodb_locations.id 
WHERE 
  u.plz IN(29386,30013,29384,29385,29232,29481,29667,29355,29977,30370,30319,30160,29970,29932,29679,29268,30128,29169,29546,29235,29444,29148,29313,30259) 
           
ORDER BY 
  FIELD(u.plz,29386,30013,29384,29385,29232,29481,29667,29355,29977,30370,30319,30160,29970,29932,29679,29268,30128,29169,29546,29235,29444,29148,29313,30259), 
  uid DESC

Resultset

uid     nick    plz     name
46208   user21  29386   Graz
46050   user22  29386   Graz
44995   user23  29386   Graz
-----------------------------------
12883   user46  29384   Gratkorn     <-- Pagination with only uid stops here
-----------------------------------
32667   user47  29385   Gratwein
-----------------------------------
33950   user50  29481   Hitzendorf
33926   user51  29481   Hitzendorf
-----------------------------------
16027   user52  29667   Lannach
496     user53  29667   Lannach
-----------------------------------
19971   user55  29977   Pöls
-----------------------------------
37080   user58  30370   Weiz
33844   user59  30370   Weiz

To paginate through the results I use

uid < 46050

Problem: Pagination is not possible for the whole resultset because uid can be higher than the last uid because of several groups within the resultset. So pagination has to be done by more than 1 column!

Next problem: There is no second column for pagination.
WHERE .. IN and ORDER BY FIELD sorting is fixed. These are zip-codes and they are mixed for each different query, so they can't be used for keyset pagination like (plz, uid) < (123, 987654)

So how is it possible to paginate through the resultset? Any ideas? Thanks in advance!

Fiddle
http://sqlfiddle.com/#!9/62a380/10

Best Answer

You effectively have a 2-column ordering. So, when "remembering where you left off", you must include both columns. Then, the > becomes more complex. I discuss that in a couple of places:

Should I store data pre-ordered rather than ordering on the fly?

http://mysql.rjweb.org/doc.php/deletebig#iterating_through_a_compound_key

General discussion of avoiding OFFSET for pagination: http://mysql.rjweb.org/doc.php/pagination

Granted, the use of FIELD() adds a wrinkle. But not a big wrinkle. Simply use the function call instead of a column name in a few places.

Related Solutions

MySQL Query Optimization : Indexing and Pagination

At this point, you will have to create an index on three columns

ALTER TABLE news ADD INDEX authored_time_sid_ndx (authored,time,sid);

You must then refactor the query just slightly to reduce two things the MySQL Query Optimizer is expected to handle:

the number of rows read
the amount of data collected

Here is your original query:

SELECT sid, title, time, bodytext, author, url FROM news WHERE approved=1 ORDER BY time desc LIMIT $start, $limit

What you can do is gather all the keys first:

SELECT sid FROM news WHERE approved=1 ORDER BY time desc LIMIT $start, $limit

This will perform a full index scan rather than a full table scan because all three columns are in the index. That's a lot less baggage to walk around with for temp table generation because you are scanning just 3 columns in a smaller resource (the index) as opposed to 6 columns as from a bigger resource (the table) as well as not sticking url and bodytext (which are probably VARCHAR(300) and TEXT fields) into the mix just for the sake of gathering keys.

Next, make the SELECT sid query into an inline table and connect them back to the news table using only the fetched keys. EXAMPLE : Suppose your LIMIT variables are 200,10. This means you want to move to the 201st row of the news table and get 10 keys from that point. This means that no matter which page you are on, you want to collect 10 keys at a time, and only 10 keys at a time.

Here is the new and improved query:

SELECT A.sid, A.title, A.time, A.bodytext, A.author, A.url
FROM
news A INNER JOIN
(SELECT sid FROM news WHERE approved=1 ORDER BY time desc LIMIT $start, $limit) B
USING (sid);

The only real cost here is doing a full index scan for keys rather than a full table scan. The benefit is that once you get the 10 keys from the inline SELECT, then only 10 titles, bodytexts, authors and urls are retrieved.

Give it a Try !!!

CAVEAT

As a rule of thumb, anytime you index a column whose cardinality is very low (i.e., Male/Female (2), Single/Married/Divorced/Widowed (4), True/False (2), 0/1 (2)) and the number of rows for any one value exceeds 5% of the total rows in the table, the MySQL Query Optimizer will rule out any and all indexes and you will perform can full table scan or a bad index gets chosen and you end up with a full index scan. This is why it is very imperative that you find the right column distribution, or at the very least perform index scans instead of table scans.

UPDATE 2011-08-08 11:13 EDT

What was I thinking ? This was my original propsed index:

ALTER TABLE news ADD INDEX authored_time_sid_ndx (authored,time,sid);

The field should be approved not authored. This is what it should be:

ALTER TABLE news ADD INDEX approved_time_sid_ndx (approved,time,sid);

The original query you gave was

SELECT sid, title, time, bodytext, author, url FROM news WHERE approved=1 ORDER BY time desc LIMIT $start, $limit

The index I am proposing (approved_time_sid_ndx) will include approved, time, and sid.

The answer that you just submitted has this query :

SELECT sid, title, time, bodytext, author, url FROM news WHERE approved = 1 AND sid > 0 ORDER BY sid desc LIMIT 500, 10;

This being the case, the index you need now should be this:

ALTER TABLE news ADD INDEX approved_sid_ndx (approved,sid);

Both approved and sid should be together. IF they are not together, the MySQL Query Optimizer may decide to perform an internal index merge of the primary key and an index where approved is the first (or only) column. In fact, your new query should be refactored as follows:

SELECT A.sid, A.title, A.time, A.bodytext, A.author, A.url
FROM
news A INNER JOIN
(SELECT sid FROM news WHERE approved=1 and sid > 0 ORDER BY sid desc LIMIT 500,10) B
USING (sid);

Remember, you want an index that encompasses as many DB columns as possible that are embedded in WHERE and ORDER BY clauses.

Mysql – Disable explicit commits in JDBC, detect them in SQL, or put the database in a readonly state

For Oracle, this seems like a good sneaky way of catching COMMITs:

https://stackoverflow.com/a/6463800/790702

What he doesn't mention is that you should be able to catch the constraint violation in your code too, to stop the 2nd situation occurring.

Best Answer

Related Solutions

MySQL Query Optimization : Indexing and Pagination

Mysql – Disable explicit commits in JDBC, detect them in SQL, or put the database in a readonly state

Related Question