A data point for discussion "Static vs. dynamic typing: on using compiler to find bugs":
Static analysis has not proven to be helpful in finding bugs. We cannot call to mind a single problem in SQLite that was detected by static analysis that was not first seen by one of the other testing methods described above. On the other hand, we have on occasion introduced new bugs in our efforts to get SQLite to compile without warnings. </quote>
It's worth noting that C can barely be considered static typing. If SQLite were written in, say, Haskell, I doubt it would need millions of lines of test code, just to make sure it frees everything it mallocs.
I'm pretty ignorant about functional languages, but how does a language like Haskell handle allocation failures? I'm curious how well it would work in the embedded space.
Most of the 'static analysis' already takes place during coding, when your (incremental) compiler screams DOES NOT COMPILE. I doubt the developers of SqlLite haven't seen that sort of message quite often (Eclipse definitely shows me the red curly line often enough).
This is really a very small subset of static analysis- GCC compiler warnings. I am sure the developers appreciate when their program fails to compile because the compiler statically notices a bug that would cause a runtime error in a more dynamic language. They might be able to productively use more sophisticated static analyses tools.
That's not to say that static analysis didn't find any problems at all. Just that the other, more extensive, methods found them first. Which speaks well for their tests. If anything, I would say that this speaks more for good static analysis, since they clearly put an enormous amount of effort into developing these tests. Most commercial software can't justify anything close to that. (kind of ironic, really)
Hypothetically, what would it take for you to believe that static analysis doesn't work? Because, as lame as C's typechecking is, this remark sounds to me a lot like the "no true Scotsman" fallacy.
The sort of testing that the SQLite developers do is, while depressingly uncommon, not that unreasonable for any sort of software been around for a few years. If your bug fixing methodology is "write test to reproduce bug, then fix; repeat" you end up with a pile of test cases as a result.
Wow, astounding ignorance/ungratefulness on static analysis. Coverity (a static analysis tool) found many defects in the code (17 fixed). The number of defects per KLOC for SQLite is not that great compared with other projects. KDE is actually much better: http://scan.coverity.com/rungAll.html
Engler (whose students founded Coverity) et al. had an OSDI "best paper" last year on using static analysis (with constraint solvers etc.) to automatically generate test cases, which actually beats hand written test cases for glibc with years of development.
All I can think when reading this is: can the test suite for MySQL possibly be this good? I've read the various results found in a search for "mysql test suite", but I don't get the same feeling that I do when reading SQLite's description.
"The SQL Logic Test or SLT test harness is used to run huge numbers of SQL statements against both SQLite and several other SQL database engines and verify that they all get the same answers. SLT currently compares SQLite against PostgreSQL, MySQL, and Microsoft SQL Server. SLT runs 7.2 million queries comprising 1.12GB of test data."
It seems MySQL could share a good chunk of SQLite's tests. If I were MySQL, I'd run these in addition to their own test suites. It was nice of SQLite to set it up for them ;)
Hmm, isn't their example in 7.0 wrong? The opposite of "a>b" (in C, anyway, AFAIK) isn't "a<=b", because if a==b==NaN both expressions are false (right?).
Just goes to show how hard testing all cases is! How many cases do you need to get full branch coverage on "a>b && c!=25"? I'm thinking 5, but I'm not very sure of that.
The sad truth is that there are bugs in SQLite which aren't being fixed.
For instance, .quit doesn't exit the program when running a script from the command-line (or C's system() ) via .init.
Also, have more than 2 inner joins and a query takes 10 minutes. I fixed this by writing some custom queries.
D. Richard Hipp (the author) refuses to accept these are bugs, when they obviously are. Also, people like Mozilla get first call on bug fixes, so the 'little guy' gets no support for no $$ - I read it costs $75,000 for 'special' status and $1500 a year for support.
The sad truth is that there are bugs in everything which aren't getting fixed. If a well-written patch were submitted, would it be ignored? Or are they just not placing priority on it themselves?
I can understand if somebody who wrote an incredibly useful system and released it into the public domain isn't always willing to take the time to fix bugs they consider minor, without being compensated to do so. (I'm glad he's sharing it, at all.) I don't think the issue is Ulrich Drepper-like behavior here.
About the inner joins - SQLite can be small because it doesn't have the tremendous amount of query optimization that e.g. Postgresql does. That's like complaining that a bicycle makes a lousy tow truck; significantly improving its query optimizer would require changing it into a completely different kind of tool, and a big part of its utility comes from being small enough for embedded use.
I think a patch would be looked at, but he'd have to admit it was a bug to accept it.
My complaint isn't that he won't fix the bug for free, it's that he won't acknowledge it's a bug, and thus won't fix it even in a year's time.
Also, I'd pay for the bug to be fixed, by hours, but I saw it costs from $1500 to $75,000 for special service. So I had to fix the bug myself.
The .quit bug, I found already mentioned on the Internet, but unsolved. I fixed that one myself with a simple hack [.quit = exit(0) ] and recompiled SQLite.
"
About the inner joins - SQLite can be small because it doesn't have the tremendous amount of query optimization that e.g. Postgresql does. That's like complaining that a bicycle makes a lousy tow truck; significantly improving its query optimizer would require changing it into a completely different kind of tool, and a big part of its utility comes from being small enough for embedded use.
"
What I realised is that some free libraries are worth the effort of having to cope with odd bugs. For instance, I'd rather spend 5 hours writing a 'cascading filter' which does its own inner joining but on top of SQLite, than 6 months writing an SQL database engine!
Also, I didn't change a line of SQLite code, it's all in my queries.
Basically, I can't go into it properly because the project is confidential, and I can't think of a similiar table example.
In SQLite:
2 inner joins took about 10 seconds.
3 inner joins in one query were taking 10 minutes.
I was using inner joins to filter - ie shrink the table - when a row had multiple fields in one column (eg, a house has 1 front door but 3 bathrooms).
What should happen in SQLite is that each progressive inner join should make the search table smaller, not bigger. So a 3-join query should be quicker than a 2-join query.
The solution was to create some temp tables, do 1 inner join at a time, and shrink the temp tables down myself.
Now a query with 4 inner joins takes 8 seconds, without changing a line of SQLite. You can't tell me that's not a bug! :-)
Offtopic, but the "Test Coverage" section shows that contrary to what Rob Pike of Plan9 says http://news.ycombinator.com/item?id=596882 the pre-processor is actually a good thing.
A data point for discussion "Static vs. dynamic typing: on using compiler to find bugs":
Static analysis has not proven to be helpful in finding bugs. We cannot call to mind a single problem in SQLite that was detected by static analysis that was not first seen by one of the other testing methods described above. On the other hand, we have on occasion introduced new bugs in our efforts to get SQLite to compile without warnings. </quote>
It's worth noting that C can barely be considered static typing. If SQLite were written in, say, Haskell, I doubt it would need millions of lines of test code, just to make sure it frees everything it mallocs.
I'm pretty ignorant about functional languages, but how does a language like Haskell handle allocation failures? I'm curious how well it would work in the embedded space.
3 replies →
Most of the 'static analysis' already takes place during coding, when your (incremental) compiler screams DOES NOT COMPILE. I doubt the developers of SqlLite haven't seen that sort of message quite often (Eclipse definitely shows me the red curly line often enough).
This is really a very small subset of static analysis- GCC compiler warnings. I am sure the developers appreciate when their program fails to compile because the compiler statically notices a bug that would cause a runtime error in a more dynamic language. They might be able to productively use more sophisticated static analyses tools.
That's not to say that static analysis didn't find any problems at all. Just that the other, more extensive, methods found them first. Which speaks well for their tests. If anything, I would say that this speaks more for good static analysis, since they clearly put an enormous amount of effort into developing these tests. Most commercial software can't justify anything close to that. (kind of ironic, really)
Hypothetically, what would it take for you to believe that static analysis doesn't work? Because, as lame as C's typechecking is, this remark sounds to me a lot like the "no true Scotsman" fallacy.
The sort of testing that the SQLite developers do is, while depressingly uncommon, not that unreasonable for any sort of software been around for a few years. If your bug fixing methodology is "write test to reproduce bug, then fix; repeat" you end up with a pile of test cases as a result.
2 replies →
Wow, astounding ignorance/ungratefulness on static analysis. Coverity (a static analysis tool) found many defects in the code (17 fixed). The number of defects per KLOC for SQLite is not that great compared with other projects. KDE is actually much better: http://scan.coverity.com/rungAll.html
Engler (whose students founded Coverity) et al. had an OSDI "best paper" last year on using static analysis (with constraint solvers etc.) to automatically generate test cases, which actually beats hand written test cases for glibc with years of development.
http://www.stanford.edu/~engler/klee-osdi-2008.pdf
All I can think when reading this is: can the test suite for MySQL possibly be this good? I've read the various results found in a search for "mysql test suite", but I don't get the same feeling that I do when reading SQLite's description.
"The SQL Logic Test or SLT test harness is used to run huge numbers of SQL statements against both SQLite and several other SQL database engines and verify that they all get the same answers. SLT currently compares SQLite against PostgreSQL, MySQL, and Microsoft SQL Server. SLT runs 7.2 million queries comprising 1.12GB of test data."
It seems MySQL could share a good chunk of SQLite's tests. If I were MySQL, I'd run these in addition to their own test suites. It was nice of SQLite to set it up for them ;)
What a wonderful piece of software. I dream to have one day a project as neat and good as SQLite.
Hmm, isn't their example in 7.0 wrong? The opposite of "a>b" (in C, anyway, AFAIK) isn't "a<=b", because if a==b==NaN both expressions are false (right?).
Just goes to show how hard testing all cases is! How many cases do you need to get full branch coverage on "a>b && c!=25"? I'm thinking 5, but I'm not very sure of that.
Maybe a and b are integers and can't be NaN.
Regarding the large quantity of Tcl (not TCL..ugh) test scripts, D. Richard Hipp is also a member of the Tcl Core Team:
http://en.wikipedia.org/wiki/D._Richard_Hipp
Hipp is also the guy behind Fossil[1] (a new DVCS) and CVSTrac[2] (the inspiration for Trac).
1- http://www.fossil-scm.org
2- http://www.cvstrac.org
The sad truth is that there are bugs in SQLite which aren't being fixed.
For instance, .quit doesn't exit the program when running a script from the command-line (or C's system() ) via .init.
Also, have more than 2 inner joins and a query takes 10 minutes. I fixed this by writing some custom queries.
D. Richard Hipp (the author) refuses to accept these are bugs, when they obviously are. Also, people like Mozilla get first call on bug fixes, so the 'little guy' gets no support for no $$ - I read it costs $75,000 for 'special' status and $1500 a year for support.
The sad truth is that there are bugs in everything which aren't getting fixed. If a well-written patch were submitted, would it be ignored? Or are they just not placing priority on it themselves?
I can understand if somebody who wrote an incredibly useful system and released it into the public domain isn't always willing to take the time to fix bugs they consider minor, without being compensated to do so. (I'm glad he's sharing it, at all.) I don't think the issue is Ulrich Drepper-like behavior here.
About the inner joins - SQLite can be small because it doesn't have the tremendous amount of query optimization that e.g. Postgresql does. That's like complaining that a bicycle makes a lousy tow truck; significantly improving its query optimizer would require changing it into a completely different kind of tool, and a big part of its utility comes from being small enough for embedded use.
I think a patch would be looked at, but he'd have to admit it was a bug to accept it.
My complaint isn't that he won't fix the bug for free, it's that he won't acknowledge it's a bug, and thus won't fix it even in a year's time.
Also, I'd pay for the bug to be fixed, by hours, but I saw it costs from $1500 to $75,000 for special service. So I had to fix the bug myself.
The .quit bug, I found already mentioned on the Internet, but unsolved. I fixed that one myself with a simple hack [.quit = exit(0) ] and recompiled SQLite.
" About the inner joins - SQLite can be small because it doesn't have the tremendous amount of query optimization that e.g. Postgresql does. That's like complaining that a bicycle makes a lousy tow truck; significantly improving its query optimizer would require changing it into a completely different kind of tool, and a big part of its utility comes from being small enough for embedded use. "
What I realised is that some free libraries are worth the effort of having to cope with odd bugs. For instance, I'd rather spend 5 hours writing a 'cascading filter' which does its own inner joining but on top of SQLite, than 6 months writing an SQL database engine!
Also, I didn't change a line of SQLite code, it's all in my queries.
Can you expand a bit on the inner join issue, how you fixed it, and when and how the author refused to accept that it was a bug?
Basically, I can't go into it properly because the project is confidential, and I can't think of a similiar table example.
In SQLite:
2 inner joins took about 10 seconds. 3 inner joins in one query were taking 10 minutes.
I was using inner joins to filter - ie shrink the table - when a row had multiple fields in one column (eg, a house has 1 front door but 3 bathrooms).
What should happen in SQLite is that each progressive inner join should make the search table smaller, not bigger. So a 3-join query should be quicker than a 2-join query.
The solution was to create some temp tables, do 1 inner join at a time, and shrink the temp tables down myself.
Now a query with 4 inner joins takes 8 seconds, without changing a line of SQLite. You can't tell me that's not a bug! :-)
2 replies →
Offtopic, but the "Test Coverage" section shows that contrary to what Rob Pike of Plan9 says http://news.ycombinator.com/item?id=596882 the pre-processor is actually a good thing.