MySQL: how to determine which rows in tables A and B are referenced by rows in table C in linear time?

I am working with a poorly designed database that I am not at liberty to restructure. In this database, there are three tables (let's call them 'companiesA', 'companiesB', and 'items') that are involved in a query that I need to optimize. 'companiesA' and 'companiesB' describe companies in the same way in that the column values are the same, but they represent two different groups of companies and have different column names. Essentially, the ID and company name columns are 'aID' and 'aName' in 'companiesA', and 'idB' and 'nameB' in 'companiesB'. 'items' contains a column, 'companyID', that contains a foreign key value from one of the two company tables.

The query I need to optimize gets a page's worth of company IDs and names from the union of the two tables, sorted by the names column, with an added column that states whether the row's company has any items associated with it. This query can also filter by the company names if the user requests it in the front-end. In its current state, I think it runs in THETA(companies * items) time, which is prohibitively slow:

select
  a.aID as companyID,
  a.aName as companyName,
  (select
     count(companyID)
   from
     items
   where
     companyID = a.aID
  ) as items
from
  companiesA as a
where
  a.aName like '%<string>%'

union

select
  b.idB as companyID,
  b.nameB as companyName,
  (select
     count(companyID)
   from
     items
   where
     companyID = b.idB
  ) as items
from
  companiesB as b
where
  b.nameB like '%<string>%'

order by
  companyName ASC
limit
  [optional_starting_index, ] 50;

It is not important that the items column contain the actual counts as this query returns (it was the only way I could figure out to cleanly return a value regarding the entire 'items' table). I suppose that I can count myself fortunate that with 1500 companies and 9000 items, this algorithm only takes seven seconds.

If I were writing this in another language in which I had access to the tables myself, I could easily write this in O(companies + items) time, but I am finding it difficult to figure out how to do so in MySQL. Is it possible to 开发者_如何学Godo this, preferably without stored functions or procedures? I CAN add them if necessary, but I have had a hard time adding them through phpMyAdmin now that the server's host only allows that interface to access the database by GUI.

---

In this solution, I took the daring assumption that the company names in each of the tables are unique by using Union All. If they are not, then you can switch back to Union but you'll get the performance hit of making the list unique. Basically, I'm eliminating your need for correlated subqueries to return the counts by using derived tables.

Select Companies.CompanyID, Companies.CompanyName
    , Coalesce(ItemTotals.ItemCount,0) As ItemCount
From    (
        Select a.aID As CompanyID, a.aName As CompanyName
        From companiesA As a
        Where a.aName Like '%<string>%'
        Union All
        Select b.IDB, b.nameB
        From companiesB As b
        Where b.bName Like '%<string>%'
        ) As Companies
    Left Join   (
                Select companyID, Count(*) As ItemCount
                From items
                Group By companyID
                ) As ItemTotals
            On ItemTotals.companyID = Companies.CompanyID
Order By Company.CompanyName

Here is another variant. This one is similar to your original except that I replaced the correlated subqueries with two Group By queries. As before, if the names and IDs between the two tables are mutually exclusive, you can use Union All otherwise you will need to use Union.

Select Z.CompanyId, Z.CompanyName, Z.ItemCount
From    (
        Select A.companyID, A.aName As CompanyName
            , Count(I.CompanyID) As ItemCount
        From companiesA As A
            Left Join items As I
                On I.CompanyId = A.CompanyId
        Where A.aName Like '%<string>%'
        Group By A.companyID, A.aName
        Union All
        Select B.companyID, B.bName, Count(I.CompanyID)
        From companiesB As B
            Left Join items As I
                On I.CompanyId = B.CompanyId
        Where B.bName Like '%<string>%'
        Group By B.companyID, B.bName
        ) As Z
Order By Z.CompanyName