Mysql Performance optimization, max CPU load, low qps

Question

I would like if anybody could look into performance optimize this:

I have a Ubuntu 12.04 running on VMWare 5.1, with 32 GB RAM and 8 Cores (No problems regarding cpu scheduling as the VM is almost alone on the host) The hardware is IBM blade with 2xE5-2660 CPU's

Im running Mysql 5.5, and have a table looking like this:

ochrange | CREATE TABLE `ochrange` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`rangestart` int(8) NOT NULL,
`rangeend` int(8) NOT NULL,
`rangelength` int(11) NOT NULL DEFAULT '1',
`networkoperator` varchar(6) COLLATE latin1_danish_ci NOT NULL,
`serviceoperator` varchar(6) COLLATE latin1_danish_ci NOT NULL,
`numbertype` varchar(6) COLLATE latin1_danish_ci NOT NULL,
`lastupdate` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
`lastupdateFile` varchar(255) COLLATE latin1_danish_ci NOT NULL,
PRIMARY KEY (`id`),
KEY `rangestart_2` (`rangestart`,`rangeend`),
KEY `rangelength` (`rangelength`)
) ENGINE=MyISAM AUTO_INCREMENT=189138 DEFAULT CHARSET=latin1 COLLATE=latin1_danish_ci |

The table contains 187,500 rows.

Im running queries like this:

SELECT `networkoperator`,`numbertype` 
FROM `och`.`ochrange` 
WHERE '20972128' 
  BETWEEN `rangestart` AND `rangeend` 
ORDER BY `rangelength` ASC  LIMIT 1;


mysql> EXPLAIN SELECT `networkoperator`,`numbertype` 
-> FROM `och`.`ochrange` 
-> WHERE '20972128' 
-> BETWEEN `rangestart` AND `rangeend` 
-> ORDER BY `rangelength` ASC LIMIT 1;
+----+-------------+----------+-------+---------------+-------------+---------+------+------+-------------+
| id | select_type | table    | type  | possible_keys | key         | key_len | ref  | rows | Extra       |
+----+-------------+----------+-------+---------------+-------------+---------+------+------+-------------+
|  1 | SIMPLE      | ochrange | index | rangestart_2  | rangelength | 4       | NULL |   46 | Using where |
+----+-------------+----------+-------+---------------+-------------+---------+------+------+-------------+
1 row in set (0.00 sec)

There are no other queries in the slow log, and the number of other queries is minimal.

Im able to do 60 qps like this, before my CPU is maxed out, and the server has a load about 150, and I'm using 21000 Mhz on the VMWare host.

I have no IO wait (0.5%) and the memory usage seems fine.

The query cache is disabled as no select will be the same in a short period.

Anybody have any suggestions about how the get more qps ?

Here are my server variables:

Variable_name: auto_increment_increment
        Value: 1

Variable_name: auto_increment_offset
        Value: 1

Variable_name: autocommit
        Value: ON

Variable_name: automatic_sp_privileges
        Value: ON

Variable_name: back_log
        Value: 50

Variable_name: basedir
        Value: /usr

Variable_name: big_tables
        Value: OFF

Variable_name: binlog_cache_size
        Value: 32768

Variable_name: binlog_direct_non_transactional_updates
        Value: OFF

Variable_name: binlog_format
        Value: STATEMENT

Variable_name: binlog_stmt_cache_size
        Value: 32768

Variable_name: bulk_insert_buffer_size
        Value: 8388608

Variable_name: character_set_client
        Value: utf8

Variable_name: character_set_connection
        Value: utf8

Variable_name: character_set_database
        Value: latin1

Variable_name: character_set_filesystem
        Value: binary

Variable_name: character_set_results
        Value: utf8

Variable_name: character_set_server
        Value: latin1

Variable_name: character_set_system
        Value: utf8

Variable_name: character_sets_dir
        Value: /usr/share/mysql/charsets/

Variable_name: collation_connection
        Value: utf8_general_ci

Variable_name: collation_database
        Value: latin1_swedish_ci

Variable_name: collation_server
        Value: latin1_swedish_ci

Variable_name: completion_type
        Value: NO_CHAIN

Variable_name: concurrent_insert
        Value: AUTO

Variable_name: connect_timeout
        Value: 10

