0

Trivially, a query like:

SELECT * FROM a, b;

...will have a result set that scales with O(a*b), so O(N^2).

But it seems as if, as soon as you join them with a foreign key, there's no way to make the query ever create more rows than is in the table containing the foreign key, not even as an intermediate step.

This seems true even with multiple levels of join: you never create more rows in your output than are in your most-populous input table, and no operation needs to be performed more than once per row in that table.

Well, other than any final sorting of the output, which could scale by O(nlog(n)) or so.

Am I missing any obvious scaling gotchas? Subqueries, maybe?

Union

The UNION command allows bigger output than input:

SELECT * FROM inputTable UNION ALL SELECT * FROM inputTable;

... which can be chained k times to make it k times longer than the biggest table, or something like:

SELECT * FROM
    inputTable,
    (SELECT '1' n UNION ALL SELECT '2') N,
    (SELECT 'a' l UNION ALL SELECT 'b') L;

... which makes an output 4 times the length of inputTable for only 2 UNION statements. So, OK, with UNION, we can make output that 2^k times, or if we nest deeper, scales as fast as we like.

But UNION still only multiplies the table size by a constant: it's O(kN), which is really still O(N). So is there anything else I'm missing? Any way that a join or subquery can scale worse than O(N)?

5
  • 1
    Now I will quibble with the meaning (or lack thereof) of "operations".
    – Rick James
    Commented Sep 2, 2022 at 2:28
  • "The product of the number of rows in the tables being JOINed." <- I agree, yup: the correct upper bound is likely the product of numrows of all sides of all joins. But I didn't ask for the value of the upper bound (wish I had!), but rather asked if the upper bound was max(table size), and got the correct answer (no, it's bigger than that). Changing the question now it's been correctly answered would be poor form. Commented Sep 2, 2022 at 4:11
  • @rickjames "operations"... good quibble, yeah. OK, time for background for the question! Answering dba.stackexchange.com/questions/316327 I realized I couldn't come up with a good example where lacking an index would scale terribly, for either CPU or mem. I was confident that worse-than-linearly-scaling queries were possible, but couldn't come up with one, and started to question if my knowledge was wrong. So "operations" was me thinking "if mem really doesn't scale that badly, maybe CPU can, in some weird cases? I'll throw that in too." It was a bad idea, and muddied the question. Commented Sep 2, 2022 at 4:23
  • 1
    @DewiMorgan - I like to count the number of rows touched. That is available via mysql.rjweb.org/doc.php/index_cookbook_mysql#handler_counts . The largest number in that output is sometimes the size of one of the tables (if there is no index). Or sometimes even a small multiple of such.
    – Rick James
    Commented Sep 2, 2022 at 5:58
  • 1
    @DewiMorgan - That brings up: `SELECT * FROM a JOIN b ON a.x = b.x -- With INDEX(x), it will, I think, show a Handler_read rows count of a + row count of b. Without any index, iw is likely to show the product of the two. Tack on an ORDER BY and it may need to write to a temp table and re-read it.
    – Rick James
    Commented Sep 2, 2022 at 6:02

1 Answer 1

2

Can a query with a join ever create more rows or require more operations than the largest [input] table involved? ... even when all joins are based on foreign keys?

Yes, it can. Example:

Table A
  (a_id, aname)

Table B
  (b_id, bname, a_id)

Table C
  (c_id, cname, a_id)

where a_id columns are FKs referencing table A.

Say table A has just 1 row, table B has 5 rows (all referencing the single row in A) and table C has 6 rows (all referencing the single row in A).

Then the following query will produce 30 (1*5*6 = 30) rows, as it is effectively a type of cross join:

select a.*, b.*, c.*
from a
  join b on b.a_id = a.a_id
  join c on c.a_id = a.a_id ;

So the (worst case) complexity is O(N*M) where N, M are the sizes of B and C.

In general, for a join of tables A, B, C, ..., X it can be O(Nb*Nc*...*Nx) where Nb, Nc, ..., Nx are the sizes of B, C, ... X.

1
  • Yay! So, where there are multiple foreign keys pointing to a common table, we can still get n^2. Exactly what I was after, thank you! I knew there was a way, but I'd almost convinced myself that I was just misremembering. Commented Sep 2, 2022 at 0:42

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.