Ottimizza query massima groupwise

Question

select * 
from records 
where id in (select max(id) from records group by option_id) 

Questa query funziona bene anche su milioni di righe. Tuttavia come si può vedere dal risultato di spiegare dichiarazione:

           QUERY PLAN 
------------------------------------------------------------------------------------------------------------------------------------------- 
Nested Loop (cost=30218.84..31781.62 rows=620158 width=44) (actual time=1439.251..1443.458 rows=1057 loops=1) 
-> HashAggregate (cost=30218.41..30220.41 rows=200 width=4) (actual time=1439.203..1439.503 rows=1057 loops=1) 
    -> HashAggregate (cost=30196.72..30206.36 rows=964 width=8) (actual time=1438.523..1438.807 rows=1057 loops=1) 
      -> Seq Scan on records records_1 (cost=0.00..23995.15 rows=1240315 width=8) (actual time=0.103..527.914 rows=1240315 loops=1) 
-> Index Scan using records_pkey on records (cost=0.43..7.80 rows=1 width=44) (actual time=0.002..0.003 rows=1 loops=1057) 
    Index Cond: (id = (max(records_1.id))) 
Total runtime: 1443.752 ms 

(cost=0.00..23995.15 rows=1240315 width=8) < - Qui si dice che è la scansione tutte le righe e che è ovviamente inefficiente.

Ho provato anche riordinando la query:

select r.* from records r 
inner join (select max(id) id from records group by option_id) r2 on r2.id= r.id; 

               QUERY PLAN 
------------------------------------------------------------------------------------------------------------------------------- 

Nested Loop (cost=30197.15..37741.04 rows=964 width=44) (actual time=835.519..840.452 rows=1057 loops=1) 
-> HashAggregate (cost=30196.72..30206.36 rows=964 width=8) (actual time=835.471..835.836 rows=1057 loops=1) 
    -> Seq Scan on records (cost=0.00..23995.15 rows=1240315 width=8) (actual time=0.336..348.495 rows=1240315 loops=1) 
-> Index Scan using records_pkey on records r (cost=0.43..7.80 rows=1 width=44) (actual time=0.003..0.003 rows=1 loops=1057) 
    Index Cond: (id = (max(records.id))) 
Total runtime: 840.809 ms 

(cost=0.00..23995.15 rows=1240315 width=8) < - Ancora la scansione di tutte le righe.

ho provato con e senza indice su (option_id), (option_id, id), (option_id, id desc), nessuno di loro ha avuto alcun effetto sul piano di query.

Esiste un modo per eseguire una query massima di gruppo in Postgres senza eseguire la scansione di tutte le righe?

Quello che sto cercando, a livello di programmazione, è un indice che memorizza l'ID massimo per ogni option_id quando vengono inseriti nella tabella dei record. In questo modo, quando chiedo il massimo di option_ids, dovrei solo eseguire la scansione dei record dell'indice tante volte quante sono gli option_id diversi.

Ho visto select distinct on risposte in tutto SO da utenti di alto livello (grazie a @Clodoaldo Neto per avermi fornito le parole chiave da cercare). Ecco perché non funziona:

create index index_name on records(option_id, id desc) 

select distinct on (option_id) * 
from records 
order by option_id, id desc 
               QUERY PLAN 
------------------------------------------------------------------------------------------------------------------------------------------------------------ 
Unique (cost=0.43..76053.10 rows=964 width=44) (actual time=0.049..1668.545 rows=1056 loops=1) 
    -> Index Scan using records_option_id_id_idx on records (cost=0.43..73337.25 rows=1086342 width=44) (actual time=0.046..1368.300 rows=1086342 loops=1) 
Total runtime: 1668.817 ms 

È fantastico, sta utilizzando un indice. Tuttavia, usare un indice per scansionare tutti gli ID non ha molto senso. Secondo le mie esecuzioni, è in realtà più lento di una semplice scansione sequenziale.

Abbastanza interessante, MySQL 5.5 è in grado di ottimizzare la query semplicemente utilizzando un indice su records(option_id, id)

mysql> select count(1) from records; 

+----------+ 
| count(1) | 
+----------+ 
| 1086342 | 
+----------+ 

1 row in set (0.00 sec) 

mysql> explain extended select * from records 
     inner join (select max(id) max_id from records group by option_id) mr 
                 on mr.max_id= records.id; 

+------+----------+--------------------------+ 
| rows | filtered | Extra     | 
+------+----------+--------------------------+ 
| 1056 | 100.00 |       | 
| 1 | 100.00 |       | 
| 201 | 100.00 | Using index for group-by | 
+------+----------+--------------------------+ 

3 rows in set, 1 warning (0.02 sec) 

Answer 1

Supponendo relativamente poche righe options per molte righe in records.

In genere, si avrebbe un look-up table options a cui fa riferimento da records.option_id, idealmente con un foreign key constraint. Se non lo fai, suggerisco di crearne uno per applicare l'integrità referenziale:

CREATE TABLE options (
    option_id int PRIMARY KEY 
, option text UNIQUE NOT NULL 
); 

INSERT INTO options 
SELECT DISTINCT option_id, 'option' || option_id -- dummy option names 
FROM records; 

allora non abbiamo bisogno di emulare un loose index scan più e questo diventa molto semplice e veloce. Le sottoquery correlate possono utilizzare un indice semplice su (option_id, id).

SELECT option_id 
     ,(SELECT max(id) 
     FROM records 
     WHERE option_id = o.option_id 
     ) AS max_id 
