1

Questions

I put my questions first, so that it is easier to understand the question. I have two working queries at the end, but I fear they are not very efficient with data sets larger than what I have at the moment. What are my best options to create an efficient query in the below case?

Description

I have a MySQL database with a table my_data. In this table I have two rows: id and version. I also have an Android app, working as a client. The client contains the same columns, but not necessarily the same versions of the data. The client should thus be able to send its current ids and versions to the server and get back only the rows that has a higher version than what is currently on the client.

Example

Server data:

mysql> SELECT id, version FROM my_data;
+-----+---------+
| id  | version |
+-----+---------+
|   1 |       0 |
|   2 |       1 |
|   3 |       2 | <-- Should be selected with the example client data below.
|   4 |       0 |
|   5 |       1 |
|   6 |       0 |
|   7 |       1 | <-- Should be selected with the example client data below.
|   8 |       1 |
|   9 |       4 | <-- Should be selected with the example client data below.
|  10 |       1 |
+-----+---------+
10 rows in set (0.00 sec)

Data sent from the client:

The client then queries the server with the following example data. It is arriving as JSON, but the format not matter for this question.

{
    "my_data": [
        {
            "id": 1,
            "version": 0
        },
        {
            "id": 2,
            "version": 1
        },
        {
            "id": 3,
            "version": 0 <-- Lower than server version (2).
        },
        {
            "id": 4,
            "version": 0
        },
        {
            "id": 5,
            "version": 1
        },
        {
            "id": 6,
            "version": 0
        },
        {
            "id": 7,
            "version": 0 <-- Lower than server version (1).
        },
        {
            "id": 8,
            "version": 1
        },
        {
            "id": 9,
            "version": 2 <-- Lower than server version (4).
        },
        {
            "id": 10,
            "version": 1
        }
    ]
}

Desired result from the sample data above:

The resulting data should be the rows in which the version in the database on the server side is greater than the data with the corresponding id in the incoming data set.

mysql> <INSERT PROPER QUERY HERE>;
+-----+---------+
| id  | version |
+-----+---------+
|   3 |       2 | <-- Version on the client was 0.
|   7 |       1 | <-- Version on the client was 0.
|   9 |       4 | <-- Version on the client was 2.
+-----+---------+

Working solution

One working solution is to create the following query based on the client data set.

SELECT * FROM my_data WHERE
    (id = 1 AND version > 0) OR
    (id = 2 AND version > 1) OR
    (id = 3 AND version > 0) OR
    (id = 4 AND version > 0) OR
    (id = 5 AND version > 1) OR
    (id = 6 AND version > 0) OR
    (id = 7 AND version > 0) OR
    (id = 8 AND version > 1) OR
    (id = 9 AND version > 2) OR
    (id = 10 AND version > 1);

My server side is php, so creating this query when I have the JSON data is no problem. For a small data set, this query is fast. The data set is organic, however, and will increase with time, up to maybe 1000 rows on both the client and the server side. At the same time, the number of clients is likely to grow as well, hopefully up to around 10 000 or maybe more, thus I am not sure that this is the most efficient solution for performing this query.

Another working solution

Here is another working solution using virtual tables. Will this in any way be more efficient than the multiple OR solution if the data set is a lot larger?

CREATE TEMPORARY TABLE my_data_virtual(id INTEGER NOT NULL, version TINYINT(3) NOT NULL);

INSERT INTO my_data_virtual VALUES
    (1,0), (2,1), (3,0), (4,0), (5,1),
    (6,0), (7,0), (8,1), (9,2), (10,1);

SELECT md.id, md.version
    FROM my_data AS md
    INNER JOIN my_data_virtual AS mdv
        ON md.id = mvd.id AND md.id > mvd.id;
3
  • 1
    I like the "virtual" table solution you use. Test it with larger tables (eg. fill the existing table with some 10s of thousands of rows and then test with temporary tables of various sizes, say 10, 100, 1000 rows.) You can eexperiment also with adding an index on the temp table on (id, version), just before running the SELECT query. A similar index on the data table should be added as well, if the (id) is not already the PK of the data table. Nov 19, 2015 at 18:16
  • 1
    You can add one more condition to your query like .. WHERE id IN (1,2,...,10) AND (<the list of ORs>) - to hint mysql how to properly utilize index on (id) or (id, version) (the second one is better if your version supports Index Condition Pushdown) - expecting that your query actually selects only a small subset of the rows, if it returns more than 50% of the table then full scan is the best way.
    – jkavalik
    Nov 20, 2015 at 8:16
  • Thanks for the comments. I have run a series of tests with both approaches, see my answer below, also with WHERE id IN (1,2...,10) AND <OR queries>. The added WHERE statements seemed to have little effect on the run times, but it did affect the multiple OR approach for the largest data sets. The client data should always be similar to the data on the server, so the returned number of rows should be maximum 5-10 % or so. This is not tested in the below test runs. Nov 21, 2015 at 12:06

2 Answers 2

2

I ran some tests based on the suggestions I got from you guys, using the MySQLdb and timeit modules in Python. I created 5 tables: test_100, test_500, test_1000, test_5000 and test_10000. All the databases were given a single table, data, which contained the following columns.

