6 ms·

This may help you mentally map in brain what happens. But this is all table scanning and doesn't include indexes, which organize data in a tree. When you do SQL

by jve 5y ago

This may help you mentally map in brain what happens. But this is all table scanning and doesn't include indexes, which organize data in a tree. When you do SQL, you should consider whether table will contain thousands or millions of rows. If millions, you have to think how that JOIN or WHERE will take indexes into account.

jiggawatts 5y ago
In a way, it is even deceptive, because naive programmers might be lead to think that repeated(!) table scanning is what real database engines do. It's actually very rare that this happens. For example, SQL Server will create a temporary index on the fly if one is missing. It can create B-Tree, Hash, and Bitmap indexes which might be unexpected for some people because only B-Tree indexes can be created "permanently". So in some ways database engines do even more than just use statically defined indexes.
- tluyben2 5y ago
  > It's actually very rare that this happens So I have a little consultancy gig for a few decades now where I spend a few days a month optimising bad software for performance (it is what I like; I don’t do anything else but ‘make shit faster’). I can tell you that the the past 10 years 99% of optimisations I did are fixing MySQL queries and indexes that table scan. I had projects that literally have table scanning queries over 50% of the queries ran. The result, as you know but apparently is not very common knowledge, is that these sites and apps run to a grinding halt (after incurring bizarre bills on aws rds; I moved many app from $100k/month bills to $10/month) when even a little traffic comes in. Or; table scans should be rare but are not. Edit; removed ‘time’ as that was not a good way of expressing this
  - gunshowmo 5y ago
    Would love to read about some examples / strategies in a blog post some day!
  - Brakenshire 5y ago
    How do you build your intuition about creating queries in a way to avoid this? Is it a matter of having a conceptual model of relational algebra and the way the different db engines work, or is it more an accumulation of heuristics over time for what probably will cause problems, and an iterative process of using EXPLAIN, adjusting the query and seeing what happens?
    - tluyben2 5y ago
      I am old :) But experience is a big thing; I can sniff by just skimming the table definitions where probably something is very wrong. In uni in the 90s I studied both relational theory and formal methods and I had to spend a lot of time figuring out and fixing complexity; if you take a university level book on big O complexity and work through it, you will have a good feeling what software can and cannot do and in what way. That has not really changed; we have more efficient and more cache, we have improved algorithms, but things that cannot be looked up in O(1) are still dangerous and possibly can incur enormous IO even with only a few million records. Naive developers see that things are blazingly fast locally on their laptops and that’s it. I have met, especially in the last few years (In my bubble this is getting worse, quite fast), quite a lot of lead devs that actually do not know what an index is for and so I see entire dbs without any or only on the id field. I know people (for some reasons) do not like ORMs that create tables and indexes, but it would prevent many rookie mistakes if they did.
      - jiggawatts 5y ago
        I can’t remember the last time I came across a non-CotS database schema that has secondary indexes in a significant number. Like more than half a dozen for a hundred tables or more. I’ve never seen a database use “advanced” features like clustered columnstore or even just page compression. I just have an email in my inbox from this morning from a small vendor that “doesn’t recommend” columnstore for a database containing 10 TB of numeric metrics in one table. That would compress to a few gigabytes and query times would go from minutes to milliseconds. But they “don’t support it”. Which I now translate to: “we haven’t even flipped through the manual and when we googled it in a panic we didn’t understand it.” This is how your data is being managed at huge enterprises and government agencies around the world.
