sqlite 在SQL中计算运行经验秩

c7rzv4ha  于 2022-12-19  发布在  SQLite
关注(0)|答案(1)|浏览(128)

我有一张表格

CREATE TABLE data (n INTEGER PRIMARY KEY, x REAL)

我想为每一行计算data.x在所有data.n较小的行上的经验秩。

SELECT data.n, COUNT(*) AS cnt
  FROM data 
  JOIN data AS megadata
 WHERE data.n >= megadata.n
   AND data.x >= megadata.x
 GROUP BY data.n

但这似乎非常昂贵,因为我可以通过以下方法计算所有数据的秩

SELECT data.n, RANK() OVER (ORDER BY data.x ASC) AS totalcnt
  FROM data

相当快。
有没有一种方法可以使用SQL(窗口函数)来更有效地实现我想要的?
目前,我在数据库外部计算和维护它,因为数据流进入,使用堆样式的数据结构SortedList,这感觉就像窗口函数 * 可以 * 为我做的,如果我更好地了解SQL语法的话。

示例以下脚本

import sqlite3
import pandas as pd
from sortedcontainers import SortedList

conn = sqlite3.connect(":memory:")
with conn:
    conn.execute("""
        CREATE TABLE data (n INTEGER PRIMARY KEY, x REAL)
    """)
    conn.executemany("""
        INSERT INTO DATA VALUES(?, ?)
    """, [ (1, 7), (2, 10), (3, 8), (4, 6), (5, 9), (6, 7) ])
    print("---------- Input Data -------------")
    print(pd.read_sql_query("SELECT * FROM data", conn))
    # This solution feels O(n^2)
    print("-------- Desired Output -----------")
    print(pd.read_sql_query("""
        SELECT data.n, COUNT(*) AS cnt
          FROM data 
          JOIN data AS megadata 
         WHERE data.n >= megadata.n
           AND data.x >= megadata.x
         GROUP BY data.n
    """, conn))
    # Whereas this solution is definitely O(n log(n))
    print("--------- Sorted List ------------")
    sl = SortedList()
    for rownum, (n, x) in enumerate(conn.execute("""
        SELECT * 
          FROM DATA
         ORDER BY n
    """)):
        runningrank = 1 + sl.bisect_right(x)
        print(f'{rownum} {n} {runningrank}')
        sl.add(x)

产生所需的输出

---------- Input Data -------------
   n     x
0  1   7.0
1  2  10.0
2  3   8.0
3  4   6.0
4  5   9.0
5  6   7.0
-------- Desired Output -----------
   n  cnt
0  1    1
1  2    2
2  3    2
3  4    1
4  5    4
5  6    3
--------- Sorted List ------------
0 1 1
1 2 2
2 3 2
3 4 1
4 5 4
5 6 3

但是SQL查询比将数据按顺序流传输到SortedList并调用bisect_right要慢得多。

rur96b6h

rur96b6h1#

我不知道有什么方法可以通过单个窗口函数而不需要子查询来处理这种需求。
此外,您要应用的条件会阻止使用索引,因为它记录在The SQLite Query Optimizer Overview中。
您的查询很好,理论上(但实际上并非如此)最好删除WHERE子句并将其条件移到ON子句中:

SELECT d1.n, 
       COUNT(*) AS cnt
FROM data d1 INNER JOIN data d2
ON d2.n <= d1.n AND d2.x <= d1.x
GROUP BY d1.n;

此外,我相信通过简单地使用相关子查询,性能至少会相当(如果不是更好的话):

SELECT d1.n, 
       (SELECT COUNT(*) FROM data d2 WHERE d2.n <= d1.n AND d2.x <= d1.x) AS cnt
FROM data d1;

参见demo

相关问题