+-------------+---------+------+-----+---------+----------------+
| Field       | Type    | Null | Key | Default | Extra          |
+-------------+---------+------+-----+---------+----------------+
| id          | int(11) | NO   | PRI | NULL    | auto_increment |
| version     | int(11) | NO   |     | 0       |                |
| description | text    | YES  |     | NULL    |                |
+-------------+---------+------+-----+---------+----------------+

The tables in the databases were then filled with random versions from 0 to 5 and a semi-random amount of lorem ipsum text. The test_100.data table got 100 rows, the test_500.data table got 500 rows and so forth. I then ran test for both the query using nested OR statements and using a temporary table with all ids and random version between 0 and 5.

Results

Results for nested OR query. Number of repeats for each n was 1000.

+----------+-------------+-------------+-------------+-------------+-------------+
|          | n = 100     | n = 500     | n = 1000    | n = 5000    | n = 10000   |
+----------+-------------+-------------+-------------+-------------+-------------+
| max      | 0.00719     | 0.02213     | 0.04325     | 1.75707     | 8.91687     |
| min      | 0.00077     | 0.00781     | 0.02696     | 0.63565     | 5.29613     |
| median   | 0.00100     | 0.00917     | 0.02996     | 0.82732     | 5.92217     |
| average  | 0.00111     | 0.01001     | 0.03057     | 0.82540     | 5.89577     |
+----------+-------------+-------------+-------------+-------------+-------------+

Results for temporary table query. Number of repeats for each n was 1000.

+----------+-------------+-------------+-------------+-------------+-------------+
|          | n = 100     | n = 500     | n = 1000    | n = 5000    | n = 10000   |
+----------+-------------+-------------+-------------+-------------+-------------+
| max      | 0.06352     | 0.07192     | 0.08798     | 0.28648     | 0.26939     |
| min      | 0.02119     | 0.02027     | 0.03126     | 0.07677     | 0.12269     |
| median   | 0.03075     | 0.03210     | 0.043833    | 0.10068     | 0.15839     |
| average  | 0.03121     | 0.03258     | 0.044968    | 0.10342     | 0.16153     |
+----------+-------------+-------------+-------------+-------------+-------------+

It seems that using nested OR queries is faster up to about n = 1000. From there on, the the nested OR scales badly and the temporary table approach wins solidly. In my case I am likely to have a maximum of around 1000 rows, so it seems that I can choose between these two approaches relatively freely.

I will probably go for the temporary table approach in case my data set should become larger than expected. The payload is small in any case.

Notes

  • Since the timeit module in Python is a bit ticklish, the database is opened and closed for each run/repeat. This might produce some overhead to the timings.
  • The queries for the temporary table approach were done in 3 steps: 1 for creating the temporary, 1 for inserting the data and 1 for joining the tables.
  • The creation of the queries are not part of the timing; they are created outside of the Python timeit call.
  • Since both the versions in the inserted data and the random "client" data are randomly chosen between 0 and 5, it is likely that between 33 % and 50 % of the rows are selected. I have not verified this. This is not really the case I have, as the client data will at any point have almost the same data as the server.
  • I tried adding WHERE id IN (1,2,3...,10) on both the temporary table approach and the nested OR approach, but it neither sped things up nor slowed them down in any of the tests, except for the larger data sets and the multiple OR approach. Here, the times were slightly lower than without this WHERE statement.
2
  • Yes, the WHERE id IN() was meant to help indexability of the query you showed - max. tens of ORs. Try adding engine=memory and proper indexes to your temporary table create statement to make it even faster - analyze the SELECT part with EXPLAIN.
    – jkavalik
    Nov 22, 2015 at 12:58
  • Compare sqlfiddle.com/#!9/5d8e16/1 and sqlfiddle.com/#!9/95696/1 - the indexes will probably not make much difference for your case, but the memory engine might make it faster even for smaller n (without it the temp table is created as MyISAM or InnoDB depending on default engine - and is at least partially written to disk so creating it takes more time).
    – jkavalik
    Nov 22, 2015 at 13:10
1

I don't have a direct answer to your question. I do have a suggestion, depending upon what you intend to do with the query results.

If the results are staying entirely within the database server -- for example, if the query is just a subquery of an insert statement -- your "Another working solution" is what I'd intuitively pick.

If the web server is going to make use of the results -- for example, if it's going to read the query results and send them to the client -- I'd prefer to put the load on the web server. Web servers are more scalable than database servers (with load balancers). I'd load the client data into a map, query the database to get the max version for each ID (select id, max(version) from my_data group by id), iterate through the result rows, and look up in the map whether the client has an older value for each row. Build the results into a new JSON object and send that to the client at the end. Most of the work would happen on the web server, and I don't think it could be any less efficient than inserting all the client data into the database and asking that server to do it.

1
  • Yes, this could make sense if I only were to return the id and version to the client. I am going to return a lot more data from the database, however, but I only discussed the id and version columns since the dictate which rows that are to be selected and returned. If I select everything first and put it into a map on the web server this could pose a huge load on the web server, since I have several TEXT fields and VARCHAR fields with lots of data. I did not mention it since it did not really affect the questions I had, so you could not know that that was the case :-) Nov 21, 2015 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.