Professional Web Applications Themes

Using two indexes on the same table - MySQL

Hello Axel, Thanks for your reply. > Seems you don't know of multi-column-indexes nor of the spatial > indexing extension (MyISAM only) > > [url]http://dev.mysql.com/doc/refman/5.0/en/create-index.html[/url] > [url]http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html[/url] Yes, I knew about those. However I fail to see how a multi-column index would help in this case. Could you elaborate? If I create an index on (lat, lon), will it be able to retrieve ranges efficiently? About the spatial indexing, I did not want to go into this as it seems overkill for my needs. But if you say it's the way to go, I'll give it a try. As you're ...

  1. #1

    Default Re: Using two indexes on the same table

    Hello Axel,

    Thanks for your reply.
    > Seems you don't know of multi-column-indexes nor of the spatial
    > indexing extension (MyISAM only)
    >
    > [url]http://dev.mysql.com/doc/refman/5.0/en/create-index.html[/url]
    > [url]http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html[/url]
    Yes, I knew about those. However I fail to see how a multi-column index
    would help in this case. Could you elaborate? If I create an index on
    (lat, lon), will it be able to retrieve ranges efficiently? About the
    spatial indexing, I did not want to go into this as it seems overkill
    for my needs. But if you say it's the way to go, I'll give it a try.

    As you're from MySQL, any plans on allowing future versions to use two
    indexes in the same query?

    Cheers,

    JFG

    J.F. Groff Guest

  2. #2

    Default Re: Using two indexes on the same table

    >I want it to perform the
    >range scan on both indexes, and then give me the intersection of
    >results.
    Do you have any evidence that this would be *faster*? It sounds like
    query pessimization to me.

    Gordon L. Burditt
    Gordon Burditt Guest

  3. #3

    Default Re: Using two indexes on the same table

    >>I want it to perform the
    >>range scan on both indexes, and then give me the intersection of
    >>results.
    >
    > Do you have any evidence that this would be *faster*? It sounds like
    > query pessimization to me.
    Well, I'm no expert on database internals, but it only seemed logical
    to me that if a range scan on one index takes a few ms (selecting a few
    thousand records out of millions), and a range scan on the second index
    also takes a few ms (again selecting a few thousand records out of
    millions), then finding the rows that are only selected in both scans
    (a few dozen) would be a piece of cake.

    If you have a suggestion how to make this sort of query easier on the
    system, please let me know.

    JFG

    jfgroff@gmail.com Guest

  4. #4

    Default Re: Using two indexes on the same table

    "J.F. Groff" <jfgroff> wrote:
    >
    >> Seems you don't know of multi-column-indexes nor of the spatial
    >> indexing extension (MyISAM only)
    >>
    >> [url]http://dev.mysql.com/doc/refman/5.0/en/create-index.html[/url]
    >> [url]http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html[/url]
    >
    > Yes, I knew about those. However I fail to see how a multi-column index
    > would help in this case. Could you elaborate? If I create an index on
    > (lat, lon), will it be able to retrieve ranges efficiently?
    MySQL will do a range scan on the index then. This should be signifi-
    cantly faster than the scan over the records itself. With an index on
    only `lat` (or `lon`) the engine has to fetch all candidate records in
    the respective `lat` (`lon`) range and look into the records which
    fulfill the condition on `lon` (`lat`). This is a (partial) table scan.
    It is expensive mostly because of the many head movement operations of
    your disks.

    With a combined index on (lat,lon) the engine would scan the part of
    the index where the `lat` condition is fulfilled and pick all records
    where the `lon` condition holds true as well. This is a (partial) index
    scan. It is supposed to be much faster because

    a) the index is much smaller than the complete records
    b) the index is supposed to be in memory anyway (no external I/O costs)

    If you try EXPLAIN with different ranges for `lat` and `lon` you will
    notice that the optimizer will pick either the `lat` or the `lon`
    index, depending on which range is more selective. To achive the same
    behaviour with a combined index you have to create two indexes as well,
    one (lat,lon) and one (lon,lat). If you know beforehand, that your
    `lat` range will be more selective in your queries, you might go with
    just the (lat,lon) index. Feel free to experiment :-)
    > About the
    > spatial indexing, I did not want to go into this as it seems overkill
    > for my needs. But if you say it's the way to go, I'll give it a try.
    You definitely should. This is exactly what the spatial indexing was
    made for. However it is a bit complicated to deal with all those
    geometry representations. Have a look at the examples in the manual.

    I would suggest to try both a combined index and the spatial index.
    I never used spatial indexes by myself but I would expect a (minor)
    performance boost by using them.
    > As you're from MySQL, any plans on allowing future versions to use two
    > indexes in the same query?
    "In the same query" is already addressed by the index merging
    algorithm. But I'm afraid the "each record will be looked up in only
    one index" will hold true for quite a while. But I'm not so familiar
    with the future plans of the optimizer team. You should go and ask
    that in the optimizer forum at forums.mysql.com.


    XL
    --
    Axel Schwenke, Senior Software Developer, MySQL AB

    Online User Manual: [url]http://dev.mysql.com/doc/refman/5.0/en/[/url]
    MySQL User Forums: [url]http://forums.mysql.com/[/url]
    Axel Schwenke Guest

  5. #5

    Default Re: Using two indexes on the same table

    >>>I want it to perform the
    >>>range scan on both indexes, and then give me the intersection of
    >>>results.
    >>
    >> Do you have any evidence that this would be *faster*? It sounds like
    >> query pessimization to me.
    >
    >Well, I'm no expert on database internals, but it only seemed logical
    >to me that if a range scan on one index takes a few ms (selecting a few
    >thousand records out of millions), and a range scan on the second index
    >also takes a few ms (again selecting a few thousand records out of
    >millions), then finding the rows that are only selected in both scans
    >(a few dozen) would be a piece of cake.
    And I don't think finding the rows that are only selected in both
    scans is a piece of cake. The lookup part is. You'd probably have
    to sort at least one of the result sets (by record address). Sorting
    gets expensive. Sequential search is worse. Especially if it
    doesn't fit in memory.

    Thought experiment: try it with hypothetical phone books. Look
    up "Smith" as a last name in the sorted-by-last-name phone book,
    and look up "J" as a middle name/initial in the
    sorted-by-middle-name/initial phone book. Now make a list of all
    the records for "J. Smith" (with any first initial/name).

    Gordon L. Burditt
    Gordon Burditt Guest

  6. #6

    Default Re: Using two indexes on the same table

    Alex and Gordon,

    Thanks a lot for your detailed explanations. The situation is a lot
    clearer to me now, especially the trick to perform the range scan on
    the index instead of the full records -- but this index is so big that
    I'm afraid it won't fit in memory either. Which settings can I adjust
    to reserve enough memory for my most heavily-used indexes?

    I'll do some experiments to optimize those queries. I was also thinking
    of creating a quadrant field which would hold a combination of lat and
    lon at the required precision (0.1 degrees should be enough given the
    distribution of locations in my db), then a lookup of places in the
    same quadrant would be instantaneous, and I can probably get decent
    performance even if I have to fetch some places from the neighbouring
    quadrants.

    I'll post my results after the experiments are done. Thanks again,

    JFG

    jfgroff@gmail.com Guest

  7. #7

    Default Re: Using two indexes on the same table

    "jfgroff" <jfgroff> wrote:
    > Alex and Gordon,
    ^^^^
    Permutation of characters...
    > Thanks a lot for your detailed explanations. The situation is a lot
    > clearer to me now, especially the trick to perform the range scan on
    > the index instead of the full records -- but this index is so big that
    > I'm afraid it won't fit in memory either.
    Indexes are compressed (simple prefix-compression works well, because
    values are ordered anyway). Typically that saves a lot of memory.
    > Which settings can I adjust
    > to reserve enough memory for my most heavily-used indexes?
    For MyISAM there's the key_buffer, caching only indexes. InnoDB uses
    the innodb_buffer_pool to cache all kinds of pages. Secondary indexes
    use their own pages, the primary key is clustered with the records.
    Depending on the table type(s) used, each of those buffers (but not
    both) could be set as high as 50-80% of the available memory. The
    manual contains some hints on how to tune those parameters.


    XL
    --
    Axel Schwenke, Senior Software Developer, MySQL AB

    Online User Manual: [url]http://dev.mysql.com/doc/refman/5.0/en/[/url]
    MySQL User Forums: [url]http://forums.mysql.com/[/url]
    Axel Schwenke Guest

  8. #8

    Default Re: Using two indexes on the same table

    Hi Axel,

    Sorry for messing up your name; it was late ;-)

    I did a few tests today, and here are my results. From a fresh database
    loaded with about 4 million records, I always perform the same query
    yielding 34 results near KÝbenhavn:
    SELECT id, name, lat, lon FROM Places
    WHERE lat > 55.5 AND lat < 55.7
    AND lon > 12.0 AND lon < 12.1;


    The query cache is disabled for these tests, although it would be
    enabled in production.

    1) Using InnoDB
    - with no index: 6.50 seconds
    - with indexes on lat and lon (range of about 8000 rows using ixlon):
    1.25 seconds
    - repeating the same query: 0.85 seconds
    - forcing use of ixlat (range of about 16000 rows): 1.21 seconds
    - repeating the same query: 1.01 seconds
    - with a combined index on (lat,lon), forcing its use (range of about
    20000 rows): 0.91 seconds
    - repeating the same query: 0.92 seconds


    2) Using MyISAM
    - with no index: 4.41 seconds
    - with indexes on lat and lon (range of about 4000 rows using ixlon):
    1.54 seconds
    - repeating the same query: 0.07 seconds
    - forcing use of ixlat (range of about 8000 rows): 0.28 seconds
    - repeating the same query: 0.22 seconds
    - with a combined index on (lat,lon), forcing its use (range of about
    8000 rows): 0.21 seconds
    - similar queries on random locations take between 0.11 and 0.19
    seconds (letting the query planner choose its preferred index)
    - when forced to use the combined index, they take between 0.11 and
    0.28 seconds

    Conclusions:
    - Use of a combined index does not bring any significant performance
    improvement, and it consumes a lot of extra disk space: abandoned.
    - MyISAM is about 4 times faster than InnoDB for this situation.
    - But with a sustained rate of 5 requests per second, we still can't
    put this in production... Our goal is 100 rps.
    - MyISAM is more efficient at re-using data from previous queries,
    essentially thanks to the built-in key cache.
    - So let's try to tune the key cache!

    3) MyISAM with pre-loaded key cache
    - set global key_buffer_size=200*1000*1024; (200 MB can accomodate
    our full indexes in the key cache)
    - LOAD INDEX INTO CACHE Places;
    - now the usual query takes 0.12 seconds
    - similar queries on random locations take between 0.07 and 0.13
    seconds

    We are now standing at 10 requests per second with a moderate memory
    expense; good progress but still not enough.

    4) Mapping (lat,lon) to a single integer key
    - we add an INT column called quadrant calculated as INT(lat*10) *
    10000 + INT((lon + 180) * 10)
    - each quadrant maps to a 0.1 x 0.1 degrees (lat,lon) rectangle,
    precise enough for our needs
    - our standard query becomes:
    SELECT id, name, lat, lon FROM Places
    WHERE quadrant = 5561920;
    - it returns 25 results in 0.00 seconds, not exactly the same results
    due to rounding of positions, but that's easy to take into account in
    the client application
    - we can extend the query to the neighbouring quadrants, e.g. for a
    0.3 x 0.2 degrees rectangle:
    SELECT id, name, lat, lon FROM Places
    WHERE quadrant = 5551920 OR quadrant = 5561920 OR quadrant = 5571920
    OR quadrant = 5551921 OR quadrant = 5561921 OR quadrant = 5571921;
    - this query returns 128 results in 0.00 seconds
    - random queries anywhere take between 0.00 and 0.01 seconds
    - we need more precise time measurement but it looks like this is the
    way to get the desired performance
    - we haven't tuned the key cache and query cache yet...

    Conclusion: optimizing the queries is nice, optimizing the caches is
    nicer, optimizing the data is nicest ;-)

    As a side note, I didn't think we should move back to MyISAM, but this
    looks good for infrequently-updated tables which need fast selects and
    don't hold critical customer data.

    Thanks again for your help.

    JFG

    jfgroff@gmail.com Guest

  9. #9

    Default Re: Using two indexes on the same table

    [email]jfgroff[/email] wrote:
    > Hi Axel,
    >
    > Sorry for messing up your name; it was late ;-)
    >
    > I did a few tests today, and here are my results. From a fresh database
    > loaded with about 4 million records, I always perform the same query
    > yielding 34 results near KÝbenhavn:
    > SELECT id, name, lat, lon FROM Places
    > WHERE lat > 55.5 AND lat < 55.7
    > AND lon > 12.0 AND lon < 12.1;
    >
    >
    > The query cache is disabled for these tests, although it would be
    > enabled in production.
    >
    > 1) Using InnoDB
    > - with no index: 6.50 seconds
    > - with indexes on lat and lon (range of about 8000 rows using ixlon):
    > 1.25 seconds
    > - repeating the same query: 0.85 seconds
    > - forcing use of ixlat (range of about 16000 rows): 1.21 seconds
    > - repeating the same query: 1.01 seconds
    > - with a combined index on (lat,lon), forcing its use (range of about
    > 20000 rows): 0.91 seconds
    > - repeating the same query: 0.92 seconds
    >
    >
    > 2) Using MyISAM
    > - with no index: 4.41 seconds
    > - with indexes on lat and lon (range of about 4000 rows using ixlon):
    > 1.54 seconds
    > - repeating the same query: 0.07 seconds
    > - forcing use of ixlat (range of about 8000 rows): 0.28 seconds
    > - repeating the same query: 0.22 seconds
    > - with a combined index on (lat,lon), forcing its use (range of about
    > 8000 rows): 0.21 seconds
    > - similar queries on random locations take between 0.11 and 0.19
    > seconds (letting the query planner choose its preferred index)
    > - when forced to use the combined index, they take between 0.11 and
    > 0.28 seconds
    >
    > Conclusions:
    > - Use of a combined index does not bring any significant performance
    > improvement, and it consumes a lot of extra disk space: abandoned.
    > - MyISAM is about 4 times faster than InnoDB for this situation.
    > - But with a sustained rate of 5 requests per second, we still can't
    > put this in production... Our goal is 100 rps.
    > - MyISAM is more efficient at re-using data from previous queries,
    > essentially thanks to the built-in key cache.
    > - So let's try to tune the key cache!
    >
    > 3) MyISAM with pre-loaded key cache
    > - set global key_buffer_size=200*1000*1024; (200 MB can accomodate
    > our full indexes in the key cache)
    > - LOAD INDEX INTO CACHE Places;
    > - now the usual query takes 0.12 seconds
    > - similar queries on random locations take between 0.07 and 0.13
    > seconds
    >
    > We are now standing at 10 requests per second with a moderate memory
    > expense; good progress but still not enough.
    >
    > 4) Mapping (lat,lon) to a single integer key
    > - we add an INT column called quadrant calculated as INT(lat*10) *
    > 10000 + INT((lon + 180) * 10)
    > - each quadrant maps to a 0.1 x 0.1 degrees (lat,lon) rectangle,
    > precise enough for our needs
    > - our standard query becomes:
    > SELECT id, name, lat, lon FROM Places
    > WHERE quadrant = 5561920;
    > - it returns 25 results in 0.00 seconds, not exactly the same results
    > due to rounding of positions, but that's easy to take into account in
    > the client application
    > - we can extend the query to the neighbouring quadrants, e.g. for a
    > 0.3 x 0.2 degrees rectangle:
    > SELECT id, name, lat, lon FROM Places
    > WHERE quadrant = 5551920 OR quadrant = 5561920 OR quadrant = 5571920
    > OR quadrant = 5551921 OR quadrant = 5561921 OR quadrant = 5571921;
    > - this query returns 128 results in 0.00 seconds
    > - random queries anywhere take between 0.00 and 0.01 seconds
    > - we need more precise time measurement but it looks like this is the
    > way to get the desired performance
    > - we haven't tuned the key cache and query cache yet...
    >
    > Conclusion: optimizing the queries is nice, optimizing the caches is
    > nicer, optimizing the data is nicest ;-)
    >
    > As a side note, I didn't think we should move back to MyISAM, but this
    > looks good for infrequently-updated tables which need fast selects and
    > don't hold critical customer data.
    >
    > Thanks again for your help.
    >
    > JFG
    >
    You also might find converting lat and long to an int will improve performance.
    Integer comparisons are always the fastest.

    --
    ==================
    Remove the "x" from my email address
    Jerry Stuckle
    JDS Computer Training Corp.
    [email]jstucklexattglobal.net[/email]
    ==================
    Jerry Stuckle Guest

  10. #10

    Default Re: Using two indexes on the same table

    You said that using the spatial was "over-kill" - why would you assume
    that anything dealing with spatial data - as you are - would be
    over-kill? While you are testing, why not test to see if the spatial
    option will give you what you really need - a way to efficiently select
    spatial data.

    onedbguru@firstdbasource.com Guest

  11. #11

    Default Re: Using two indexes on the same table

    I wanted to test it, but the doentation says that spatial tables
    currently can not be populated with LOAD DATA INFILE from a text
    format, so it would be difficult to import my existing geo data in
    there for proper testing. However, if you have practical experience
    with using spatial tables in a similar context, I'd be glad to read
    about it. Our needs are: a few million places defined as simple lat/lon
    points, typical query is to find places in a 0.1x0.1 degrees area, must
    support about 100 requests per second on a single machine.

    Besides, I have now measured that the mapping of lat and lon to a
    single integer quadrant can deliver the required performance with
    minimal hassle, so I'm going to use this for the first production
    release, but I remain open to more sophisticated solutions for the
    future.

    JFG

    jfgroff@gmail.com Guest

Similar Threads

  1. indexes in cs
    By Albert_Constantineau@adobeforums.com in forum Adobe Indesign Macintosh
    Replies: 1
    Last Post: August 14th, 09:41 PM
  2. Indexes
    By tomL in forum Dreamweaver AppDev
    Replies: 2
    Last Post: March 14th, 04:26 PM
  3. Two indexes?
    By Andy_Fielding@adobeforums.com in forum Adobe Indesign Windows
    Replies: 1
    Last Post: August 14th, 02:55 AM
  4. Replies: 2
    Last Post: August 12th, 07:55 AM
  5. How many indexes can 9i use on one table in a single query?
    By Roger Redford in forum Oracle Server
    Replies: 3
    Last Post: January 7th, 12:16 AM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139