Forum Stats

  • 3,824,874 Users
  • 2,260,435 Discussions
  • 7,896,336 Comments

Discussions

Index Range scan cost ?

448778
448778 Member Posts: 447 Red Ribbon
edited Dec 29, 2008 4:05AM in General Database Discussions
Why the effective index selectivity of index range scan is calculated this way

(highendval -lowendval)/(highvalue -lowvalue)+ 2/num_distinct ?why its not 1/num_distinct which is used in case of equality predicate?


Second question is why the effective index selectivity calculation for a composite index is calculated differently if there is range scan on the leading column of the indexes and though there are predicates available in the where clause for other column in the index why the cost of those predicates is not included in the index range scan.

e.g I have composite index on (n1,n2,n3) and the where clause is

n1 between 6 and 9 and
n2=3 and
n3='a'

why only the effective index selectivity of the index range scan for the predicate n1 is used in finding effective Index selectivity , but all n1,n2 and n3 are considered in getting effective table selectivity(which makes sense)

P.S:- I am refering Cost based fundamental by Jonathan Lewis.

Edited by: user445775 on Dec 28, 2008 11:06 AM
Tagged:

Answers

  • Randolf Geist
    Randolf Geist Member Posts: 2,214 Silver Trophy
    user445775 wrote:
    Why the effective index selectivity of index range scan is calculated this way

    (highendval -lowendval)/(highvalue -lowvalue)+ 2/num_distinct ?why its not 1/num_distinct which is used in case of equality predicate?
    Not sure what you intend to say here? You're referring to the selectivity formula for ranges (but I think there is an error, it's not "... + 2 / num_distinct", this part depends on whether it's a closed or open range) and there is nothing special in case of an index range scan.
    Second question is why the effective index selectivity calculation for a composite index is calculated differently if there is range scan on the leading column of the indexes and though there are predicates available in the where clause for other column in the index why the cost of those predicates is not included in the index range scan.

    e.g I have composite index on (n1,n2,n3) and the where clause is

    n1 between 6 and 9 and
    n2=3 and
    n3='a'

    why only the effective index selectivity of the index range scan for the predicate n1 is used in finding effective Index selectivity , but all n1,n2 and n3 are considered in getting effective table selectivity(which makes sense)
    Because the remaining predicates can only be applied while performing the range scan on the leaf blocks, so for the effective index selectivity (the number of leaf blocks to visit) you can only use the predicates up to the range scan (or up to a column omission), but once you read the index leaf blocks you can apply all remaining predicates that can be satisfied by the index (the index selectivity with filters or effective table selectivity).

    By the way, this is explained on page 74.

    Regards,
    Randolf

    Oracle related stuff blog:
    http://oracle-randolf.blogspot.com/

    SQLTools++ for Oracle (Open source Oracle GUI for Windows):
    http://www.sqltools-plusplus.org:7676/
    http://sourceforge.net/projects/sqlt-pp/
  • 448778
    448778 Member Posts: 447 Red Ribbon
    edited Dec 28, 2008 6:44PM
    Thanks Randolf,

    If you look at the page 72 the index selectivity with predicate n2 between 1 and 3 which is bounded and closed range predicate.


    The effective index selectivity is been calculated as
    (3-1)/(19-1) +1/20+1/20 (20 is the num_distinct key value for the column n2 in the index).
    (Please disregard this question as I have got the answer)


    Still not able to understand the 2nd question.

    Also regarding second question if the range of n1 is between 1 and 3, will Oracle will only search the leaf blocks which has the value for n1 between 1 and 3 ,the values for other predicates may be or may not belongs to same leaf blocks where Oracle storescolumn value n1 between 1 and 3 , does it mean or it will search the whole index and then after reading all the leaf blocks it will apply all the predicate filter?

    Edited by: user445775 on Dec 28, 2008 3:43 PM
  • Randolf Geist
    Randolf Geist Member Posts: 2,214 Silver Trophy
    user445775 wrote:
    Still not able to understand the 2nd question.

    Also regarding second question if the range of n1 is between 1 and 3, will Oracle will only search the leaf blocks which has the value for n1 between 1 and 3 ,the values for other predicates may be or may not belongs to same leaf blocks where Oracle storescolumn value n1 between 1 and 3 , does it mean or it will search the whole index and then after reading all the leaf blocks it will apply all the predicate filter?
    It will scan all leaf blocks that correspond to all predicates up to the range scan (that's the effective index selectivity), and all predicates that can only be satisfied by checking these leaf blocks will then be applied, that's the effective index selectivity with filters, because these remaining predicates can't be used to restrict the number of leaf blocks to examine, but can then only be applied as filter to these index leaf blocks.

    This doesn't mean that the whole index and all of its leaf blocks need to be read, it's just the leaf blocks that need to be scanned according to the predicates up to the range scan.

    Note that there is a third selectivity, if you include the table visit: You might have predicates that can only be applied to the table after visiting (and filtering) the index leaf blocks (page 78).

    Regards,
    Randolf

    Oracle related stuff blog:
    http://oracle-randolf.blogspot.com/

    SQLTools++ for Oracle (Open source Oracle GUI for Windows):
    http://www.sqltools-plusplus.org:7676/
    http://sourceforge.net/projects/sqlt-pp/
This discussion has been closed.