This is an SQL version of that question.
Shops and groups
The problem domain is a collection of shops (identified by an int shop_id number) each of which is assigned to a group_id (also identified by an int). The association between shop_id and group_id is contained within shops table.
Simple inventory
The simple inventory is stored in table shop_stock. That table contains those fields: item_idx, shop_id, and amount. The item_idx field is a string containing the item identifier, and the shop_id represents the shop that has the item and amount is an integer representing the quantity of the item at that shop.
Effective inventory
The simple inventory is simply the number of items at each shop, as described above, but the desired effective inventory takes into account the fact that the inventory of nearby shops could, if needed, be quickly moved to one particular shop. Thus, the effective inventory of a particular shop represents the simple inventory of that shop plus that of nearby stores. Nearby stores and the direction of possible movement of inventory is represented in sgm table which contains the following fields: group_from and group_to. For example, a row in the table might say 8 15 which means that any inventory in group 8 can be counted in the effective inventory of all shops in group 15. These associations are many-to-many (that is group 8 might feed multiple groups and group 15 might be fed from multiple other groups) and not necessarily reciprocal. That is, group 8 inventory may be moved to group 15 shops but not necessarily the other direction unless explicitly stated in sgm table.
Additionally, all shops within the same group also share their effective inventory without needing a row with that in the sgm table.
Finally, some warehouse shops (those with shop_id > 10000) have extra storage available and goods are only transferred from and never to such shops. To differentiate, the program actually calculates two effective inventory quantities for each store; total which is the effective inventory from all stores including these warehouse shops and total10k which is the effective inventory excluding these warehouse shops.
Tables
CREATE TABLE shops (
shop_id int(11) NOT NULL,
group_id int(11),
PRIMARY KEY (shop_id)
);
CREATE TABLE sgm (
id int(11) NOT NULL AUTO_INCREMENT,
group_from int(11),
group_to int(11),
PRIMARY KEY (id)
);
CREATE TABLE shop_stock (
id int(11) NOT NULL AUTO_INCREMENT,
item_idx varchar(50),
shop_id int(11),
amount int(11),
PRIMARY KEY (id)
);
Result table
CREATE TABLE shop_stock_total (
id int(11) NOT NULL AUTO_INCREMENT,
item_idx varchar(50),
shop_id int(11),
total int(11),
total10k int(11),
PRIMARY KEY (id)
);
Note: shop_stock table contains only meaningful data (i.e. no zero amounts stored). However, in case of item could be moved there, it should be present in shop_stock_total table, although it was missing in shop_stock for that shop_id.
Solution
The proposed solution work really slow (do not try to run without indexes):
insert into shop_stock_total (item_idx, shop_id, total, total10k)
select
zp.item_idx,
s.shop_id,
SUM(
IFNULL(ss.amount, 0)
+ IFNULL(ss2.amount, 0)
+ IFNULL(ss3.amount, 0)
) total,
SUM(
IF(ss.shop_id<10000, IFNULL(ss.amount, 0), 0)
+ IF(ss2.shop_id<10000, IFNULL(ss2.amount, 0), 0)
+ IF(ss3.shop_id<10000, IFNULL(ss3.amount, 0), 0)
) total10k
from
(select distinct item_idx from shop_stock) zp
join shops s on s.shop_id > 0
left join shop_stock ss on s.shop_id = ss.shop_id and ss.item_idx = zp.item_idx
left join shops s2 on s.group_id = s2.group_id and s.shop_id <> s2.shop_id
left join shop_stock ss2 on s2.shop_id = ss2.shop_id and ss2.item_idx = zp.item_idx
left join sgm on s.group_id = sgm.group_to
left join shops s3 on sgm.group_from = s3.group_id
left join shop_stock ss3 on s3.shop_id = ss3.shop_id and ss3.item_idx = zp.item_idx
where
ss.amount IS NOT NULL OR ss2.amount IS NOT NULL OR ss3.amount IS NOT NULL
group by
zp.item_idx, s.shop_id
;
query plan (without indexes)
+----+-------------+------------------+------------+-------+---------------+---------+---------+------+-------+----------+----------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+------------------+------------+-------+---------------+---------+---------+------+-------+----------+----------------------------------------------------+
| 1 | INSERT | shop_stock_total | NULL | ALL | NULL | NULL | NULL | NULL | NULL | NULL | NULL |
| 1 | PRIMARY | s | NULL | range | PRIMARY | PRIMARY | 4 | NULL | 78 | 100.00 | Using where; Using temporary; Using filesort |
| 1 | PRIMARY | <derived2> | NULL | ALL | NULL | NULL | NULL | NULL | 85125 | 100.00 | Using join buffer (Block Nested Loop) |
| 1 | PRIMARY | ss | NULL | ALL | NULL | NULL | NULL | NULL | 85125 | 100.00 | Using where; Using join buffer (Block Nested Loop) |
| 1 | PRIMARY | s2 | NULL | ALL | NULL | NULL | NULL | NULL | 79 | 100.00 | Using where; Using join buffer (Block Nested Loop) |
| 1 | PRIMARY | ss2 | NULL | ALL | NULL | NULL | NULL | NULL | 85125 | 100.00 | Using where; Using join buffer (Block Nested Loop) |
| 1 | PRIMARY | sgm | NULL | ALL | NULL | NULL | NULL | NULL | 792 | 100.00 | Using where; Using join buffer (Block Nested Loop) |
| 1 | PRIMARY | s3 | NULL | ALL | NULL | NULL | NULL | NULL | 79 | 100.00 | Using where; Using join buffer (Block Nested Loop) |
| 1 | PRIMARY | ss3 | NULL | ALL | NULL | NULL | NULL | NULL | 85125 | 100.00 | Using where; Using join buffer (Block Nested Loop) |
| 2 | DERIVED | shop_stock | NULL | ALL | NULL | NULL | NULL | NULL | 85125 | 100.00 | Using temporary |
+----+-------------+------------------+------------+-------+---------------+---------+---------+------+-------+----------+----------------------------------------------------+
Indexes
create index ix_item_shop on shop_stock (item_idx, shop_id);
create index ix_item_shop_amount on shop_stock (item_idx, shop_id, amount);
create index ix_shop_group on shops (shop_id, group_id);
create index ix_group_shop on shops (group_id, shop_id);
create index ix_from_to on sgm (group_from, group_to);
create index ix_to_from on sgm (group_to, group_from);
Query plan with indexes
+----+-------------+------------------+------------+-------+----------------------------------+---------------------+---------+---------------------------------+-------+----------+----------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+------------------+------------+-------+----------------------------------+---------------------+---------+---------------------------------+-------+----------+----------------------------------------------+
| 1 | INSERT | shop_stock_total | NULL | ALL | NULL | NULL | NULL | NULL | NULL | NULL | NULL |
| 1 | PRIMARY | s | NULL | range | PRIMARY,ix_shop_group | PRIMARY | 4 | NULL | 78 | 100.00 | Using where; Using temporary; Using filesort |
| 1 | PRIMARY | <derived2> | NULL | ALL | NULL | NULL | NULL | NULL | 15413 | 100.00 | Using join buffer (Block Nested Loop) |
| 1 | PRIMARY | ss | NULL | ref | ix_item_shop,ix_item_shop_amount | ix_item_shop_amount | 158 | zp.item_idx,sst_test.s.shop_id | 1 | 100.00 | Using index |
| 1 | PRIMARY | s2 | NULL | ref | ix_group_shop | ix_group_shop | 5 | sst_test.s.group_id | 1 | 100.00 | Using where; Using index |
| 1 | PRIMARY | ss2 | NULL | ref | ix_item_shop,ix_item_shop_amount | ix_item_shop_amount | 158 | zp.item_idx,sst_test.s2.shop_id | 1 | 100.00 | Using index |
| 1 | PRIMARY | sgm | NULL | ref | ix_to_from | ix_to_from | 5 | sst_test.s.group_id | 16 | 100.00 | Using index |
| 1 | PRIMARY | s3 | NULL | ref | ix_group_shop | ix_group_shop | 5 | sst_test.sgm.group_from | 1 | 100.00 | Using index |
| 1 | PRIMARY | ss3 | NULL | ref | ix_item_shop,ix_item_shop_amount | ix_item_shop_amount | 158 | zp.item_idx,sst_test.s3.shop_id | 1 | 100.00 | Using where; Using index |
| 2 | DERIVED | shop_stock | NULL | range | ix_item_shop,ix_item_shop_amount | ix_item_shop | 153 | NULL | 15413 | 100.00 | Using index for group-by |
+----+-------------+------------------+------------+-------+----------------------------------+---------------------+---------+---------------------------------+-------+----------+----------------------------------------------+
Still very slow: 571766 rows affected (3 min 35.93 sec).
Well, test server is virtual machine with limited amounts of memory.
test server
Intel(R) Xeon(R) CPU X5660 @ 2.80GHz (2 cores for VM)
free
total used free shared buff/cache available
Mem: 3080280 1109944 196164 105300 1774172 858476
mysql configuration
key_buffer_size = 16M
max_allowed_packet = 16M
thread_stack = 192K
thread_cache_size = 8
max_allowed_packet = 2M
query_cache_limit = 1M
query_cache_size = 16M
The database scheme and data are in dump.sql file on Gitlab. https://gitlab.com/pk72/shop-stock-total
