行與最接近的列值

Question

我具有下表：

CREATE TABLE items (
    id serial 
    timestamp bigint 
    CONSTRAINT id_pkey PRIMARY KEY (id), 
); 

此表是在僅追加-方式使用，所以timestamp值與id增加。我需要找到誰的timestamp是最接近特定$value行。

查詢1：這需要兩個全表掃描。

SELECT id FROM 
    (
     (
      SELECT id, timestamp 
      FROM records 
      WHERE timestamp < $value 
      ORDER BY timestamp DESC 
      LIMIT 1 
    ) 
     UNION ALL 
     (
      SELECT id, timestamp 
      FROM items 
      WHERE timestamp >= $value 
      ORDER BY timestamp ASC 
      LIMIT 1 
    ) 
) AS tmp 
ORDER BY abs($value - timestamp) 
LIMIT 1 

查詢2：這一個看起來像它應該更快，但由於某種原因它不是

SELECT id 
FROM items 
WHERE scan.gpstimestamp >= $value 
ORDER BY id ASC 
LIMIT 1 

問題3：我與需要全表掃描一個自定義聚合試驗，但不需要對任何東西進行排序或加載任何索引。

create function closest_id_sfunc(
    agg_state bigint[2], 
    id bigint, 
    timestamp bigint, 
    target_timestamp bigint 
) 
returns bigint[2] 
immutable 
language plpgsql 
as $$ 
declare 
    difference bigint; 
begin 
    difference := abs(timestamp - target_timestamp); 
    if agg_state is null or difference < agg_state[0] then 
    agg_state[0] = difference; 
    agg_state[1] = id; 
    end if; 
    return agg_state; 
end; 
$$; 

create function closest_id_finalfunc(agg_state bigint[2]) 
returns bigint 
immutable 
strict 
language plpgsql 
as $$ 
begin 
    return agg_state[1]; 
end; 
$$; 

create aggregate closest_id (bigint, bigint, bigint) 
(
    stype  = bigint[2], 
    sfunc  = closest_id_sfunc, 
    finalfunc = closest_id_finalfunc 
); 


SELECT closest_id(id, timestamp, $value) as id FROM items 

爲什麼查詢2比查詢1慢？

Answer 1

你的第二個查詢將行不通，因爲有可能是由所提供的時間，這是更接近提供的值前行。並且精度並不是唯一的關注點：可能沒有一行，它大於所提供的時間戳（同時存在較低的值）。

你的第一個查詢看起來有效的（當你在子查詢使用limit 1太）。但是，是的，它需要兩個表掃描，當你沒有索引時，但你無法解決。您需要索引才能獲得巨大的性能提升。然而，有一些技巧可以使用。

我最初的想法是，你能避免外部查詢的排序的成本，通過使用條件語句來代替：

（注：我將使用ts作爲列名，timestamp是一個關鍵詞&不應該作爲列名，除非它被轉義。）

with l as (
    select id, ts 
    from  items 
    where ts < $value 
    order by ts desc 
    limit 1 
), 
g as (
    select id, ts 
    from  items 
    where ts >= $value 
    order by ts asc 
    limit 1 
) 
select case 
      when abs($value - l.ts) < abs($value - g.ts) 
      then l.id 
      else coalesce(g.id, l.id) 
      end id 
from  l 
full join g on true 

然而，這僅僅引起我的測試中一個微小的性能增益（似乎PostgreSQL是非常聰明的排序只有兩行）。

您可以通過使用一些PostgreSQL的幾何類型的直接「距離」計算加速您的查詢。注意：這些類型通常使用double precision作爲值，因此它們可以包含舍入錯誤。如果您的值是真正的unix時間戳（在bigint中），這很可能不是問題。

下面是使用上point(ts, 0)始終可用point型的距離操作<->（所以第二個座標始終爲零）查詢：

select id 
from  items 
order by point(ts, 0) <-> point($value, 0) 
limit 1 

在我的測試，這會花費〜你原來的70％查詢（或CTE變體）。

您還可以使用cube module'scube型&其（歐幾里得）距離操作<->（9。6+特徵）上cube(ts)（所以立方體將始終是一個一維的點）：

select id 
from  items 
order by cube(ts) <-> cube($value) 
limit 1 

這相當於在速度point變體。它會有一些不同，當你使用它的索引。

（注：你可以用create extension cube;初始化模塊）

指標

所以，最有趣的部分（S）：

你原來的查詢（或CTE變體）能使用以下（覆蓋）指數：

create index idx_items_ts_id on items (ts, id) 

有了這個，你原來的查詢（和CTE VAR iant）使用僅索引掃描，其成本約爲相同查詢的1.5％（沒有索引）。

的point變體可以使用下面的GiST索引：

（注意：需要對btree_gist模塊id是索引的一部分，您可以用create extension btree_gist;初始化模塊）

create index idx_items_point_gist on items using gist (point(ts, 0), id) 

這樣，point變體花費了原始查詢的約1％（沒有索引）。

cube的變體可以使用下面的GiST指數：

（注意：這也需要btree_gist模塊）

create index idx_items_cube_gist on items using gist (cube(ts), id) 

再次，這是仍比得上point變體。

結論（見編輯後）

可以實現與使用point或cube最佳性能（後者需要9.6+）。此外，索引可以幫助你很多。

其它注意事項：

• 的point變種實際上有時快（比cube變體）
• 的PostgreSQL花了很長的時間來建立cube指數&我完全不知道爲什麼
• 理論上，cube索引應該更小，因爲它不包含不必要的零。但是，因爲它們更普遍（N維），所以我可能並不正確。我建議可以嘗試兩個&措施（兩個指數大小&性能）。

http://rextester.com/KNY52367（查詢在這裏爲cube太多，但將無法運行，因爲rextester使用9.5現在）。我也測試了一個自定義的聚合解決方案（基本上是你的版本，但我用language sql函數來加速一點點，但仍然），它比你的原始查詢慢了10倍。恕我直言，這是不值得的。 http://rextester.com/PLG94853

編輯：只注意到，該btree_gist模塊增加了用於基本類型的距離操作<->（如bigint）的支持。

所以這個查詢將超越甚至point和cube變種太（一點點）：

select id 
from  items 
order by ts <-> $value 
limit 1 

而這個指數將工作最上面的查詢：

create index idx_items_ts_gist on items using gist (ts, id) 

http://rextester.com/XUF56126