6 ms·

How SQLite is tested

176 points by antonios 14y ago

lrem 14y ago
You should definitely see drh present it in person. He's giving a talk about it in universities around the world, seen it a couple years back, in Poland. It's incredible what effort goes into reliability of what seems such a small thing. Btw, the very same day he persuaded me to move to Fossil. Edit: just to be clear, you should see it for all the good ideas he's explaining. Not for some marketing of a piece o of software.
- RDeckard 14y ago
  link?
  - lrem 14y ago
    Hmmm, despite what uni authorities said, there is no recording of that particular talk available. So I have no specific advice, apart from bland "search YouTube" or "ask by email".
    - cfn 14y ago
      Here is an old one (2006) at Google: http://www.youtube.com/watch?v=jN_YdMdjVpU http://www.youtube.com/watch?v=jN_YdMdjVpU
tedunangst 14y ago
Unfortunately, 100% testing is only effective if you can detect 100% of the errors generated. The only bug I found in sqlite was an off by one in the btree code that was mostly harmless, unless your memory allocator was particularly fussy. I only found the bug, never quite understood it, and after seeing how disturbing the fix was decided some things were best left unlearned. http://www2.sqlite.org/cgi/src/fdiff?v1=fa113d624d38bcb36700a0244b47f39d57d34efb&v2=8cab7c66c822ae9c37c59a923ffec81927583ee2 http://www2.sqlite.org/cgi/src/fdiff?v1=fa113d624d38bcb36700... That said, sqlite is one of the most reliable and better designed libraries I've used. Software is hard.
- dbaupp 14y ago
  100% testing is effective, just not 100% effective. And 100% testing is strictly better than 99% testing is strictly better than 50% testing (when considering only its bug detecting capabilities).
  - jemfinch 14y ago
    I'm glad you appended "when considering only its bug detecting capabilities". Something like SQLite, whose functionality is largely static, definitely benefits from the additional test coverage, but the majority of code out there--code that's constantly evolving, code to which functionality is frequently added and removed--is too often prematurely cast in stone by overzealous testers, making maintenance and evolution significantly more difficult than it ought to be. In a lot of cases, too much test coverage actually reduces the value of the code.
    - josephlord 14y ago
      There is a strong case that more tests allow you to make changes to the code with some confidence that there won't be unintended side effects. Now maybe SQLite's level isn't appropriate in most cases but that doesn't mean high levels of code coverage are bad. It can also give confidence to upgrade underlying frameworks or libraries
- moron 14y ago
  "Unfortunately, 100% testing is only effective if you can detect 100% of the errors generated." Wow, the word "only" is doing a lot of work in that sentence. Because these tests don't find literally every single problem, you would honestly say they are not effective?
josephlord 14y ago
Is there any more widely deployed software in the world than SQLite? Multiple copies (browsers, language runtimes, embedded in other software) on many computers and built into most smartphones and its probably in quite a few TVs and other devices too. Very successful invisible (to non-developers) software.
- tsahyt 14y ago
  Not just successful, it's really good too! The API is rather easy to use, it's lightweight and (for small to medium sized databases) it performs really well. Not really suprising it is so widely used.
- mhd 14y ago
  > Is there any more widely deployed software in the world than SQLite? zlib or libjepg, maybe.
  - mrich 14y ago
    libc (both GNU and BSD)
    - lrem 14y ago
      A funny thing here... If you count the number of active copies, this may not be true. Usually you don't see ten apps in one system coming with their own version of libc. This may pretty well be true for sqlite.
    - deleted 14y ago
      [deleted]
- wickedchicken 14y ago
  The BSD networking stack.
  - josephlord 14y ago
    I suspect it is less deployed than SQLite. SQLite gets into things even without network capabilities (e.g. Digital TVs even before they were internet connected for the channel data and the EPG information). I don't know to what extent the code of the BSD stack remains in Windows but you can bet even if a raw build of Windows doesn't have SQLite embedded somewhere within it (which it might well do) that there are probably multiple software installations with it embedded somewhere. Would you actually describe the BSD networking code as being deployed in Linux even? I know it is derived from the BSD stack but is it really still the same software. Zlib and libjpeg as someone else suggests are good suggestions and at least in the races with SQLite.