Variable_name: datadir
        Value: /var/lib/mysql/

Variable_name: date_format
        Value: %Y-%m-%d

Variable_name: datetime_format
        Value: %Y-%m-%d %H:%i:%s

Variable_name: default_storage_engine
        Value: InnoDB

Variable_name: default_week_format
        Value: 0

Variable_name: delay_key_write
        Value: ON

Variable_name: delayed_insert_limit
        Value: 100

Variable_name: delayed_insert_timeout
        Value: 300

Variable_name: delayed_queue_size
        Value: 1000

Variable_name: div_precision_increment
        Value: 4

Variable_name: engine_condition_pushdown
        Value: ON

Variable_name: error_count
        Value: 0

Variable_name: event_scheduler
        Value: OFF

Variable_name: expire_logs_days
        Value: 7

Variable_name: external_user
        Value: 

Variable_name: flush
        Value: OFF

Variable_name: flush_time
        Value: 0

Variable_name: foreign_key_checks
        Value: ON

Variable_name: ft_boolean_syntax
        Value: + -><()~*:""&|

Variable_name: ft_max_word_len
        Value: 84

Variable_name: ft_min_word_len
        Value: 4

Variable_name: ft_query_expansion_limit
        Value: 20

Variable_name: ft_stopword_file
        Value: (built-in)

Variable_name: general_log
        Value: OFF

Variable_name: general_log_file
        Value: /var/lib/mysql/db-nrlookup.log

Variable_name: group_concat_max_len
        Value: 1024

Variable_name: have_compress
        Value: YES

Variable_name: have_crypt
        Value: YES

Variable_name: have_csv
        Value: YES

Variable_name: have_dynamic_loading
        Value: YES

Variable_name: have_geometry
        Value: YES

Variable_name: have_innodb
        Value: YES

Variable_name: have_ndbcluster
        Value: NO

Variable_name: have_openssl
        Value: DISABLED

Variable_name: have_partitioning
        Value: YES

Variable_name: have_profiling
        Value: YES

Variable_name: have_query_cache
        Value: YES

Variable_name: have_rtree_keys
        Value: YES

Variable_name: have_ssl
        Value: DISABLED

Variable_name: have_symlink
        Value: YES

Variable_name: hostname
        Value: db-nrlookup

Variable_name: identity
        Value: 0

Variable_name: ignore_builtin_innodb
        Value: OFF

Variable_name: init_connect
        Value: 

Variable_name: init_file
        Value: 

Variable_name: init_slave
        Value: 

Variable_name: innodb_adaptive_flushing
        Value: ON

Variable_name: innodb_adaptive_hash_index
        Value: ON

Variable_name: innodb_additional_mem_pool_size
        Value: 8388608

Variable_name: innodb_autoextend_increment
        Value: 8

Variable_name: innodb_autoinc_lock_mode
        Value: 1

Variable_name: innodb_buffer_pool_instances
        Value: 1

Variable_name: innodb_buffer_pool_size
        Value: 134217728

Variable_name: innodb_change_buffering
        Value: all

Variable_name: innodb_checksums
        Value: ON

Variable_name: innodb_commit_concurrency
        Value: 0

Variable_name: innodb_concurrency_tickets
        Value: 500

Variable_name: innodb_data_file_path
        Value: ibdata1:10M:autoextend

Variable_name: innodb_data_home_dir
        Value: 

Variable_name: innodb_doublewrite
        Value: ON

Variable_name: innodb_fast_shutdown
        Value: 1

Variable_name: innodb_file_format
        Value: Antelope

Variable_name: innodb_file_format_check
        Value: ON

Variable_name: innodb_file_format_max
        Value: Antelope

Variable_name: innodb_file_per_table
        Value: OFF

Variable_name: innodb_flush_log_at_trx_commit
        Value: 1

Variable_name: innodb_flush_method
        Value: 

Variable_name: innodb_force_load_corrupted
        Value: OFF

Variable_name: innodb_force_recovery
        Value: 0

Variable_name: innodb_io_capacity
        Value: 200

Variable_name: innodb_large_prefix
        Value: OFF

Variable_name: innodb_lock_wait_timeout
        Value: 50

Variable_name: innodb_locks_unsafe_for_binlog
        Value: OFF

Variable_name: innodb_log_buffer_size
        Value: 8388608

