mySQL: ¿es posible hacer esta consulta más rápido?

Question

Tengo una tabla de "prueba" que contiene millones de entradas. Cada fila contiene una "característica" de coma flotante y un "recuento" de la frecuencia con la que esta característica está presente en el elemento "id". La clave principal para esta tabla es la combinación de "id" y "característica", es decir, cada elemento puede tener múltiples funciones. Por lo general, hay un par de cientos a un par de miles de entradas de función por ID de artículo.

create table test 
(
    id  int not null, 
    feature double not null, 
    count int not null 
); 

La tarea es encontrar los 500 elementos más similares a un elemento de referencia dado. La similitud se mide en el número de valores de características idénticas en ambos elementos. La consulta que he encontrado se cita a continuación, pero a pesar de utilizar índices de forma adecuada, su plan de ejecución todavía contiene "usar temporal" y "usar archivado", lo que da un rendimiento inaceptable para mi caso de uso.

select 
    t1.id, 
    t2.id, 
    sum(least(t1.count, t2.count)) as priority 
from test as t1 
inner join test as t2 
    on t2.feature = t1.feature 
where t1.id = {some user supplied id value} 
group by t1.id, t2.id 
order by priority desc 
limit 500; 

¿Alguna idea de cómo mejorar esto? El esquema se puede modificar e incluir índices según sea necesario.

Answer 1

Con el esquema actual, esta consulta difícilmente se puede mejorar.

Ya tiene un índice en feature y esto es lo mejor que puede hacer con el diseño de esquema actual.

El problema es más similar que no es una relación de orden.Si a es más similar a b que a c, esto no implica que c sea menos similar a a que a b. Por lo tanto, no puede compilar un solo índice que describa esta relación, y debe hacerlo para cada elemento por separado, lo que haría que su índice N^2 sea extenso, donde N es el número de elementos.

Si siempre necesita solo los mejores artículos 500, puede limitar su índice a esa cifra (en cuyo caso tendrá 500 * N entradas).

MySQL no admite vistas indizadas o materializado, por lo que tendrá que hacerlo usted mismo:

1. Crear una tabla como la siguiente:

   CREATE TABLE similarity 
        (
        id1 INT NOT NULL, 
        id2 INT NOT NULL, 
        similarity DOUBLE NOT NULL, 
        PRIMARY KEY (id1, id2), 
        KEY (id1, similarity) 
        ) 
   

2. Cada vez que inserte una nueva característica en la tabla, refleja los cambios en el similarity:

   INSERT 
   INTO similarity 
   SELECT @newid, id, 
        LEAST(@newcount, count) AS ns 
   FROM test 
   WHERE feature = @newfeature 
        AND id <> @newid 
   ON DUPLICATE KEY UPDATE 
   SET  similarity = similarity + ns; 
   
   
   INSERT 
   INTO similarity 
   SELECT @newid, id, 
        LEAST(@newcount, count) AS ns 
   FROM test 
   WHERE feature = @newfeature 
        AND id <> @newid 
   ON DUPLICATE KEY UPDATE 
   SET  similarity = similarity + ns; 
   

3. en forma oportuna, eliminar el exceso de similitudes:

   DELETE s 
   FROM (
        SELECT id1, 
          (
          SELECT similarity 
          FROM similarity si 
          WHERE si.id1 = s.id1 
          ORDER BY 
            si.id1 DESC, si.similarity DESC 
          LIMIT 499, 1 
          ) AS cs 
        FROM (
          SELECT DISTINCT id1 
          FROM similarity 
          ) s 
        ) q 
   JOIN similarity s 
   ON  s.id1 = q.id1 
        AND s.similarity < q.cs 
   

4. consultar sus datos:

   SELECT id2 
   FROM similarity 
   WHERE id1 = @myid 
   ORDER BY 
        similarity DESC 
   LIMIT 500 
   

Answer 2

Una optimización sería excluir el objeto mismo de la autocombinación:

inner join test as t2 
    on t2.feature = t1.feature and t2.id <> t1.id 
            ^^^^^^^^^^^^^^ 

Para mayor aumento de velocidad, crear un índice de cobertura de (feature, id, count).

Answer 3

