[.NET] LINQ 的延遲執行 (Deferred Execution)

延遲執行 (Deferred Execution) 是 LINQ 的重點技術之一,對於像是會存取資料庫的 Framework 或指令,如果在指令下的當下就執行的話,有可能會在下個指令存取之前就跑了,這樣可能會有時間差,或是下一個指令無法反應到結果上的問題...

PS: 這篇不是要和 91 打對台,只是就算看了他的文章,我還是不了解,所以我透過我的觀點來描述看看,讀者可以自由選擇要看 91 的文還是我這篇文。

延遲執行 (Deferred Execution) 是 LINQ 的重點技術之一,對於像是會存取資料庫的 Framework 或指令,如果在指令下的當下就執行的話,有可能會在下個指令存取之前就跑了,這樣可能會有時間差,或是下一個指令無法反應到結果上的問題,這個和之前在 ORM 系列文講到的 Lazy Loading (延遲載入) 不太一樣,Lazy Loading 是指已經有鍵值資料,但為了要節省查詢時間,因此只有在需要時才會載入全部的資料,而這裡的延遲執行是指說要在真正要瀏覽元素時才正式執行指令

不過我一直很好奇的是,以下面的 LINQ 指令來說:


var query = from customer in db.Customers  
            where customer.City == "Paris" 
            select customer;               

誰會是查詢的發動者?是 in?from?where?還是 select?亦或是都不發動?

依照我們前面的說明,事實上就算到了 select 也不會發動,因為查詢也有可能會複雜到這樣:


var query = from i in (from i in list
                        where i > 0
                        select i)
            where i > 5
            select new { i = i, s = "Greater Than 5" };

那如果是這樣的指令,應該是哪個 select 才是發動者呢?