chris_wot 14y ago
One of my proudest moments was finding a bug in SQLite where a corrupted index caused a select statement to segfault Firefox. I jumped through a lot of hoops to get to the point where I got a backtrace that showed me the SQL statement of a corrupted places.sqlite. I then loaded SQLite on the data file, ran the statement and reproduced the segfault. One of their lead devs then got in contact with me, grabbed the data file and fixed the issue. I suspect that not only did my diagnosis lead to a fix for a LOT of Firefox crashes, but it stopped a lot of frustrating crashes on things like iPhones, etc :-) I may not have done the fix, but I took the time to reproduce the problem. It felt damn good :-) P.S. in case anyone is interested, the bug is https://bugzilla.mozilla.org/show_bug.cgi?id=581946 https://bugzilla.mozilla.org/show_bug.cgi?id=581946 on Mozilla, and at SQLite it's at http://www.sqlite.org/src/ci/83395a3d24 http://www.sqlite.org/src/ci/83395a3d24
- dicroce 14y ago
  Good Job. That is a good one. I'd be proud of that too.
- awj 14y ago
  Thank you for taking the time to help out with a project that nearly everyone uses, even if they don't know it.
- joevandyk 14y ago
  Curious: why was there no test checked in at the same time as the bug fix?
- sbochins 14y ago
  congrats on catching that bug. I use sqlite for a ton of stuff. I just used it at work a few days ago. It has so many use cases where you need a lite query language and not an rdbms.
  - timClicks 14y ago
    I agree with your sentiment, but SQLite is a RDBMS. It's just very lightweight.
