Postgresql

Question

我正在 Postgres 中实现 LRU 缓存。

我有一个项目清单。每个项目都有优先级和权重。优先级越低，必须越早从缓存中逐出。让我们来看看以下项目：

priority | weight
-----------------
1          2
2          3
3          3
4          1
5          2

现在，我想为要添加的新项目腾出空间。此新项目的权重为 6，因此必须删除优先级为 1、2 和 3 的项目（前三行）以便为该新项目腾出位置.

我正在尝试对这些行进行查询 returns。目前，我有以下解决方案：

with
item (priority, weight) as (
    select 1, 2 union all
    select 2, 3 union all
    select 3, 3 union all
    select 4, 1 union all
    select 5, 2
),
item_weighted (priority, cumulative_weight) as (
    select  priority, sum(weight) over (order by priority)
    from    item
)
select  priority
from    item_weighted
where   priority <= (select priority from item_weighted where cumulative_weight >= 6 order by priority limit 1);

解释：

在CTE中item_weighted我计算每件物品的累计重量
在查询本身中，我 select 优先级低于或高于累积权重大于 6 的项目的优先级的所有项目。

所以，这行得通。但是，我对这个解决方案并不是很满意。首先 select 一行，然后 select 该行之前的所有行，对我来说似乎很奇怪。

我相信还有更优雅的方法。这可以改进吗？

Answer 1

我会使用 lag window 函数：

SELECT priority
FROM (SELECT priority,
             lag(cumulative_weight, 1, BIGINT '0')
                OVER (ORDER BY cumulative_weight) lagging_weightsum
      FROM (SELECT priority,
                   sum(weight)
                      OVER (ORDER BY priority) cumulative_weight
            FROM item
           ) cumulated
     ) lagging
WHERE lagging_weightsum < 6;

我不知道那是否更优雅，但它不会扫描 table 两次。

如果你有两次相同的优先级怎么办？ table 不应该有主键吗？

Postgresql - LRU 缓存的实现 - 逐出项

Postgresql - implementation of LRU cache - eviction of items

window-functions