延遲執行事實上想解決的就是這種問題,只是 LINQ 本身的算符太多太大了,所以我簡化一下,寫一個自己的 IQueryable<T> 以及 Queryable<T>:


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DefrredExecutionPrototype
{
    public interface IQueryable<T>
    {
        T First();
        T Last();
        IEnumerable<T> Where(Func<T, bool> WhereClause);
        IEnumerable<T> ToList();
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DefrredExecutionPrototype
{
    public class Queryable<T> : IQueryable<T> 
    {
        private IEnumerable<T> _list = null;

        public Queryable(IEnumerable<T> InitialList)
        {
            this._list = InitialList;
        }
        
        public T First()
        {
            IEnumerator<T> cursor = this._list.GetEnumerator();
            int offset = 0;

            if (this._list.Count() == 0)
                return default(T);

            while (cursor.MoveNext())
            {
                if (offset == 0)
                    return cursor.Current;
            }

            return default(T);
        }

        public T Last()
        {
            IEnumerator<T> cursor = this._list.GetEnumerator();
            int offset = 0;

            while (cursor.MoveNext())
            {
                if (offset == this._list.Count() - 1)
                    return cursor.Current;

                offset++;
            }

            return default(T);
        }

        public IEnumerable<T> Where(Func<T, bool> WhereClause)
        {
            IEnumerator<T> cursor = this._list.GetEnumerator();
            List<T> itemStore = new List<T>();

            if (this._list.Count() == 0)
                return new List<T>();

            Console.WriteLine("Invoke query");

            while (cursor.MoveNext())
            {
                if (WhereClause.Invoke(cursor.Current))
                    itemStore.Add(cursor.Current);
            }

            return itemStore;
        }

        public IEnumerable<T> ToList()
        {
            IEnumerator<T> cursor = this._list.GetEnumerator();
            List<T> itemStore = new List<T>();

            if (this._list.Count() == 0)
                return new List<T>();

            while (cursor.MoveNext())
            {
                itemStore.Add(cursor.Current);
            }

            return itemStore;
        }
    }
}

IQueryable<T> 模擬了 First(), Last(), ToList() 和 Where() 四個指令,其中 First() 和 Last() 的實作最簡單,只是把傳入的 IEnumerable<T> 的第一個或最後一個元素回傳,而 ToList() 是將所有的資料複製到 List<T> 也不難,但有點小難的是 Where()。


public IEnumerable<T> Where(Func<T, bool> WhereClause)
{
    IEnumerator<T> cursor = this._list.GetEnumerator();
    List<T> itemStore = new List<T>();

    if (this._list.Count() == 0)
        return new List<T>();

    Console.WriteLine("Invoke query");

    while (cursor.MoveNext())
    {
        if (WhereClause.Invoke(cursor.Current))
            itemStore.Add(cursor.Current);
    }

    return itemStore;
}

Where 接受一個查詢條件的引數,只是這個查詢條件是一個委派,Func<T, bool> 的意思是指會傳入一個參數 T,而回傳 bool 為結果的意思,相對於它的是 Action<T>,Action 是無傳回值的委派。在 Where 裡面會將每個 IEnumerable<T> 中的元素都丟到 WhereClause 中比對,並且只要符合的就會丟給 List<T>,這點和 ToList() 就很像。

我們的用戶端程式是這樣寫的:


List<int> list = new List<int>(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
IQueryable<int> query = new Queryable<int>(list);

Console.WriteLine("first: {0}, last: {1}", query.First(), query.Last());

foreach (var item in query.Where((i) => i % 2 == 0))
{
    Console.WriteLine(item);
}

Console.ReadLine();

實際執行,你會發現:

image

"Invoke query" 是我放在 Where() 中的一個輸出字串,這樣看起來,只有 query.Where() 時才會真正發動查詢,不過我很好奇的是,它似乎不會另外找地方存,為了證實這件事,我在迴圈中加了輸出指令,然後執行,它的結果會是:

image

這個結果就挺令人玩味了,為什麼它會完全依照順序,而不是再次產生新的空間來巡覽呢?我就用 Reflector 展開這個程式碼,發現一件有趣的事:

image

這 ... 看起來不像是程式碼本身的東西,而且,在程式中還出現了一個叫做 <Where>d_0<T> 的類別:

image

看到 1_state ... 看來似乎結論出來了,這個由編譯器產生的類別是一個有限狀態機 (Finite State Machine) 類別,我們再展開它的 MoveNext 看看:

image

裡面出現了我們下的指令。

簡單的說,在每次 Where 執行時,它並不會從頭來執行,透過由編譯器產生的這個狀態機類別,在每次巡覽元素時,會檢查狀態機的狀態,同時狀態機內會保存當下的 Queryable<T> 物件,以及最後一次巡覽到的值 (this.<>2_current),下次當巡覽要求再次呼叫時,就會由最後一次巡覽到的位置來查詢。這樣的作法可以節省巡覽時的所需要的時間和記憶體,對資料庫來說,LINQ provider 只需要在這個時候下達 SQL 指令,就能將資料取回。

透過上面的解析,能得到一個結論:LINQ 在呼叫 select 時,還是沒有引發查詢動作,真正引發查詢動作會是在 foreach,也就是 IEnumerator<T>.MoveNext(),而這個方法會被由編譯器產生的狀態機類別處理,因此開發人員通常不會感覺到,但這卻是延遲執行的精華所在。

為了證實這一點,我們在 Where() 後和 foreach 前加入一個字串 "Execute Query":


namespace DefrredExecutionPrototype
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> list = new List<int>(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
            IQueryable<int> query = new Queryable<int>(list);

            Console.WriteLine("first: {0}, last: {1}", query.First(), query.Last());
            var q = query.Where((i) => i % 2 == 0);

            Console.WriteLine("Execute query");

            foreach (var item in q)
            {
                Console.WriteLine(item);
            }

            Console.ReadLine();
        }
    }
}

它的執行結果會是:

image

"Execute query" 在 foreach 之前觸發,證明了實際的元素查詢是在 foreach 執行。

最終的 Queryable<T> 程式碼如下:


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DefrredExecutionPrototype
{
    public class Queryable<T> : IQueryable<T> 
    {
        private IEnumerable<T> _list = null;

        public Queryable(IEnumerable<T> InitialList)
        {
            this._list = InitialList;
        }
        
        public T First()
        {
            IEnumerator<T> cursor = this._list.GetEnumerator();
            int offset = 0;

            if (this._list.Count() == 0)
                return default(T);

            while (cursor.MoveNext())
            {
                if (offset == 0)
                    return cursor.Current;
            }

            return default(T);
        }

        public T Last()
        {
            IEnumerator<T> cursor = this._list.GetEnumerator();
            int offset = 0;

            while (cursor.MoveNext())
            {
                if (offset == this._list.Count() - 1)
                    return cursor.Current;

                offset++;
            }

            return default(T);
        }

        public IEnumerable<T> Where(Func<T, bool> WhereClause)
        {
            if (WhereClause == null)
                throw new ArgumentNullException("WhereClause", "WHERE clause cannot be null.");

            IEnumerator<T> cursor = this._list.GetEnumerator();
            List<T> itemStore = new List<T>();

            if (this._list.Count() == 0)
                throw new InvalidOperationException("List cannot empty.");
            
            return this.WhereImpl(WhereClause);
        }

        private IEnumerable<T> WhereImpl(Func<T, bool> WhereClause)
        {
            foreach (var item in this._list)
            {
                Console.WriteLine("Invoke query item: {0}", item);

                if (WhereClause(item))
                    yield return item;
            }
        }

        public IEnumerable<T> ToList()
        {
            IEnumerator<T> cursor = this._list.GetEnumerator();
            List<T> itemStore = new List<T>();

            if (this._list.Count() == 0)
                return new List<T>();

            while (cursor.MoveNext())
            {
                itemStore.Add(cursor.Current);
            }

            return itemStore;
        }
    }
}

Reference:

http://msmvps.com/blogs/jon_skeet/archive/2010/09/03/reimplementing-linq-to-objects-part-2-quot-where-quot.aspx

http://csharpindepth.com/Articles/Chapter6/IteratorBlockImplementation.aspx