jemfinch 14y ago
What I'm more interested in is how SQLite reached such substantial test coverage. What techniques or tools were used to generate the tests? Did someone (drh?) actually sit down, read through the code, and construct a test case for every branch, or did they use tools to facilitate test case construction? How can I apply the same effort to my own software (once it's ready) to improve its reliability?
- antonios 14y ago
  Probably a combination of the above. They are also writing tests for each successfully crushed bug: Whenever a bug is reported against SQLite, that bug is not considered fixed until new test cases have been added to the TCL test suite which would exhibit the bug in an unpatched version of SQLite. Over the years, this has resulted in thousands and thousands of new tests being added to the TCL test suite. These regression tests ensure that bugs that have been fixed in the past are not reintroduced into future versions of SQLite.
  - npsimons 14y ago
    This is precisely how regression tests are supposed to be built; to wit: 1. Find/identify/isolate the bug; 2. Create a test that fails if the bug is not fixed; 3. Run the test to make sure it detects the bug; 4. Fix the bug; 5. Run the test to make sure it passes now that the bug is fixed; 6. Add the test to the test suite and checkin/push the bugfix. I don't always get to do this on my projects, but it's a good habit to get into. Having a good/easy to use test framework already setup can help a lot with this (if tests are hard to write/take too much time, they won't be written).
    - furyofantares 14y ago
      I do it differently. 1. Find/identify/isolate the bug; 2. Fix the bug; 3. Create a test that fails if the bug is not fixed; 4. Run the test to make sure it passes now that the bug is fixed; 5. Revert the fix and run the test to make sure it detects the bug; 6. Add the test to the test suite and checkin/push the bugfix. I prefer this order because if I make a mistake in step 1 I usually realize it in step 2, where I feel like you might not realize it until step 4. I'd be curious to know if there are advantages you know of to the order in which you do it.
zandorg 14y ago
Well, I told the author of SQLite that a double inner join took forever to complete. He just told me I was wrong, but this inner join worked fine on PostGres, MySql and so on. It annoys me, because neither PostGres not MySql are a binary file you can just run with a query, unlike SQLite which is very convenient for embedding in a desktop app.
- stonemetal 14y ago
  Mysql has an embedded version. It may not boil down to a single file on the HD, but I don't see that as a big drawback. http://dev.mysql.com/doc/refman/5.1/en/libmysqld.html http://dev.mysql.com/doc/refman/5.1/en/libmysqld.html
- fdr 14y ago
  SQLite does not have very many execution methods or a very intelligent optimizer, and every database has different access methods available to it to some extent. For example, Postgres lacks skip scan, which Oracle has. MySQL lacks bitmap index scans to combine indexes, which Postgres and Oracle have. Postgres (until the recently released 9.2) lacked index-only scan, which MySQL and Oracle (and DB2, and Informix, and SQL server...that was a feature long in coming) have. MySQL of many versions lacked hash joins (which blows my mind), it may have it now (depends how you count the forks). So, all in all...somewhat expected. I have a number of queries that simply cannot run in their most naive rendering on Postgres due to lack of skip scan.
  - plq 14y ago
    In case anyone wants to read more about skip scans, here's the link: http://docs.oracle.com/cd/B10501_01/server.920/a96533/optimops.htm#51553 http://docs.oracle.com/cd/B10501_01/server.920/a96533/optimo...
dblock 14y ago
Can anyone please comment on the humans involved in running some of this stuff? What are their roles, occupations? Infrastructure? Who owns that?
kderbe 14y ago
My takeaway from this is high-quality software needs several robust test suites, each written with a different testing methodology. A presentation from the Opus audio codec developers ( http://www.ietf.org/proceedings/82/slides/codec-4.pdf http://www.ietf.org/proceedings/82/slides/codec-4.pdf ) opened my eyes to just how many overlapping approaches you can use. In addition to listing a dizzying array of software tests (similar to the SQLite article), the Opus presentation summarizes the strengths and weaknesses of each approach, which is great for understanding when each approach is appropriate to use.
YZF 14y ago
This Google Talk starting about 32:35 the author talks a little about SQLite testing: http://www.youtube.com/watch?v=f428dSRkTs4 http://www.youtube.com/watch?v=f428dSRkTs4
anonymousDan 14y ago
Anyone have any thoughts on how they might be doing 'automatic' memory/resource leak detection (Section 6.0)? Seems to me it would be hard to do without generating lots of false positive failures.
dgregd 14y ago
Does anyone know the real reason SQLite was removed form HTML5 specs? I known official Mozilla arguments. Which are quite week IMHO. Is this was MS job? They where afraid that browser apps will make desktop apps obsolete?
- mariuz 14y ago
  Yes was a Microsoft Hand , they killend it and went to more complex indexed db that no one loves http://h30499.www3.hp.com/t5/Following-the-Wh1t3-Rabbit-Down/W3C-Buries-quot-Web-SQL-Database-Standard-quot/ba-p/2407945#.UHBiwlU-on8 http://h30499.www3.hp.com/t5/Following-the-Wh1t3-Rabbit-Down...

176 points by antonios 14y ago

lrem 14y ago

You should definitely see drh present it in person. He's giving a talk about it in universities around the world, seen it a couple years back, in Poland. It's incredible what effort goes into reliability of what seems such a small thing. Btw, the very same day he persuaded me to move to Fossil. Edit: just to be clear, you should see it for all the good ideas he's explaining. Not for some marketing of a piece o of software.

RDeckard 14y ago
link?
- lrem 14y ago
  Hmmm, despite what uni authorities said, there is no recording of that particular talk available. So I have no specific advice, apart from bland "search YouTube" or "ask by email".
  - cfn 14y ago
    Here is an old one (2006) at Google: http://www.youtube.com/watch?v=jN_YdMdjVpU http://www.youtube.com/watch?v=jN_YdMdjVpU

tedunangst 14y ago

Unfortunately, 100% testing is only effective if you can detect 100% of the errors generated. The only bug I found in sqlite was an off by one in the btree code that was mostly harmless, unless your memory allocator was particularly fussy. I only found the bug, never quite understood it, and after seeing how disturbing the fix was decided some things were best left unlearned. http://www2.sqlite.org/cgi/src/fdiff?v1=fa113d624d38bcb36700a0244b47f39d57d34efb&v2=8cab7c66c822ae9c37c59a923ffec81927583ee2 http://www2.sqlite.org/cgi/src/fdiff?v1=fa113d624d38bcb36700... That said, sqlite is one of the most reliable and better designed libraries I've used. Software is hard.

dbaupp 14y ago
100% testing is effective, just not 100% effective. And 100% testing is strictly better than 99% testing is strictly better than 50% testing (when considering only its bug detecting capabilities).
- jemfinch 14y ago
  I'm glad you appended "when considering only its bug detecting capabilities". Something like SQLite, whose functionality is largely static, definitely benefits from the additional test coverage, but the majority of code out there--code that's constantly evolving, code to which functionality is frequently added and removed--is too often prematurely cast in stone by overzealous testers, making maintenance and evolution significantly more difficult than it ought to be. In a lot of cases, too much test coverage actually reduces the value of the code.
  - josephlord 14y ago
    There is a strong case that more tests allow you to make changes to the code with some confidence that there won't be unintended side effects. Now maybe SQLite's level isn't appropriate in most cases but that doesn't mean high levels of code coverage are bad. It can also give confidence to upgrade underlying frameworks or libraries
moron 14y ago
"Unfortunately, 100% testing is only effective if you can detect 100% of the errors generated." Wow, the word "only" is doing a lot of work in that sentence. Because these tests don't find literally every single problem, you would honestly say they are not effective?

josephlord 14y ago

Is there any more widely deployed software in the world than SQLite? Multiple copies (browsers, language runtimes, embedded in other software) on many computers and built into most smartphones and its probably in quite a few TVs and other devices too. Very successful invisible (to non-developers) software.

tsahyt 14y ago
Not just successful, it's really good too! The API is rather easy to use, it's lightweight and (for small to medium sized databases) it performs really well. Not really suprising it is so widely used.
mhd 14y ago
> Is there any more widely deployed software in the world than SQLite? zlib or libjepg, maybe.
- mrich 14y ago
  libc (both GNU and BSD)
  - lrem 14y ago
    A funny thing here... If you count the number of active copies, this may not be true. Usually you don't see ten apps in one system coming with their own version of libc. This may pretty well be true for sqlite.
  - deleted 14y ago
    [deleted]
wickedchicken 14y ago
The BSD networking stack.
- josephlord 14y ago
  I suspect it is less deployed than SQLite. SQLite gets into things even without network capabilities (e.g. Digital TVs even before they were internet connected for the channel data and the EPG information). I don't know to what extent the code of the BSD stack remains in Windows but you can bet even if a raw build of Windows doesn't have SQLite embedded somewhere within it (which it might well do) that there are probably multiple software installations with it embedded somewhere. Would you actually describe the BSD networking code as being deployed in Linux even? I know it is derived from the BSD stack but is it really still the same software. Zlib and libjpeg as someone else suggests are good suggestions and at least in the races with SQLite.

chris_wot 14y ago

One of my proudest moments was finding a bug in SQLite where a corrupted index caused a select statement to segfault Firefox. I jumped through a lot of hoops to get to the point where I got a backtrace that showed me the SQL statement of a corrupted places.sqlite. I then loaded SQLite on the data file, ran the statement and reproduced the segfault. One of their lead devs then got in contact with me, grabbed the data file and fixed the issue. I suspect that not only did my diagnosis lead to a fix for a LOT of Firefox crashes, but it stopped a lot of frustrating crashes on things like iPhones, etc :-) I may not have done the fix, but I took the time to reproduce the problem. It felt damn good :-) P.S. in case anyone is interested, the bug is https://bugzilla.mozilla.org/show_bug.cgi?id=581946 https://bugzilla.mozilla.org/show_bug.cgi?id=581946 on Mozilla, and at SQLite it's at http://www.sqlite.org/src/ci/83395a3d24 http://www.sqlite.org/src/ci/83395a3d24