Tener un número de punto flotante como parte de la clave principal (PK) es un asesino. Por lo demás, no debería ser una parte de cualquier restricción - clave única (Reino Unido), clave externa (FK), etc.

Para mejorar el rendimiento de la consulta SQL muchas veces, trate de cambiar el esquema de la siguiente manera:

CREATE TABLE test ( 
item_id  INTEGER, 
feature_id INTEGER, 
count INTEGER); 

CREATE TABLE features (
id INTEGER, feature_value double not null); 

CREATE TABLE items (
id INTEGER, item_description varchar2(100) not null); 

ALTER TABLE test ADD CONSTRAINT fk_test_item_id foreign key (item_id) references items(id); 

ALTER TABLE test ADD CONSTRAINT fk_test_feature_id foreign key(feature_id) references features(id); 

Con su tabla de prueba normalizada como la anterior, he separado los elementos y la función en sus propias tablas separadas y esto se convierte en algo más que una mera tabla de asignación con el recuento de cada asignación.

Si ahora inicia la consulta SQL que ha activado anteriormente con pequeñas modificaciones como se menciona a continuación, debería ver una mejora significativa/drástica en el rendimiento de la consulta SQL.

select t1.id, t2.id, sum(least(t1.count, t2.count)) as priority 
from test as t1 inner join test as t2 on t2.feature_id = t1.feature_id 
where t1.id = {some user supplied id value} 
group by t1.id, t2.id 
order by priority desc 
limit 500; 

¡Salud!

Answer 4

¿Puedes derribarlo en una sola mesa? Al utilizar subconsultas, es posible que pueda evitar la unión y será una ganancia si las subconsultas son más rápidas, indexadas y ejecutadas exactamente una vez. Algo como esto (no probado).

select
t2.id,
SUM(t2.count) as priority
from test as t2
where t2.id = {some user supplied id value} AND
t2.count > (SELECT MIN(count) FROM test t1 WHERE id= {some user supplied value}) AND
t2.feature IN (SELECT feature FROM test t1 WHERE id= {some user supplied value})
group by t1.id
order by priority desc
limit 500;


Si eso no funciona MySQL es terrible en la realización de las mesas selecciona interiores son constantes y se volverá a ejecutarlos para cada fila. Envolviéndolos en una selección nuevamente obliga a una búsqueda constante de la tabla. Aquí hay un truco:


select
t1.id,
SUM(t2.count) as priority
from test as t2
where t2.id = {some user supplied id value} AND
t2.count > (
SELECT * FROM (
SELECT MIN(count) FROM test t1 WHERE id= {some user supplied
value}) as const) AND
t2.feature IN (SELECT * from (
SELECT feature FROM test t1 WHERE id= {some user supplied value}
) as const)
group by t1.id
order by priority desc
limit 500;


Answer 5

Me gustaría empezar con esto ... encantaría escuchar de nuevo en el rendimiento que está mirando a. No creo que necesitaras el MENOR (de los conteos t1 vs t2). Si califica por primera vez en función de ID = {algún valor}, obviamente obtendrá todas esas "características". Luego, a través de una autoinscripción dedicada solo a las "funciones" coincidentes, obtiene un recuento. Dado que está desglosando por ID1 e ID2, cada "característica" respectiva se contará una vez. Al final de esta consulta, dado que no estoy excluyendo explícitamente t2.ID igual a {algún valor de usuario}, su recuento debe ser EXACTAMENTE el MISMO recuento de características en t1, y cualquier otra cosa debajo de eso sería sus otras coincidencias más cercanas .

Me aseguraría de tener un índice de ID y FUNCIÓN.

select STRAIGHT_JOIN 
     t1.id, 
     t2.id, 
     count(*) as MatchedInBoth 
    from 
     test as t1, 
     test as t2 
    where 
      t1.id = {some user value} 
     and t1.feature = t2.feature 
    group by 
     t1.id, 
     t2.id 
    order by 
     MatchedInBoth desc 
    limit 
     500; 

El resultado podría dar algo así como

t1   t2   MatchedInBoth 
{user value} {user value} 275 
{user value} Other ID 1 270 
{user value} Other ID 2 241 
{user value} Other ID 3 218 
{user value} Other ID 4 197 
{user value} Other ID 5 163, etc