Derby
  1. Derby
  2. DERBY-47

Some possible improvements to IN optimization

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 10.0.2.0
    • Fix Version/s: 10.3.1.4
    • Component/s: SQL
    • Labels:
      None
    • Environment:
      all

      Description

      Consider a simple case of -
      A table tbl has 10000 rows, there is a primary key index on i1
      and the query in question is
      select * from tbl where i1 in (-1,100000)

      derby does a table scan of the entire table even though the "IN" list has only two values and the comparison is on a field that has an index.

      Briefly looking at the code, it seems like we insert a between and use the IN list to get the start and stop values for the scan. Thus the range of the values in the "IN" list here plays an important role.

      Thus if the query was changed to select * from tbl where i1 in (-1, 1), an index scan would be chosen.

      It would be nice if we could do something clever in this case where there is clearly an index on the field and the number of values in the IN list is known. Maybe use the rowcount estimate and the IN list size to do some optimizations.

      • consider the length of the "IN" list to do searches on the table. ie use the IN list values to do index key searches on the table,
        -or try to convert it to a join. Use the "IN" list values to create a temporary table and do a join. It is most likely that the optimizer will choose the table with "IN" list here as the outer table in the join and thus will do key searches on the larger table.

      -------------------------------------------------------------------
      some query plans that I logged using derby.language.logQueryPlan=true for some similar queries:

      Table has ascending values from 0 - 9999 for i1. primary key index on i1.

      GMT Thread[UT0,5,main] (XID = 19941), (SESSIONID = 0), select * from scanfixed where i1 in (-1,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990) ******* Project-Restrict ResultSet (2):
      Number of opens = 1
      Rows seen = 10000
      Rows filtered = 9990
      restriction = true
      projection = false
      constructor time (milliseconds) = 0
      open time (milliseconds) = 0
      next time (milliseconds) = 0
      close time (milliseconds) = 0
      restriction time (milliseconds) = 0
      projection time (milliseconds) = 0
      optimizer estimated row count: 750.38
      optimizer estimated cost: 8579.46

      Source result set:
      Table Scan ResultSet for SCANFIXED at read committed isolation level using instantaneous share row locking chosen by the optimizer
      Number of opens = 1
      Rows seen = 10000
      Rows filtered = 0
      Fetch Size = 16
      constructor time (milliseconds) = 0
      open time (milliseconds) = 0
      next time (milliseconds) = 0
      close time (milliseconds) = 0
      next time in milliseconds/row = 0

      scan information:
      Bit set of columns fetched=All
      Number of columns fetched=9
      Number of pages visited=417
      Number of rows qualified=10000
      Number of rows visited=10000
      Scan type=heap
      start position:
      null stop position:
      null qualifiers:
      Column[0][0] Id: 0
      Operator: <=
      Ordered nulls: false
      Unknown return value: false
      Negate comparison result: false
      Column[0][1] Id: 0
      Operator: <
      Ordered nulls: false
      Unknown return value: true
      Negate comparison result: true

      optimizer estimated row count: 750.38
      optimizer estimated cost: 8579.46

      ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------
      l
      2004-10-14 18:59:47.577 GMT Thread[UT0,5,main] (XID = 19216), (SESSIONID = 0), select * from scanfixed where i1 in (9999,9998,9997,9996,9995,9994,9993,9992,9991,9990) ******* Project-Restrict ResultSet (3):
      Number of opens = 1
      Rows seen = 10
      Rows filtered = 0
      restriction = true
      projection = true
      constructor time (milliseconds) = 0
      open time (milliseconds) = 0
      next time (milliseconds) = 0
      close time (milliseconds) = 0
      restriction time (milliseconds) = 0
      projection time (milliseconds) = 0
      optimizer estimated row count: 4.80
      optimizer estimated cost: 39.53

      Source result set:
      Index Row to Base Row ResultSet for SCANFIXED:
      Number of opens = 1
      Rows seen = 10
      Columns accessed from heap =

      {0, 1, 2, 3, 4, 5, 6, 7, 8}

      constructor time (milliseconds) = 0
      open time (milliseconds) = 0
      next time (milliseconds) = 0
      close time (milliseconds) = 0
      optimizer estimated row count: 4.80
      optimizer estimated cost: 39.53

      Index Scan ResultSet for SCANFIXED using index SCANFIXEDX at read committed isolation level using instantaneous share row locking chosen by the optimizer
      Number of opens = 1
      Rows seen = 10
      Rows filtered = 0
      Fetch Size = 16
      constructor time (milliseconds) = 0
      open time (milliseconds) = 0
      next time (milliseconds) = 0
      close time (milliseconds) = 0
      next time in milliseconds/row = 0

      scan information:
      Bit set of columns fetched=All
      Number of columns fetched=2
      Number of deleted rows visited=0
      Number of pages visited=2
      Number of rows qualified=10
      Number of rows visited=10
      Scan type=btree
      Tree height=2
      start position:
      >= on first 1 column(s).
      Ordered null semantics on the following columns:

      stop position:
      > on first 1 column(s).
      Ordered null semantics on the following columns:

      qualifiers:
      None
      optimizer estimated row count: 4.80
      optimizer estimated cost: 39.53

      1. QueryPlanUniqueIndexAndWordIndexOneTerm.txt
        3 kB
        Kevin Hore
      2. QueryPlanUniqueIndexAndWordIndexTwoTerms.txt
        4 kB
        Kevin Hore
      3. QueryPlanUniqueIndexOnlyOneTerm.txt
        3 kB
        Kevin Hore
      4. QueryPlanUniqueIndexOnlyTwoTerms.txt
        3 kB
        Kevin Hore
      5. Derby47PerformanceTest.java
        32 kB
        James Synge
      6. derby-47-performance-data.txt
        4 kB
        James Synge
      7. Derby47PerformanceTest.java
        38 kB
        James Synge
      8. derby-47-performance-data.txt
        4 kB
        James Synge
      9. InListOperatorNode.java
        24 kB
        James Synge
      10. d47_engine_doNotCommit_v1.patch
        68 kB
        A B
      11. d47_engine_doNotCommit_v1.stat
        2 kB
        A B
      12. readlocks.diff
        15 kB
        A B
      13. readlocks_withContext.diff
        43 kB
        A B
      14. d47_mp_relOpPredCheck_v1.patch
        9 kB
        A B
      15. d47_mp_relOpPredCheck_v1.stat
        0.2 kB
        A B
      16. d47_mp_CBO_MoAP_v1.patch
        10 kB
        A B
      17. d47_mp_CBO_MoAP_v1.stat
        0.2 kB
        A B
      18. d47_mp_addlTestCases.patch
        37 kB
        A B
      19. d47_mp_codeGen_v1.patch
        28 kB
        A B
      20. d47_mp_codeGen_v1.stat
        0.9 kB
        A B
      21. d47_mp_exec_v1.patch
        23 kB
        A B
      22. d47_mp_exec_v1.stat
        0.4 kB
        A B
      23. d47_mp_preprocess_v1.patch
        18 kB
        A B
      24. d47_mp_masters_v1.patch
        59 kB
        A B
      25. d47_mp_preprocess_v1.stat
        0.8 kB
        A B
      26. readlocks_withContext.diff
        34 kB
        A B
      27. Derby47PerformanceTest.java
        38 kB
        James Synge
      28. d47_mp_preprocess_v2.patch
        20 kB
        A B
      29. d47_mp_cleanup_v1.patch
        17 kB
        A B
      30. d47_mp_cleanup_v1.stat
        0.6 kB
        A B
      31. d47_mp_junitTest_v1.patch
        32 kB
        A B
      32. d47_beforeAndAfter.html
        112 kB
        A B
      33. d47_beforeAndAfter.html
        112 kB
        A B

        Issue Links

          Activity

          Sunitha Kambhampati created issue -
          Kevin Hore made changes -
          Field Original Value New Value
          Attachment QueryPlanUniqueIndexAndWordIndexOneTerm.txt [ 12320702 ]
          Kevin Hore made changes -
          Kevin Hore made changes -
          Attachment QueryPlanUniqueIndexOnlyOneTerm.txt [ 12320704 ]
          Kevin Hore made changes -
          Attachment QueryPlanUniqueIndexOnlyTwoTerms.txt [ 12320705 ]
          Daniel James Neades made changes -
          Link This issue is cloned as DERBY-713 [ DERBY-713 ]
          James Synge made changes -
          Attachment Derby47PerformanceTest.java [ 12340205 ]
          James Synge made changes -
          Attachment derby-47-performance-data.txt [ 12340206 ]
          James Synge made changes -
          Attachment Derby47PerformanceTest.java [ 12340270 ]
          Attachment derby-47-performance-data.txt [ 12340269 ]
          James Synge made changes -
          Attachment InListOperatorNode.java [ 12347581 ]
          A B made changes -
          Assignee A B [ army ]
          A B made changes -
          Attachment d47_engine_doNotCommit_v1.stat [ 12349471 ]
          Attachment d47_engine_doNotCommit_v1.patch [ 12349470 ]
          A B made changes -
          Attachment d47_engine_doNotCommit_v1.patch [ 12349470 ]
          A B made changes -
          Attachment d47_engine_doNotCommit_v1.stat [ 12349471 ]
          A B made changes -
          Attachment d47_engine_doNotCommit_v1.stat [ 12349481 ]
          Attachment d47_engine_doNotCommit_v1.patch [ 12349480 ]
          A B made changes -
          Attachment readlocks.diff [ 12349483 ]
          A B made changes -
          Attachment readlocks_withContext.diff [ 12349552 ]
          A B made changes -
          Attachment d47_mp_relOpPredCheck_v1.patch [ 12351823 ]
          Attachment d47_mp_relOpPredCheck_v1.stat [ 12351824 ]
          A B made changes -
          Attachment d47_mp_CBO_MoAP_v1.patch [ 12352071 ]
          Attachment d47_mp_CBO_MoAP_v1.stat [ 12352072 ]
          A B made changes -
          Derby Info [Patch Available]
          A B made changes -
          Attachment d47_mp_addlTestCases.patch [ 12352193 ]
          A B made changes -
          Derby Info [Patch Available]
          A B made changes -
          Attachment d47_mp_codeGen_v1.patch [ 12352685 ]
          Attachment d47_mp_codeGen_v1.stat [ 12352686 ]
          A B made changes -
          Attachment d47_mp_exec_v1.stat [ 12352866 ]
          Attachment d47_mp_exec_v1.patch [ 12352865 ]
          A B made changes -
          Derby Info [Patch Available]
          A B made changes -
          Attachment d47_mp_preprocess_v1.stat [ 12353152 ]
          Attachment d47_mp_masters_v1.patch [ 12353151 ]
          Attachment d47_mp_preprocess_v1.patch [ 12353150 ]
          A B made changes -
          Attachment readlocks_withContext.diff [ 12353203 ]
          James Synge made changes -
          Attachment Derby47PerformanceTest.java [ 12353309 ]
          A B made changes -
          Attachment d47_mp_preprocess_v2.patch [ 12353319 ]
          A B made changes -
          Derby Info [Patch Available]
          A B made changes -
          Attachment d47_mp_cleanup_v1.stat [ 12353519 ]
          Attachment d47_mp_cleanup_v1.patch [ 12353518 ]
          A B made changes -
          Attachment d47_mp_junitTest_v1.patch [ 12353556 ]
          A B made changes -
          Resolution Fixed [ 1 ]
          Status Open [ 1 ] Resolved [ 5 ]
          Fix Version/s 10.3.0.0 [ 12310800 ]
          A B made changes -
          Attachment d47_beforeAndAfter.html [ 12353802 ]
          A B made changes -
          Attachment d47_beforeAndAfter.html [ 12353854 ]
          Sunitha Kambhampati made changes -
          Status Resolved [ 5 ] Closed [ 6 ]
          Kathey Marsden made changes -
          Link This issue relates to DERBY-3061 [ DERBY-3061 ]
          A B made changes -
          Link This issue relates to DERBY-3253 [ DERBY-3253 ]
          A B made changes -
          Link This issue relates to DERBY-3279 [ DERBY-3279 ]
          A B made changes -
          Link This issue relates to DERBY-2740 [ DERBY-2740 ]
          A B made changes -
          Link This issue relates to DERBY-2500 [ DERBY-2500 ]
          Knut Anders Hatlen made changes -
          Link This issue is related to DERBY-4376 [ DERBY-4376 ]
          Mike Matrigali made changes -
          Link This issue relates to DERBY-6045 [ DERBY-6045 ]
          Mike Matrigali made changes -
          Link This issue relates to DERBY-6226 [ DERBY-6226 ]
          Gavin made changes -
          Workflow jira [ 37894 ] Default workflow, editable Closed status [ 12802266 ]

            People

            • Assignee:
              A B
              Reporter:
              Sunitha Kambhampati
            • Votes:
              8 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development