dicroce 14y ago
Good Job. That is a good one. I'd be proud of that too.
awj 14y ago
Thank you for taking the time to help out with a project that nearly everyone uses, even if they don't know it.
joevandyk 14y ago
Curious: why was there no test checked in at the same time as the bug fix?
sbochins 14y ago
congrats on catching that bug. I use sqlite for a ton of stuff. I just used it at work a few days ago. It has so many use cases where you need a lite query language and not an rdbms.
- timClicks 14y ago
  I agree with your sentiment, but SQLite is a RDBMS. It's just very lightweight.

jemfinch 14y ago

What I'm more interested in is how SQLite reached such substantial test coverage. What techniques or tools were used to generate the tests? Did someone (drh?) actually sit down, read through the code, and construct a test case for every branch, or did they use tools to facilitate test case construction? How can I apply the same effort to my own software (once it's ready) to improve its reliability?

antonios 14y ago
Probably a combination of the above. They are also writing tests for each successfully crushed bug: Whenever a bug is reported against SQLite, that bug is not considered fixed until new test cases have been added to the TCL test suite which would exhibit the bug in an unpatched version of SQLite. Over the years, this has resulted in thousands and thousands of new tests being added to the TCL test suite. These regression tests ensure that bugs that have been fixed in the past are not reintroduced into future versions of SQLite.
- npsimons 14y ago
  This is precisely how regression tests are supposed to be built; to wit: 1. Find/identify/isolate the bug; 2. Create a test that fails if the bug is not fixed; 3. Run the test to make sure it detects the bug; 4. Fix the bug; 5. Run the test to make sure it passes now that the bug is fixed; 6. Add the test to the test suite and checkin/push the bugfix. I don't always get to do this on my projects, but it's a good habit to get into. Having a good/easy to use test framework already setup can help a lot with this (if tests are hard to write/take too much time, they won't be written).
  - furyofantares 14y ago
    I do it differently. 1. Find/identify/isolate the bug; 2. Fix the bug; 3. Create a test that fails if the bug is not fixed; 4. Run the test to make sure it passes now that the bug is fixed; 5. Revert the fix and run the test to make sure it detects the bug; 6. Add the test to the test suite and checkin/push the bugfix. I prefer this order because if I make a mistake in step 1 I usually realize it in step 2, where I feel like you might not realize it until step 4. I'd be curious to know if there are advantages you know of to the order in which you do it.

zandorg 14y ago

Well, I told the author of SQLite that a double inner join took forever to complete. He just told me I was wrong, but this inner join worked fine on PostGres, MySql and so on. It annoys me, because neither PostGres not MySql are a binary file you can just run with a query, unlike SQLite which is very convenient for embedding in a desktop app.

stonemetal 14y ago
Mysql has an embedded version. It may not boil down to a single file on the HD, but I don't see that as a big drawback. http://dev.mysql.com/doc/refman/5.1/en/libmysqld.html http://dev.mysql.com/doc/refman/5.1/en/libmysqld.html
fdr 14y ago
SQLite does not have very many execution methods or a very intelligent optimizer, and every database has different access methods available to it to some extent. For example, Postgres lacks skip scan, which Oracle has. MySQL lacks bitmap index scans to combine indexes, which Postgres and Oracle have. Postgres (until the recently released 9.2) lacked index-only scan, which MySQL and Oracle (and DB2, and Informix, and SQL server...that was a feature long in coming) have. MySQL of many versions lacked hash joins (which blows my mind), it may have it now (depends how you count the forks). So, all in all...somewhat expected. I have a number of queries that simply cannot run in their most naive rendering on Postgres due to lack of skip scan.
- plq 14y ago
  In case anyone wants to read more about skip scans, here's the link: http://docs.oracle.com/cd/B10501_01/server.920/a96533/optimops.htm#51553 http://docs.oracle.com/cd/B10501_01/server.920/a96533/optimo...

dblock 14y ago

Can anyone please comment on the humans involved in running some of this stuff? What are their roles, occupations? Infrastructure? Who owns that?

kderbe 14y ago

My takeaway from this is high-quality software needs several robust test suites, each written with a different testing methodology. A presentation from the Opus audio codec developers ( http://www.ietf.org/proceedings/82/slides/codec-4.pdf http://www.ietf.org/proceedings/82/slides/codec-4.pdf ) opened my eyes to just how many overlapping approaches you can use. In addition to listing a dizzying array of software tests (similar to the SQLite article), the Opus presentation summarizes the strengths and weaknesses of each approach, which is great for understanding when each approach is appropriate to use.

YZF 14y ago

This Google Talk starting about 32:35 the author talks a little about SQLite testing: http://www.youtube.com/watch?v=f428dSRkTs4 http://www.youtube.com/watch?v=f428dSRkTs4

anonymousDan 14y ago

Anyone have any thoughts on how they might be doing 'automatic' memory/resource leak detection (Section 6.0)? Seems to me it would be hard to do without generating lots of false positive failures.

dgregd 14y ago

Does anyone know the real reason SQLite was removed form HTML5 specs? I known official Mozilla arguments. Which are quite week IMHO. Is this was MS job? They where afraid that browser apps will make desktop apps obsolete?

mariuz 14y ago
Yes was a Microsoft Hand , they killend it and went to more complex indexed db that no one loves http://h30499.www3.hp.com/t5/Following-the-Wh1t3-Rabbit-Down/W3C-Buries-quot-Web-SQL-Database-Standard-quot/ba-p/2407945#.UHBiwlU-on8 http://h30499.www3.hp.com/t5/Following-the-Wh1t3-Rabbit-Down...