- zasdffaa 5y ago
  > For example, SQL Server will create a temporary index on the fly if one is missing err, I may be misunderstanding but can you explain why you feel this? I have never (IME) seen MSSQL do this and it wouldn't make sense because constructing an index needs a table scan plus a lot of work on top. Just doing a hash join is simply the better option. I mean it would be nice at times but there are traps to this which is why (again AFAICS) it's not done and would be unsafe to do without a lot of info about resources and future expected queries which the query planner just doesn't have. Happy to be set right on this.
  - jve 5y ago
    > Just doing a hash join is simply the better option. Maybe he meant just that - hash join has to populate hashtable before joining. Regarding B-Tree index, perhaps he thought Automatic Index management - https://docs.microsoft.com/en-us/sql/relational-databases/automatic-tuning/automatic-tuning?view=sql-server-ver15#automatic-index-management https://docs.microsoft.com/en-us/sql/relational-databases/au... - but it must be enabled explicitly. But I don't feel like it is "on-the-fly". Rather in-background.
  - jiggawatts 5y ago
    It won't create an index you can see in the GUI or query via "sys.indexes" or anything like that. It's a temporary object, much like a temporary table that exists only in the scope of the query. As another comment mentioned, this is what a hash-join does internally: it builds a temporary "hash index" of one input, and then uses it to look up rows while scanning through the other input. If you looks at the query plans in SSMS, you'll occasionally see bitmap indexes as well. The equivalent of a standard B-Tree index that you would create permanently is the "Index Spool" operator. You'll also see "Table Spool", which is basically a temporary heap. The example in the original article was the equivalent of this loop: foreach( a in table_a ) { foreach( b in table_b ) { if ( a.id == b.aid ) ... } } That's hideously inefficient. Most databases will automatically do something like: var a_hash = new Hashtable( a.row_count ) foreach( a in table_a ) { a_hash.add( a.id, a ) } foreach( b in table_b ) { if ( a_hash.lookup( b.aid )) ... } The clever part in all of this is that you can do this two ways: build a hashtable of "a" and lookup "b" rows in it, OR build a table of "b" and lookup "a" rows in it. They're equivalent, but the performance can be wildly different. RDMBS query planners have the job of figuring out which to pick. Even if you think you can outperform the database by writing code like the above in Java or C# or whatever, you won't write out every combination and have the statistics available to choose. The database engine can and does. SQL Server can do both steps in parallel across all CPU cores which is a topic of several PHD-level research papers. For example, hash tables can have performance issues if the same key occurs too often (e.g. many NULL columns). Balancing this across multiple cores is... complicated.
deleted 5y ago
[deleted]

by jve 5y ago

jiggawatts 5y ago

In a way, it is even deceptive, because naive programmers might be lead to think that repeated(!) table scanning is what real database engines do. It's actually very rare that this happens. For example, SQL Server will create a temporary index on the fly if one is missing. It can create B-Tree, Hash, and Bitmap indexes which might be unexpected for some people because only B-Tree indexes can be created "permanently". So in some ways database engines do even more than just use statically defined indexes.

tluyben2 5y ago
> It's actually very rare that this happens So I have a little consultancy gig for a few decades now where I spend a few days a month optimising bad software for performance (it is what I like; I don’t do anything else but ‘make shit faster’). I can tell you that the the past 10 years 99% of optimisations I did are fixing MySQL queries and indexes that table scan. I had projects that literally have table scanning queries over 50% of the queries ran. The result, as you know but apparently is not very common knowledge, is that these sites and apps run to a grinding halt (after incurring bizarre bills on aws rds; I moved many app from $100k/month bills to $10/month) when even a little traffic comes in. Or; table scans should be rare but are not. Edit; removed ‘time’ as that was not a good way of expressing this
- gunshowmo 5y ago
  Would love to read about some examples / strategies in a blog post some day!
