Indexes not being used--why not?

[Margaret MacDonald]

I have a table of about 173K records, organised as a logical n-way tree. Each record has a unique identifier (recid) and a field (parent_recid) that holds the recid of its logical parent.

I submit a query that left-joins the table to itself so that on the one side I'm looking up some subset with a WHERE that involves 2-3 fields, and on the other the parent of each of those records using the parent_recid=recid equality.

It reliably takes about .75-.85 seconds to perform that query (on my dev machine, which is a 2GHz P4 with 1GB and SCSI2 discs, running W2K). Each of the fields is indexed, but the explain doesn't mention the key K3 under 'possible' and anyway claims not to use the indexes at all for the main lookup:

id 1
select_type SIMPLE
table child
type ALL
possible_keys K1, K2, K2_2
key
key_len
ref
rows 173123
Extra Using where; Using temporary; Using filesort
id 1
select_type SIMPLE
table parent
type eq_ref
possible_keys PRIMARY
key PRIMARY
key_len 32
ref db.child.parent_recid
rows 1
Extra

Any insights as to what might be going on?