Variable_name: innodb_log_file_size
        Value: 5242880

Variable_name: innodb_log_files_in_group
        Value: 2

Variable_name: innodb_log_group_home_dir
        Value: ./

Variable_name: innodb_max_dirty_pages_pct
        Value: 75

Variable_name: innodb_max_purge_lag
        Value: 0

Variable_name: innodb_mirrored_log_groups
        Value: 1

Variable_name: innodb_old_blocks_pct
        Value: 37

Variable_name: innodb_old_blocks_time
        Value: 0

Variable_name: innodb_open_files
        Value: 300

Variable_name: innodb_print_all_deadlocks
        Value: OFF

Variable_name: innodb_purge_batch_size
        Value: 20

Variable_name: innodb_purge_threads
        Value: 0

Variable_name: innodb_random_read_ahead
        Value: OFF

Variable_name: innodb_read_ahead_threshold
        Value: 56

Variable_name: innodb_read_io_threads
        Value: 4

Variable_name: innodb_replication_delay
        Value: 0

Variable_name: innodb_rollback_on_timeout
        Value: OFF

Variable_name: innodb_rollback_segments
        Value: 128

Variable_name: innodb_spin_wait_delay
        Value: 6

Variable_name: innodb_stats_method
        Value: nulls_equal

Variable_name: innodb_stats_on_metadata
        Value: ON

Variable_name: innodb_stats_sample_pages
        Value: 8

Variable_name: innodb_strict_mode
        Value: OFF

Variable_name: innodb_support_xa
        Value: ON

Variable_name: innodb_sync_spin_loops
        Value: 30

Variable_name: innodb_table_locks
        Value: ON

Variable_name: innodb_thread_concurrency
        Value: 0

Variable_name: innodb_thread_sleep_delay
        Value: 10000

Variable_name: innodb_use_native_aio
        Value: OFF

Variable_name: innodb_use_sys_malloc
        Value: ON

Variable_name: innodb_version
        Value: 5.5.34

Variable_name: innodb_write_io_threads
        Value: 4

Variable_name: insert_id
        Value: 0

Variable_name: interactive_timeout
        Value: 28800

Variable_name: join_buffer_size
        Value: 131072

Variable_name: keep_files_on_create
        Value: OFF

Variable_name: key_buffer_size
        Value: 8589934592

Variable_name: key_cache_age_threshold
        Value: 300

Variable_name: key_cache_block_size
        Value: 1024

Variable_name: key_cache_division_limit
        Value: 100

Variable_name: large_files_support
        Value: ON

Variable_name: large_page_size
        Value: 0

Variable_name: large_pages
        Value: OFF

Variable_name: last_insert_id
        Value: 0

Variable_name: lc_messages
        Value: en_US

Variable_name: lc_messages_dir
        Value: /usr/share/mysql/

Variable_name: lc_time_names
        Value: en_US

Variable_name: license
        Value: GPL

Variable_name: local_infile
        Value: ON

Variable_name: lock_wait_timeout
        Value: 31536000

Variable_name: locked_in_memory
        Value: OFF

Variable_name: log
        Value: OFF

Variable_name: log_bin
        Value: ON

Variable_name: log_bin_trust_function_creators
        Value: OFF

Variable_name: log_error
        Value: /var/log/mysql/error.log

Variable_name: log_output
        Value: FILE

Variable_name: log_queries_not_using_indexes
        Value: OFF

Variable_name: log_slave_updates
        Value: OFF

Variable_name: log_slow_queries
        Value: ON

Variable_name: log_warnings
        Value: 1

Variable_name: long_query_time
        Value: 10.000000

Variable_name: low_priority_updates
        Value: OFF

Variable_name: lower_case_file_system
        Value: OFF

Variable_name: lower_case_table_names
        Value: 0

Variable_name: max_allowed_packet
        Value: 134217728

Variable_name: max_binlog_cache_size
        Value: 18446744073709547520

Variable_name: max_binlog_size
        Value: 209715200

Variable_name: max_binlog_stmt_cache_size
        Value: 18446744073709547520

Variable_name: max_connect_errors
        Value: 10

Variable_name: max_connections
        Value: 8000

Variable_name: max_delayed_threads
        Value: 20

Variable_name: max_error_count
        Value: 64

