[Db-derby Wiki] Update of "DerbyBug47" by JamesSynge

[Apache Wiki <wi...@apache.org>]

Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Db-derby Wiki" for change notification.

The following page has been changed by JamesSynge:
http://wiki.apache.org/db-derby/DerbyBug47

New page:
Derby Bug 47 (http://issues.apache.org/jira/browse/DERBY-47),
"Some possible improvements to IN optimization", 
draws attention to a problem with IN lists that contain parameter markers,
though there do appear to be problems with IN lists that contain literals
that are not closely grouped in the range of values for the column being
filtered.  Derby Bug 713 (http://issues.apache.org/jira/browse/DERBY-713),
"Query optimizer should not make poor choices when optimizing IN and WHERE clauses",
focuses on the same issue.

I attached a program to Derby Bug 47, Derby47PerformanceTest.java, that evaluates
a number of different SELECT statements that achieve the same result as evaluating:

{{{ SELECT * FROM someTable WHERE someColumn IN (?, ?, ..., ?) }}}

These alternatives are:

||Literals         || 1 query, using {{{ WHERE someColumn IN ('literal1', ..., 'literalN') }}} ||
||Literal          || N queries, using {{{ WHERE someColumn = 'literal[i] }}} ||
||Markers          || 1 query, using {{{ WHERE someColumn IN (?, ..., ?) }}} ||
||Marker           || N queries, using {{{ WHERE someColumn = ? }}} ||
||Join Temp        || 1 query, store parameters in a temp table, use join query, then delete parameters ||
||Join  Scratch    || 1 query, store parameters in a table, use join query, then delete parameters ||
||Join Savepoint   || 1 query, set savepoint, store parameters in a table, use join query, then rollback savepoint ||
||Nested Temp      || 1 query, store parameters in a temp table, use nested query, then delete parameters ||
||Nested Scratch   || 1 query, store parameters in a table, use nested query, then delete parameters ||
||Nested Savepoint || 1 query, set savepoint, store parameters in a table, use nested query, then rollback savepoint ||

Here are the results for different numbers of parameters (the ID Count column below), on a table of 100,000 rows.

|| ||||Literals||||Literal||||Markers||||Marker||||Join Temp||||Join Scratch||||Join Savepoint||||Nested Temp||||Nested Scratch||||Nested Savepoint||
||ID Count||Total ms||Avg ms||Total ms||Avg ms||Total ms||Avg ms||Total ms||Avg ms||Total ms||Avg ms||Total ms||Avg ms||Total ms||Avg ms||Total ms||Avg ms||Total ms||Avg ms||Total ms||Avg ms||
||1||30||30||40||40||10||10||0||0||120||120||10||10||10||10||1126||1126||881||881||860||860||
||2||690||345||50||25||1370||685||0||0||40||20||0||0||10||5||761||380||711||355||871||435||
||3||660||220||90||30||1962||654||0||0||50||16||10||3||0||0||761||253||771||257||730||243||
||4||700||175||80||20||1901||475||0||0||60||15||10||2||10||2||781||195||720||180||700||175||
||5||731||146||70||14||1601||320||10||2||70||14||0||0||10||2||721||144||811||162||2153||430||
||6||811||135||90||15||2754||459||0||0||30||5||10||1||30||5||986||164||731||121||1062||177||
||7||791||113||120||17||2193||313||0||0||100||14||0||0||10||1||782||111||821||117||771||110||
||8||741||92||140||17||2363||295||0||0||20||2||10||1||10||1||741||92||791||98||831||103||
||9||776||86||60||6||2373||263||0||0||20||2||10||1||51||5||711||79||691||76||711||79||
||10||671||67||70||7||2243||224||0||0||30||3||0||0||10||1||741||74||761||76||852||85||
||20||872||43||120||6||2804||140||0||0||40||2||60||3||111||5||721||36||801||40||811||40||
||30||832||27||195||6||3034||101||10||0||30||1||70||2||60||2||731||24||811||27||861||28||
||40||831||20||300||7||3305||82||10||0||30||0||140||3||181||4||741||18||862||21||881||22||
||50||856||17||260||5||3645||72||10||0||21||0||91||1||30||0||721||14||781||15||761||15||
||60||862||14||351||5||3605||60||40||0||30||0||40||0||20||0||742||12||811||13||861||14||
||70||881||12||350||5||4156||59||40||0||30||0||60||0||81||1||761||10||811||11||821||11||
||80||906||11||330||4||4287||53||20||0||30||0||30||0||30||0||771||9||901||11||842||10||
||90||911||10||380||4||4577||50||20||0||50||0||31||0||40||0||981||10||991||11||842||9||
||100||891||8||431||4||4517||45||20||0||30||0||40||0||90||0||771||7||801||8||912||9||
||150||941||6||666||4||5498||36||30||0||40||0||120||0||70||0||951||6||811||5||992||6||
||200||941||4||882||4||6789||33||70||0||81||0||140||0||130||0||751||3||771||3||922||4||
||250||946||3||1432||5||7571||30||70||0||70||0||160||0||260||1||771||3||952||3||962||3||
||300||961||3||1743||5||8683||28||60||0||70||0||171||0||341||1||791||2||922||3||921||3||
||350||982||2||1847||5||9574||27||90||0||80||0||271||0||460||1||821||2||1282||3||1061||3||
||400||1001||2||2118||5||10946||27||90||0||100||0||321||0||330||0||771||1||1091||2||1032||2||
||450||1291||2||2278||5||11686||25||110||0||110||0||450||1||400||0||871||1||1071||2||1221||2||
||500||1252||2||2534||5||13049||26||110||0||130||0||381||0||530||1||791||1||1212||2||1432||2||
||750||1422||1||3665||4||19668||26||230||0||180||0||932||1||821||1||836||1||1351||1||1462||1||
||1000||1632||1||4927||4||26929||26||240||0||220||0||831||0||962||0||876||0||1457||1||1632||1||
||1250||1787||1||6609||5||32066||25||280||0||305||0||982||0||1132||0||916||0||1782||1||1808||1||
||1500||2433||1||7792||5||103108||68||330||0||381||0||1281||0||1512||1||1031||0||1752||1||2103||1||
||1750||2654||1||9283||5||134974||77||381||0||390||0||1452||0||2032||1||961||0||2033||1||2363||1||
||2000||3365||1||10455||5||169463||84||446||0||465||0||1562||0||1873||0||976||0||2213||1||2343||1||
||2250||3956||1||11361||5||142104||63||481||0||540||0||1852||0||2233||0||1026||0||2474||1||2674||1||
||2500||4992||1||12938||5||167521||67||521||0||571||0||1978||0||2223||0||1071||0||2524||1||3104||1||