4 ms·
> Example, you join on a column that isn't indexed. To find every matching row DB has to scan entire table. Hello O(n^2). It's only O(n^2) if your DBMS uses ne
by twic 9y ago
> Example, you join on a column that isn't indexed. To find every matching row DB has to scan entire table. Hello O(n^2).
It's only O(n^2) if your DBMS uses nested loops to do this join. If it uses a merge join it's O(n log n) (plus you get an order by for 'free'), and if it uses a hash join it's O(n).
MySQL, last I checked, only supported various forms of nested loops, but first-class databases like PostgreSQL support the others.
- bitexploder 9y agoGood point, and a good reason to learn how your DBMS of choice does common operations. Most query planners will explicitly tell you what yours is doing. I remember even back a long time ago MSSQL 7 had a nice GUI for its "query explain" and pgAdmin also gives a really nice graphical view of query plans, which really helps visualize when it is looping, doing hash lookups, etc. I suppose that would be part of the recommendation for learning: use a graphical query plan view if you can find a client that supports it :) http://www.postgresonline.com/journal/archives/27-Reading-PgAdmin-Graphical-Explain-Plans.html http://www.postgresonline.com/journal/archives/27-Reading-Pg... (example pictures if anyone reading this hasn't seen it before), it is pretty cool.