主页 / dba / 问题 / 233610
Accepted
peterh
Asked: 2019-04-01 09:19:37 +0800 CST

如何在大表的有序列中获取最后一个非空值？

  • 772

我有以下输入：

 id | value 
----+-------
  1 |   136
  2 |  NULL
  3 |   650
  4 |  NULL
  5 |  NULL
  6 |  NULL
  7 |   954
  8 |  NULL
  9 |   104
 10 |  NULL

我期待以下结果：

 id | value 
----+-------
  1 |   136
  2 |   136
  3 |   650
  4 |   650
  5 |   650
  6 |   650
  7 |   954
  8 |   954
  9 |   104
 10 |   104

简单的解决方案是将表与<关系连接起来，然后选择 a 中的MAX值GROUP BY：

WITH tmp AS (
  SELECT t2.id, MAX(t1.id) AS lastKnownId
  FROM t t1, t t2
  WHERE
    t1.value IS NOT NULL
    AND
    t2.id >= t1.id
  GROUP BY t2.id
)
SELECT
  tmp.id, t.value
FROM t, tmp
WHERE t.id = tmp.lastKnownId;

但是，此代码的简单执行将在内部创建输入表行数的平方（O(n^2)）。我希望 t-sql 对其进行优化 - 在块/记录级别上，要做的任务非常简单且线性，本质上是一个 for 循环（O(n)）。

但是，在我的实验中，最新的 MS SQL 2016 无法正确优化此查询，导致无法针对大型输入表执行此查询。

此外，查询必须快速运行，使得类似简单（但非常不同）的基于游标的解决方案不可行。

使用一些内存支持的临时表可能是一个很好的折衷方案，但我不确定它是否可以运行得更快，考虑到我使用子查询的示例查询不起作用。

我也在考虑从 t-sql 文档中挖掘出一些窗口函数，什么可以被欺骗来做我想做的事情。例如，累积总和做了一些非常相似的事情，但我无法欺骗它给出最新的非空元素，而不是之前元素的总和。

理想的解决方案是没有过程代码或临时表的快速查询。或者，使用临时表的解决方案也可以，但程序上迭代表不是。

sql-server t-sql

3 个回答

  1. Best Answer

    Itzik Ben-Gan 在他的文章The Last non NULL Puzzle中给出了此类问题的常见解决方案：

    DROP TABLE IF EXISTS dbo.Example;

CREATE TABLE dbo.Example
(
    id integer PRIMARY KEY,
    val integer NULL
);

INSERT dbo.Example
    (id, val)
VALUES
    (1, 136),
    (2, NULL),
    (3, 650),
    (4, NULL),
    (5, NULL),
    (6, NULL),
    (7, 954),
    (8, NULL),
    (9, 104),
    (10, NULL);

SELECT
    E.id,
    E.val,
    lastval =
        CAST(
            SUBSTRING(
                MAX(CAST(E.id AS binary(4)) + CAST(E.val AS binary(4))) OVER (
                    ORDER BY E.id
                    ROWS UNBOUNDED PRECEDING),
            5, 4)
        AS integer)
FROM dbo.Example AS E
ORDER BY
    E.id;

    演示：db<>fiddle

    • 12

  2. 我希望 t-sql 对其进行优化 - 在块/记录级别上，要做的任务非常简单且线性，本质上是一个 for 循环（ O(n) ）。

    那不是你写的查询。它可能不等同于您编写的查询，具体取决于表架构的一些其他次要细节。您对查询优化器的期望过高。

    使用正确的索引，您可以通过以下 T-SQL 获得您寻求的算法：

    SELECT t1.id, ca.[VALUE] 
FROM dbo.[BIG_TABLE(FOR_U)] t1
CROSS APPLY (
    SELECT TOP (1) [VALUE]
    FROM dbo.[BIG_TABLE(FOR_U)] t2
    WHERE t2.ID <= t1.ID AND t2.[VALUE] IS NOT NULL
    ORDER BY t2.ID DESC
) ca; --ORDER BY t1.ID ASC

    对于每一行，查询处理器向后遍历索引，并在找到具有非空值的行时停止[VALUE]。在我的机器上，对于源表中的 1 亿行，这在大约 90 秒内完成。查询运行的时间超过了必要的时间，因为在客户端丢弃所有这些行时浪费了一些时间。

    我不清楚你是否需要有序的结果，或者你打算用这么大的结果集做什么。可以根据实际情况调整查询。这种方法的最大优点是它不需要在查询计划中进行排序。这有助于更大的结果集。一个缺点是，如果表中有很多 NULL，性能将不是最佳的，因为将从索引中读取许多行并丢弃。在这种情况下，您应该能够使用排除 NULL 的过滤索引来提高性能。

    测试样本数据：

    DROP TABLE IF EXISTS #t;

CREATE TABLE #t (
ID BIGINT NOT NULL
);

INSERT INTO #t WITH (TABLOCK)
SELECT TOP (10000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) - 1
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);

DROP TABLE IF EXISTS dbo.[BIG_TABLE(FOR_U)];

CREATE TABLE dbo.[BIG_TABLE(FOR_U)] (
ID BIGINT NOT NULL,
[VALUE] BIGINT NULL
);

INSERT INTO dbo.[BIG_TABLE(FOR_U)] WITH (TABLOCK)
SELECT 10000 * t1.ID + t2.ID, CASE WHEN (t1.ID + t2.ID) % 3 = 1 THEN t2.ID ELSE NULL END
FROM #t t1
CROSS JOIN #t t2;

CREATE UNIQUE CLUSTERED INDEX ADD_ORDERING ON dbo.[BIG_TABLE(FOR_U)] (ID);
    • 11

  3. 通过使用OVER()和基于此来源MAX()的一种方法可能是：COUNT()

    SELECT ID, MAX(value) OVER (PARTITION BY Value2) as value
FROM
(
    SELECT ID, value
        ,COUNT(value) OVER (ORDER BY ID) AS Value2
    FROM dbo.HugeTable
) a
ORDER BY ID;

    结果

    Id  UpdatedValue
1   136
2   136
3   650
4   650
5   650
6   650
7   954
8   954
9   104
10  104

    基于此来源的另一种方法，与第一个示例密切相关 

    ;WITH CTE As 
( 
SELECT  value,
        Id, 
        COUNT(value) 
        OVER(ORDER BY Id) As  Value2 
FROM dbo.HugeTable
),

CTE2 AS ( 
SELECT Id,
       value,
       First_Value(value)  
       OVER( PARTITION BY Value2
             ORDER BY Id) As UpdatedValue 
FROM CTE 
            ) 
SELECT Id,UpdatedValue 
FROM CTE2;
    • 8

相关问题