window functions - Postgresql - implementation of LRU cache - eviction of items -


i implementing lru cache in postgres.

i have list of items. each item has priority , weight. lower priority, earlier must evicted cache. let's take following items:

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

now, want make room new item added. weight of new item 6, items of priority 1, 2 , 3 (the first 3 rows) must removed make place new item.

i trying come query returns these row. currently, have following solution:

with item (priority, weight) (     select 1, 2 union     select 2, 3 union     select 3, 3 union     select 4, 1 union     select 5, 2 ), item_weighted (priority, cumulative_weight) (     select  priority, sum(weight) on (order priority)        item ) select  priority    item_weighted   priority <= (select priority item_weighted cumulative_weight >= 6 order priority limit 1); 

explanation:

  • in cte item_weighted calculate cumulative weight of each item.
  • in query itself, select items priority lower or greater priority of item where cumulative weight becomes greater 6.

so, works. but, not really happy solution. first selecting single row, , selecting rows before row, seems odd me.

i believe there more elegant approaches possible. can improved?

i use lag window function:

select priority (select priority,              lag(cumulative_weight, 1, bigint '0')                 on (order cumulative_weight) lagging_weightsum       (select priority,                    sum(weight)                       on (order priority) cumulative_weight             item            ) cumulated      ) lagging lagging_weightsum < 6; 

i don't know if more elegant, not scan table twice.

what if have same priority twice? shouldn't table have primary key?


Comments

Popular posts from this blog

'hasOwnProperty' in javascript -

python - ValueError: No axis named 1 for object type <class 'pandas.core.series.Series'> -

Command prompt result in label. Python 2.7 -