Variable_name: max_heap_table_size
        Value: 16777216

Variable_name: max_insert_delayed_threads
        Value: 20

Variable_name: max_join_size
        Value: 18446744073709551615

Variable_name: max_length_for_sort_data
        Value: 1024

Variable_name: max_long_data_size
        Value: 134217728

Variable_name: max_prepared_stmt_count
        Value: 16382

Variable_name: max_relay_log_size
        Value: 0

Variable_name: max_seeks_for_key
        Value: 18446744073709551615

Variable_name: max_sort_length
        Value: 1024

Variable_name: max_sp_recursion_depth
        Value: 0

Variable_name: max_tmp_tables
        Value: 32

Variable_name: max_user_connections
        Value: 0

Variable_name: max_write_lock_count
        Value: 18446744073709551615

Variable_name: metadata_locks_cache_size
        Value: 1024

Variable_name: min_examined_row_limit
        Value: 0

Variable_name: multi_range_count
        Value: 256

Variable_name: myisam_data_pointer_size
        Value: 6

Variable_name: myisam_max_sort_file_size
        Value: 9223372036853727232

Variable_name: myisam_mmap_size
        Value: 18446744073709551615

Variable_name: myisam_recover_options
        Value: BACKUP

Variable_name: myisam_repair_threads
        Value: 1

Variable_name: myisam_sort_buffer_size
        Value: 8388608

Variable_name: myisam_stats_method
        Value: nulls_unequal

Variable_name: myisam_use_mmap
        Value: OFF

Variable_name: net_buffer_length
        Value: 16384

Variable_name: net_read_timeout
        Value: 30

Variable_name: net_retry_count
        Value: 10

Variable_name: net_write_timeout
        Value: 60

Variable_name: new
        Value: OFF

Variable_name: old
        Value: OFF

Variable_name: old_alter_table
        Value: OFF

Variable_name: old_passwords
        Value: ON

Variable_name: open_files_limit
        Value: 40000

Variable_name: optimizer_prune_level
        Value: 1

Variable_name: optimizer_search_depth
        Value: 62

Variable_name: optimizer_switch
        Value: index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on

Variable_name: performance_schema
        Value: OFF

Variable_name: performance_schema_events_waits_history_long_size
        Value: 10000

Variable_name: performance_schema_events_waits_history_size
        Value: 10

Variable_name: performance_schema_max_cond_classes
        Value: 80

Variable_name: performance_schema_max_cond_instances
        Value: 1000

Variable_name: performance_schema_max_file_classes
        Value: 50

Variable_name: performance_schema_max_file_handles
        Value: 32768

Variable_name: performance_schema_max_file_instances
        Value: 10000

Variable_name: performance_schema_max_mutex_classes
        Value: 200

Variable_name: performance_schema_max_mutex_instances
        Value: 1000000

Variable_name: performance_schema_max_rwlock_classes
        Value: 30

Variable_name: performance_schema_max_rwlock_instances
        Value: 1000000

Variable_name: performance_schema_max_table_handles
        Value: 100000

Variable_name: performance_schema_max_table_instances
        Value: 50000

Variable_name: performance_schema_max_thread_classes
        Value: 50

Variable_name: performance_schema_max_thread_instances
        Value: 1000

Variable_name: pid_file
        Value: /var/run/mysqld/mysqld.pid

Variable_name: plugin_dir
        Value: /usr/lib/mysql/plugin/

Variable_name: port
        Value: 3306

Variable_name: preload_buffer_size
        Value: 32768

Variable_name: profiling
        Value: OFF

Variable_name: profiling_history_size
        Value: 15

Variable_name: protocol_version
        Value: 10

Variable_name: proxy_user
        Value: 

Variable_name: pseudo_slave_mode
        Value: OFF

Variable_name: pseudo_thread_id
        Value: 30736

Variable_name: query_alloc_block_size
        Value: 8192

Variable_name: query_cache_limit
        Value: 8388608

Variable_name: query_cache_min_res_unit
        Value: 4096

Variable_name: query_cache_size
        Value: 0

Variable_name: query_cache_type
        Value: ON

Variable_name: query_cache_wlock_invalidate
        Value: OFF

Variable_name: query_prealloc_size
        Value: 8192

Variable_name: rand_seed1
        Value: 0