FROM options o 
ORDER BY 1; 

Questo include le opzioni con alcuna corrispondenza nella tabella records. Ottieni NULL per max_id e puoi facilmente rimuovere tali righe in un esterno SELECT se necessario.

Or (stesso risultato):

SELECT option_id 
    , (SELECT id 
     FROM records 
     WHERE option_id = o.option_id 
     ORDER BY id DESC NULLS LAST 
     ) AS max_id 
FROM options o 
ORDER BY 1; 

può essere un po 'più veloce. La sottoquery utilizza l'ordinamento DESC NULLS LAST - uguale alla funzione di aggregazione max() che ignora i valori NULL. Ordinamento solo DESC avrebbe NULL prima:

• Why do NULL values come first when ordering DESC in a PostgreSQL query?

Così, l'indice perfetto per questo:

CREATE INDEX on records (option_id, id DESC NULLS LAST); 

non ha molta importanza, mentre le colonne sono definiti NOT NULL.

Ci può ancora essere una scansione sequenziale sul tavolino options, che è solo il modo più veloce per recuperare tutte le righe. Lo ORDER BY può introdurre una scansione di indice (solo) per recuperare righe pre-ordinate.
La grande tabella records è accessibile solo tramite scansione dell'indice (bitmap) - o, se possibile, index-only scan.

SQL Fiddle che mostra due scansioni di solo indice per il caso semplice.

O uso LATERAL si unisce per un effetto simile in Postgres 9.3+:

• Optimize GROUP BY query to retrieve latest record per user

Answer 2

select distinct on (option_id) * 
from records 
order by option_id, id desc 

indici saranno utilizzati solo se il cardinality è favorevole. Detto questo puoi provare un indice composito

create index index_name on records(option_id, id desc) 

Answer 3

Si dice di volere un indice che indicizza solo il massimo (id) per ogni id_opzione. Questo non è attualmente supportato da PostgreSQL. Se tale funzione viene aggiunta in futuro, probabilmente si farebbe attraverso il meccanismo di creare una vista materializzata sulla query aggregata e quindi indicizzare la vista materializzata. Non me lo aspetterei per almeno un paio d'anni, però.

Quello che puoi fare ora, però, è utilizzare una query ricorsiva per saltare l'indice ad ogni valore univoco di option_id. Vedi the PostgreSQL wiki page per una descrizione generale della tecnica.

Il modo in cui è possibile utilizzare questo per il vostro caso scrivi la query ricorsiva per restituire i valori distinti di option_id, e quindi per ciascuno di quelli sub-SELECT il max (id):

with recursive dist as (
    select min(option_id) as option_id from records 
union all 
    select (select min(option_id) from records where option_id > dist.option_id) 
    from dist where dist.option_id is not null 
) 

select option_id, 
    (select max(id) from records where records.option_id=dist.option_id) 
from dist where option_id is not null; 

E 'brutto , ma puoi nasconderlo dietro una vista.

Nelle mie mani questo funziona in 43 ms, anziché 513 ms per la varietà on distinct.

Probabilmente potrebbe essere fatto circa il doppio più velocemente se è possibile trovare un modo per incorporare il massimo (id) nella query ricorsiva, ma non sono riuscito a trovare un modo per farlo. Il problema è che queste query hanno una sintassi piuttosto restrittiva, non è possibile utilizzare "limite" o "ordine per" in combinazione con UNION ALL.

Questa query tocca una pagina molto diffusa in tutto l'indice e, se queste pagine non si adattano alla cache, si verificheranno molti errori di I/O inefficienti. Tuttavia, se questo tipo di query è popolare, le pagine dell'indice foglia 1057 avranno pochi problemi a rimanere nella cache.

Questo è come un set up il mio banco di prova:

create table records as select floor(random()*1057)::integer as option_id, floor(random()*50000000)::integer as id from generate_series(1,1240315); 
create index on records (option_id ,id); 
explain analyze; 

Answer 4

PostgreSQL non supporta la scansione lassa che MySQL è in grado di utilizzare per le query di questo tipo. È lo Using index for group-by che vedi nel piano MySQL.

In pratica, restituisce la prima o l'ultima voce in un intervallo corrispondente a un sottoinsieme di una chiave composta, quindi cerca il valore successivo o precedente di questo sottoinsieme.

Nel tuo caso prima restituisce l'ultimo valore dell'intero indice su (option_id, id) (che per definizione accade per tenere il MAX(id) per il più grande option_id), quindi ricerca per l'ultimo valore con accanto al più grande option_id e così via.

L'ottimizzatore di PostgreSQL non è in grado di creare un piano simile, tuttavia PostgreSQL consente di emularlo in SQL. Se hai molti record ma pochi distinti option_id, vale la pena farlo.

Per fare questo, prima creare l'indice:

CREATE INDEX ix_records_option_id ON records (option_id, id); 

quindi eseguire la query:

WITH RECURSIVE q (option_id) AS 
     (
     SELECT MIN(option_id) 
     FROM records 
     UNION ALL 
     SELECT (
       SELECT MIN(option_id) 
       FROM records 
       WHERE option_id > q.option_id 
       ) 
     FROM q 
     WHERE option_id IS NOT NULL 
     ) 
SELECT option_id, 
     (
     SELECT MAX(id) 
     FROM records r 
     WHERE r.option_id = q.option_id 
     ) 
FROM q 
WHERE option_id IS NOT NULL 

vedere sul sqlfiddle.com: http://sqlfiddle.com/#!15/4d77d/4