- Brakenshire 5y ago
  How do you build your intuition about creating queries in a way to avoid this? Is it a matter of having a conceptual model of relational algebra and the way the different db engines work, or is it more an accumulation of heuristics over time for what probably will cause problems, and an iterative process of using EXPLAIN, adjusting the query and seeing what happens?
  - tluyben2 5y ago
    I am old :) But experience is a big thing; I can sniff by just skimming the table definitions where probably something is very wrong. In uni in the 90s I studied both relational theory and formal methods and I had to spend a lot of time figuring out and fixing complexity; if you take a university level book on big O complexity and work through it, you will have a good feeling what software can and cannot do and in what way. That has not really changed; we have more efficient and more cache, we have improved algorithms, but things that cannot be looked up in O(1) are still dangerous and possibly can incur enormous IO even with only a few million records. Naive developers see that things are blazingly fast locally on their laptops and that’s it. I have met, especially in the last few years (In my bubble this is getting worse, quite fast), quite a lot of lead devs that actually do not know what an index is for and so I see entire dbs without any or only on the id field. I know people (for some reasons) do not like ORMs that create tables and indexes, but it would prevent many rookie mistakes if they did.
    - jiggawatts 5y ago
      I can’t remember the last time I came across a non-CotS database schema that has secondary indexes in a significant number. Like more than half a dozen for a hundred tables or more. I’ve never seen a database use “advanced” features like clustered columnstore or even just page compression. I just have an email in my inbox from this morning from a small vendor that “doesn’t recommend” columnstore for a database containing 10 TB of numeric metrics in one table. That would compress to a few gigabytes and query times would go from minutes to milliseconds. But they “don’t support it”. Which I now translate to: “we haven’t even flipped through the manual and when we googled it in a panic we didn’t understand it.” This is how your data is being managed at huge enterprises and government agencies around the world.
zasdffaa 5y ago
> For example, SQL Server will create a temporary index on the fly if one is missing err, I may be misunderstanding but can you explain why you feel this? I have never (IME) seen MSSQL do this and it wouldn't make sense because constructing an index needs a table scan plus a lot of work on top. Just doing a hash join is simply the better option. I mean it would be nice at times but there are traps to this which is why (again AFAICS) it's not done and would be unsafe to do without a lot of info about resources and future expected queries which the query planner just doesn't have. Happy to be set right on this.
- jve 5y ago
  > Just doing a hash join is simply the better option. Maybe he meant just that - hash join has to populate hashtable before joining. Regarding B-Tree index, perhaps he thought Automatic Index management - https://docs.microsoft.com/en-us/sql/relational-databases/automatic-tuning/automatic-tuning?view=sql-server-ver15#automatic-index-management https://docs.microsoft.com/en-us/sql/relational-databases/au... - but it must be enabled explicitly. But I don't feel like it is "on-the-fly". Rather in-background.
- jiggawatts 5y ago
  It won't create an index you can see in the GUI or query via "sys.indexes" or anything like that. It's a temporary object, much like a temporary table that exists only in the scope of the query. As another comment mentioned, this is what a hash-join does internally: it builds a temporary "hash index" of one input, and then uses it to look up rows while scanning through the other input. If you looks at the query plans in SSMS, you'll occasionally see bitmap indexes as well. The equivalent of a standard B-Tree index that you would create permanently is the "Index Spool" operator. You'll also see "Table Spool", which is basically a temporary heap. The example in the original article was the equivalent of this loop: foreach( a in table_a ) { foreach( b in table_b ) { if ( a.id == b.aid ) ... } } That's hideously inefficient. Most databases will automatically do something like: var a_hash = new Hashtable( a.row_count ) foreach( a in table_a ) { a_hash.add( a.id, a ) } foreach( b in table_b ) { if ( a_hash.lookup( b.aid )) ... } The clever part in all of this is that you can do this two ways: build a hashtable of "a" and lookup "b" rows in it, OR build a table of "b" and lookup "a" rows in it. They're equivalent, but the performance can be wildly different. RDMBS query planners have the job of figuring out which to pick. Even if you think you can outperform the database by writing code like the above in Java or C# or whatever, you won't write out every combination and have the statistics available to choose. The database engine can and does. SQL Server can do both steps in parallel across all CPU cores which is a topic of several PHD-level research papers. For example, hash tables can have performance issues if the same key occurs too often (e.g. many NULL columns). Balancing this across multiple cores is... complicated.

deleted 5y ago

[deleted]