Variable_name: rand_seed2
        Value: 0

Variable_name: range_alloc_block_size
        Value: 4096

Variable_name: read_buffer_size
        Value: 131072

Variable_name: read_only
        Value: OFF

Variable_name: read_rnd_buffer_size
        Value: 262144

Variable_name: relay_log
        Value: 

Variable_name: relay_log_index
        Value: 

Variable_name: relay_log_info_file
        Value: relay-log.info

Variable_name: relay_log_purge
        Value: ON

Variable_name: relay_log_recovery
        Value: OFF

Variable_name: relay_log_space_limit
        Value: 0

Variable_name: report_host
        Value: 

Variable_name: report_password
        Value: 

Variable_name: report_port
        Value: 3306

Variable_name: report_user
        Value: 

Variable_name: rpl_recovery_rank
        Value: 0

Variable_name: secure_auth
        Value: OFF

Variable_name: secure_file_priv
        Value: 

Variable_name: server_id
        Value: 7

Variable_name: skip_external_locking
        Value: ON

Variable_name: skip_name_resolve
        Value: OFF

Variable_name: skip_networking
        Value: OFF

Variable_name: skip_show_database
        Value: OFF

Variable_name: slave_compressed_protocol
        Value: OFF

Variable_name: slave_exec_mode
        Value: STRICT

Variable_name: slave_load_tmpdir
        Value: /tmp

Variable_name: slave_max_allowed_packet
        Value: 1073741824

Variable_name: slave_net_timeout
        Value: 3600

Variable_name: slave_skip_errors
        Value: OFF

Variable_name: slave_transaction_retries
        Value: 10

Variable_name: slave_type_conversions
        Value: 

Variable_name: slow_launch_time
        Value: 2

Variable_name: slow_query_log
        Value: ON

Variable_name: slow_query_log_file
        Value: /var/lib/mysql/db-nrlookup-slow.log

Variable_name: socket
        Value: /var/run/mysqld/mysqld.sock

Variable_name: sort_buffer_size
        Value: 2097152

Variable_name: sql_auto_is_null
        Value: OFF

Variable_name: sql_big_selects
        Value: ON

Variable_name: sql_big_tables
        Value: OFF

Variable_name: sql_buffer_result
        Value: OFF

Variable_name: sql_log_bin
        Value: ON

Variable_name: sql_log_off
        Value: OFF

Variable_name: sql_low_priority_updates
        Value: OFF

Variable_name: sql_max_join_size
        Value: 18446744073709551615

Variable_name: sql_mode
        Value: 

Variable_name: sql_notes
        Value: ON

Variable_name: sql_quote_show_create
        Value: ON

Variable_name: sql_safe_updates
        Value: OFF

Variable_name: sql_select_limit
        Value: 18446744073709551615

Variable_name: sql_slave_skip_counter
        Value: 0

Variable_name: sql_warnings
        Value: OFF

Variable_name: ssl_ca
        Value: 

Variable_name: ssl_capath
        Value: 

Variable_name: ssl_cert
        Value: 

Variable_name: ssl_cipher
        Value: 

Variable_name: ssl_key
        Value: 

Variable_name: storage_engine
        Value: InnoDB

Variable_name: stored_program_cache
        Value: 256

Variable_name: sync_binlog
        Value: 0

Variable_name: sync_frm
        Value: ON

Variable_name: sync_master_info
        Value: 0

Variable_name: sync_relay_log
        Value: 0

Variable_name: sync_relay_log_info
        Value: 0

Variable_name: system_time_zone
        Value: CET

Variable_name: table_definition_cache
        Value: 400

Variable_name: table_open_cache
        Value: 4096

Variable_name: thread_cache_size
        Value: 64

Variable_name: thread_concurrency
        Value: 10

Variable_name: thread_handling
        Value: one-thread-per-connection

Variable_name: thread_stack
        Value: 196608

Variable_name: time_format
        Value: %H:%i:%s

Variable_name: time_zone
        Value: SYSTEM

Variable_name: timed_mutexes
        Value: OFF

Variable_name: timestamp
        Value: 1385625067

Variable_name: tmp_table_size
        Value: 16777216

Variable_name: tmpdir
        Value: /tmp

Variable_name: transaction_alloc_block_size
        Value: 8192

Variable_name: transaction_prealloc_size
        Value: 4096

Variable_name: tx_isolation
        Value: REPEATABLE-READ

Variable_name: unique_checks
        Value: ON

Variable_name: updatable_views_with_limit
        Value: YES

Variable_name: version
        Value: 5.5.34-0ubuntu0.12.04.1-log

Variable_name: version_comment
        Value: (Ubuntu)

Variable_name: version_compile_machine
        Value: x86_64

Variable_name: version_compile_os
        Value: debian-linux-gnu

Variable_name: wait_timeout
        Value: 28800

Variable_name: warning_count
        Value: 0

Answer 1

Based on reading the query plan you've posted from the explain output, you will probably have difficulty believing the explanation of how this query is actually being processed by the server... but the explanation does illustrate why the performance would not be good.

Since you've asked for the results to be ordered by `rangelength` and since the B-TREE index on (`rangestart`,`rangeend`) is poorly-suited to resolving "x between y and z" expressions, the optimizer has decided to use the index on `rangelength` to determine an order in which it will proceed to read every row, if necessary, in the entire table (type = index), in ascending order as sorted by the index on rangelength (type = index, key = rangelength), until it finds the first row where (extra = using where) the where clause is matched. Since the rows are being read in the desired order-by, the server can stop after the first row... so I would assume this query exhibits substantial variability depending on how much of the table or index has to be scanned to resolve any particular value.

There are two approaches that come to mind to improve this.

Option 1: The first suggestion would be to add an index that includes all three values you're sorting by and selecting by... but not for the usual reasons, because the query isn't going to use it quite like that.

ALTER TABLE ochrange ADD KEY(rangelength,rangeend,rangestart);

This is still far from the ideal index for this query, but it has three advantages over what you have now:

1. it's already sorted by rangelength
2. it narrows down the number of comparisons needed, because for any given rangelength, the rangestart values that are too high can be ignored
3. while it isn't truly a covering index, all of the values of interest in the WHERE clause are found within the index, so the optimizer should be able to qualify or disqualify the rows based on an index scan instead of having to read the table data, and might be able to do more.

Very important note on point 3: I am not saying this index will be used to look up the matching rows, because it can't exactly be used for that. It should at least, however, be used more effectively than the current plan because it contains values we need to use for filtering and because it may also allow out of range values for rangeend to be quickly eliminated, and among the remaining values, it may allow out of range values for rangestart to also be eliminated.

I would also recommend that the where clause be written in a less-ambiguous but logically equivalent form, to potentially make things a little bit easier on the optimizer:

  WHERE 20972128 
BETWEEN `rangestart` AND `rangeend` 
  ORDER BY `rangelength` ASC  LIMIT 1;

...becomes this:

  WHERE rangestart <= 20972128 
    AND rangeend >= 20972128
  ORDER BY rangelength ASC  LIMIT 1;

The (rangestart,rangeend) index, at first glance, seems like it would have been more useful, but a 2-column B-Tree isn't well-suited for finding values between the low and high bounds, like this.

The residential telephone directory is a fitting analogy for a two-column index on (last_name, first_name) and illustrates why this kind of index doesn't provide as much benefit as it would seem to.

In such a directory, given the last name "Smith" and first name "John," it is easy to find all of the people named Smith, and very easy to find first name John accompanying last name Smith. It is quite impossible, though, to use the index in a telephone directory to find all of the people with first name John regardless of last name.

What we're asking of the index in this query, whether written the original way or in my suggested way, is to find all of the rows where 'rangestart' <= 20972128 with accompanying rangeend >= 20972128 in the same row. This would be like trying to find all of the people in a telephone directory with a last name of Smith or any other last name that appears prior to Smith in the directory, and of those people, find those with the first name of John, or any other name that is lexically (alphabetically) "greater than" (after) John. The task would be tedious, and our only consolation is that we don't have to examine any of the pages in the directory that follow Smith, but we have to examine every entry on every preceding page before we can find what we are looking for.

Still, Option #1, adding a new index, seems worth a try. After testing with that index, it could also be worthwhile to add yet another index, this one on (rangelength,rangestart,rangeend), to see which one the optimizer prefers to use. Hopefully it will use one of them, and depending on the data in the table and the values in the query, it might alternate and it might not.

Option #2 is apparently a little bit "outside the box" in some people's minds, but it is a solution that I use for finding the specific block of IP addresses (IPv4 addresses are essentially INT UNSIGNED, with low/high boundaries) where a particular IP address lies, for geocoding. I caught some grief for suggesting this technique once over on Stack Overflow, but I can only conclude that the people voicing objections were simply "thinking small" because I really see no reason that this isn't an excellent solution. The topic I am referring to is spatial indexes. I assume the objections I encountered were based on the assumption that MySQL's Spatial Extensions were originally intended for manipulating geospatial data... but to limit their use to only latitude and longitude is not justified at all.

Spatial indexes in MySQL are implemented as R-Trees.

The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in R-tree is for rectangle. Since all objects lie within this bounding rectangle, a query that does not intersect the bounding rectangle also cannot intersect any of the contained objects. At the leaf level, each rectangle describes a single object; at higher levels the aggregation of an increasing number of objects. This can also be seen as an increasingly coarse approximation of the data set.

^{— http://en.wikipedia.org/wiki/R-tree}

We are trying to find the position in a "space" of values where a particular value exists, so it makes sense to utilize an index structure designed to resolve which "spaces" a particular object fits inside... a spatial index.

Technically, the rangstart/rangeend continuum is a one-dimensional space, since it is made up of points within ranges that all exist on a continuous line, though I personally find it easier to explain if each pair of (rangestart, rangeend) is illustrated as a box, from (min,min) to (max,min) to (max,max) to (min,max) and back down to (min,min) again. It's easy from this example to see that if we have an index structure that can quickly determine which sets of boxes our particular point in space does or doesn't exist in, then we can quickly traverse that index to find the right spot. In this case, we'd have to find the right sets of boxes and then find the smallest box among those boxes (assuming my guess about the nature of the content of "rangelength" is correct) where our little point (effectively a "box" with 0 height and 0 width) fits in.

Rather than duplicate work that's already been done, I'll refer to Jeremy Cole's write-up of the subject:

http://blog.jcole.us/2007/11/24/on-efficiently-geo-referencing-ips-with-maxmind-geoip-and-mysql-gis/

I approach this slightly differently, but the principles are all there, and once you understand what's happening here, I suspect you will see this as a good fit for what you're trying to do and may implement it slightly differently than either of us.

But one final point about spatial indexes. Here's an example of my query where the spatial column is called 'node_polygon' and is of type GEOMETRY:

SELECT ...
  FROM geo_block b
 WHERE MBRContains(b.node_polygon,POINT(in_ip_unsigned,in_ip_unsigned))

I mention this query structure because it illustrates an important point. It is almost always the case that when you use a column as an argument to a function in the WHERE clause, that is bad design because it prevents indexes from being used to resolve the expression and will cause a full table scan or something analogous to it.

WHERE YEAR(birthday) = 1973;                                # bad
WHERE birthday >= '1973-01-01' AND birthday < '1974-01-01'; # good

The former expression has to evaluate YEAR() for the 'birthday' column in every row, while the latter expression can take advantage of an index on 'birthday' and do a range scan.

Spatial indexes are different, because the MBRContains() and MBRWithin() functions are understood by the optimizer to mean that the column and the constant should be evaluated with respect to the range that the constant identifies within the spatial index. These "functions" are rare examples of functions that still allow the optimizer to realize that it knows a better way to resolve the query than to evaluate the function against each row.

In my application, I don't need ordering, because the table is constrained such that no two entries can touch or overlap -- every given IP address either fits into exactly one block, or fits into no blocks at all. In your case, you still presumably need to order by rangelength, and what I would try, depending on whether you build the geometry structures lines or boxes, would be testing your performance while ordering by an appropriate geometry function, such as Area() or Glength(), to directly compare the size of the range, as opposed to using the rangelength column. I don't know which will perform better, geometric functions or ordering by the existing column rangelength.

---

Side note, as pointed out in comments, you should also not quote the integer that you're using in the where clause, since it's matching against an integer column and by quoting it you're causing an implicit cast of one thing to the other thing (either the literal is being cast to an integer or each value of rangestart/rangeend is being cast to a string) for comparison. The server is probably doing the right thing and casting the string to an integer but it would be better to query with the same data type as you're matching.